mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-06-24, 03:49   #188
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

It's a model to calibrate your hashes against. Btw, x^(h0*h0) is not modular and can be precomputed.

Last fiddled with by patnashev on 2020-06-24 at 04:27
patnashev is online now   Reply With Quote
Old 2020-06-24, 19:48   #189
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1AFE16 Posts
Default

Some data (now using the attached sliding window exponentiation routine)

Proof level 8:
Proof generator does 15489 or 20632 squarings (48-bit vs 64-bit hash)
Server does 1080 or 1414 squarings
Proof verifier does 390625 squarings (assuming 100,000,000 exponent)

Proof level 9:
Proof generator does 31485 or 41925 squarings (48-bit vs 64-bit hash)
Server does 1207 or 1577 squarings
Proof verifier does 195312 squarings (assuming 100,000,000 exponent)

From a total system point of view, we can see that proof level 10 is currently optimal. Compared to level 9, generator does 42K more squarings to save the verifier 97K squarings.

If 800 PRP tests a day are reported to the server, I think it can handle 1.2M squarings a day. My quad core Haswells can generate 10 million squarings a day.

For me, at proof level 9, the 10500 squarings saved for 48-bit vs. 64-bit hash represents 1/2 PRP test a year.
Attached Files
File Type: c exponentiate.c (4.3 KB, 6 views)
Prime95 is offline   Reply With Quote
Old 2020-06-24, 20:02   #190
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11010111111102 Posts
Default

Quote:
Originally Posted by preda View Post
The attack would be so-much-more less practical for 48 or 64 bit hash. So, I'd take the above attack more like an indication of "lack of a practical attack", right?
In choosing the hash function, we are really guarding against a researcher discovering a weakness in the system that is not presently known.

If the future weakness is a reduction in brute force effort, then a longer hash key is our safe guard. So let's rule out 32-bit hash values.

If the future weakness revolves around a small hash value, let's thwart them by making all hash values >= 2^32.

If the future weakness results from some root-of-unity issue, lets rule out multiples of the PRP base 3. I'd remove multiples of two just for good measure. Removing hashes with more small primes is also possible. In total, this does not greatly reduce the search space for the brute force attacker.

I'm happy with 48-bit or 64-bit (or anything in-between!). When eliminating 0 mod 3 hashes, the scheme should not be a simple "add 2" as that would favor 2 mod 3 hashes.

Further comments? Time to come up with the concrete algorithm?

Last fiddled with by Prime95 on 2020-06-24 at 20:09
Prime95 is offline   Reply With Quote
Old 2020-06-24, 20:39   #191
wedgingt
 
"Will Edgington"
Nov 2010
Utah, USA

1816 Posts
Default Avoiding multiples or 2 or 3 in hash values

If you just want to eliminate values that are multiples of 2 or 3:
Code:
  int add[2*3] = { 1, 0, 3, 2, 1, 0 };
  value += add[value % 6];
The value will always be either 1 or 5 mod 6 after this but with a bias towards 5 % 6. Changing one value in the array appropriately would eliminate the bias.
To avoid possibly exceeding 2^64, the array value could be subtracted instead, sometimes leading to a final value < 2^32.
If you also want to eliminate multiples of 5, expand the array to 2*3*5 appropriately.
-- Will



Quote:
Originally Posted by Prime95 View Post
In choosing the hash function, we are really guarding against a researcher discovering a weakness in the system that is not presently known.

If the future weakness is a reduction in brute force effort, then a longer hash key is our safe guard. So let's rule out 32-bit hash values.

If the future weakness revolves around a small hash value, let's thwart them by making all hash values >= 2^32.

If the future weakness results from some root-of-unity issue, lets rule out multiples of the PRP base 3. I'd remove multiples of two just for good measure. Removing hashes with more small primes is also possible. In total, this does not greatly reduce the search space for the brute force attacker.

I'm happy with 48-bit or 64-bit (or anything in-between!). When eliminating 0 mod 3 hashes, the scheme should not be a simple "add 2" as that would favor 2 mod 3 hashes.

Further comments? Time to come up with the concrete algorithm?
wedgingt is offline   Reply With Quote
Old 2020-06-24, 21:25   #192
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13·19·23 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Some data (now using the attached sliding window exponentiation routine)

Proof level 8:
Proof generator does 15489 or 20632 squarings (48-bit vs 64-bit hash)
Server does 1080 or 1414 squarings
Proof verifier does 390625 squarings (assuming 100,000,000 exponent)

Proof level 9:
Proof generator does 31485 or 41925 squarings (48-bit vs 64-bit hash)
Server does 1207 or 1577 squarings
Proof verifier does 195312 squarings (assuming 100,000,000 exponent)

From a total system point of view, we can see that proof level 10 is currently optimal. Compared to level 9, generator does 42K more squarings to save the verifier 97K squarings.

If 800 PRP tests a day are reported to the server, I think it can handle 1.2M squarings a day. My quad core Haswells can generate 10 million squarings a day.

For me, at proof level 9, the 10500 squarings saved for 48-bit vs. 64-bit hash represents 1/2 PRP test a year.
What are the current estimates of storage and bandwidth requirements of each of these levels?
henryzz is offline   Reply With Quote
Old 2020-06-24, 22:54   #193
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

100010011102 Posts
Default

Quote:
Originally Posted by Prime95 View Post
In choosing the hash function, we are really guarding against a researcher discovering a weakness in the system that is not presently known.

If the future weakness is a reduction in brute force effort, then a longer hash key is our safe guard. So let's rule out 32-bit hash values.

If the future weakness revolves around a small hash value, let's thwart them by making all hash values >= 2^32.

If the future weakness results from some root-of-unity issue, lets rule out multiples of the PRP base 3. I'd remove multiples of two just for good measure. Removing hashes with more small primes is also possible. In total, this does not greatly reduce the search space for the brute force attacker.

I'm happy with 48-bit or 64-bit (or anything in-between!). When eliminating 0 mod 3 hashes, the scheme should not be a simple "add 2" as that would favor 2 mod 3 hashes.

Further comments? Time to come up with the concrete algorithm?
A more complicated hash does not make a better hash (but it can make a weaker hash if not careful). I think it's Knuth who said something on the lines of "a random algorithm does not make a good random number generator". It's unlikely to obtain any security benefit by doing "hardening in the dark" without knowing why or what we're hardening against.

I propose we use simply SHA3-256 truncated to 64bits for the "h" exponents. The chaining of the hash OTOH is done using the full SHA3-256.

Maybe we should also present our "simple" hash scheme to the larger crypto community and ask them for an attack?
preda is offline   Reply With Quote
Old 2020-06-25, 14:14   #194
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·5·11·37 Posts
Default

Quote:
Originally Posted by preda View Post
Maybe we should also present our "simple" hash scheme to the larger crypto community and ask them for an attack?
Get best available informed input, yes.
I think doing that repeatedly is one of the things that has made prime95 and gpuowl as good as they already are.
kriesel is offline   Reply With Quote
Old 2020-06-28, 05:48   #195
patnashev
 
"Pavel Atnashev"
Mar 2020

3710 Posts
Default

We've started searching for GFN-15 Mega (b^32768+1, 1M digits). b is a hundred-bit number, but Pietrzak VDF works just fine with such numbers.
patnashev is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
phi function rula Homework Help 3 2017-01-18 01:41
delay in crediting? ixfd64 PrimeNet 7 2008-10-20 20:45
Why delay between posts? JHagerson Forum Feedback 1 2006-05-13 21:30
Minimum delay between server connections vaughan ElevenSmooth 5 2005-09-08 17:17
Stats delay ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 13:34.

Fri Jul 10 13:34:35 UTC 2020 up 107 days, 11:07, 2 users, load averages: 2.56, 2.13, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.