20180924, 02:29  #1 
"Mihai Preda"
Apr 2015
1343_{10} Posts 
Doublechecking PRP
A longstanding problem is how to get rid of the expensive doublechecking for PRP.
Let's assume that PRP with GEC is "perfect" i.e. produces no errors, ever. Now the doublechecking is still needed against attackers who intentionally fake it: they submit bogus results; they put significant effort in manufacturing genuinelooking fake results; they read the doublechecking source code and mersenneforum.org and attempt to workaround any checks and tricks there. We'd like to find a technique allowing to reliably detect a fake with less effort then the effort that was put into manufacturing the fake. So here it comes: The server chooses a *special* iteration number, fixed, let's say K=36756720, and asks the user to send the "bits" at that iteration. i.e. for m==M(p)==2^p  1, to send R = 3^(2^K) %m together with the result. (the cost: no additional computation cost as the user anyway computes that, but network transfer cost for m bits, and storage cost (m bits) on the server until validation). Validation: The server chooses, randomly, a set of primes p_i such that (p_i  1)  K Computes X = 3^product(p_i) Computes S = R/3 = 3^(2^K  1) %m (which can be trivially computed from R) And verifies that X divides S (e.g. by checking that GCD(X, S)==X). In addition, the server chooses a value L < K, as large as practical, and verifies that 3^(2^L)  R The thesis is that the cheapest way for the attacker to reliably pass the test is to actually compute 3^(2^K) (there's no easy way to fake it); And the server can do the verification much cheaper than that. 
20180924, 02:46  #2 
"Mihai Preda"
Apr 2015
17·79 Posts 

20180924, 02:56  #3 
"Mihai Preda"
Apr 2015
10100111111_{2} Posts 
There are 742 (!) primes such that z(p)  36756720.
See attached. 
20180924, 03:00  #4 
"Mihai Preda"
Apr 2015
17·79 Posts 
And the *sorted* list of primes:

20180924, 03:05  #5 
Jun 2003
4,861 Posts 

20180924, 03:15  #6 
"Mihai Preda"
Apr 2015
17×79 Posts 

20180924, 04:04  #7 
Jun 2003
4,861 Posts 
ok, so they can compute (3^((prod p_i)+1)*(3^2^L) [L as large as practical to effectively fake residue]?
EDIT: Scratch that. I think it needs to be 3^((prod p_i)*C+1), such that 2^L  ((prod p_i)*C+1). Should be doable  C will be appr. L bits Last fiddled with by axn on 20180924 at 04:11 
20180924, 04:32  #8 
"Mihai Preda"
Apr 2015
17·79 Posts 
I think my initial idea doesn't work at all. I did some huge mistakes in my initial writeup. My apologies. Maybe a moderator could delete the whole thread, thanks!

20180924, 04:50  #9 
Jun 2003
12FD_{16} Posts 

20180924, 04:54  #10 
"Mihai Preda"
Apr 2015
17·79 Posts 

20180924, 05:26  #11 
EC8_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Double checking  gd_barnes  Riesel Prime Search  68  20210212 10:16 
What about doublechecking TF/P1?  137ben  PrimeNet  6  20120313 04:01 
Double checking  Unregistered  Information & Answers  19  20110729 09:57 
Doublechecking milestone?  jobhoti  Math  17  20040521 05:02 
Any glory in double checking?  Quacky  Lounge  5  20031203 02:20 