mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-09-24, 02:29   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

134310 Posts
Default Double-checking PRP

A longstanding problem is how to get rid of the expensive double-checking for PRP.

Let's assume that PRP with GEC is "perfect" i.e. produces no errors, ever.

Now the double-checking is still needed against attackers who intentionally fake it: they submit bogus results; they put significant effort in manufacturing genuine-looking fake results; they read the double-checking source code and mersenneforum.org and attempt to work-around 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.
preda is offline   Reply With Quote
Old 2018-09-24, 02:46   #2
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

17·79 Posts
Default

Quote:
Originally Posted by preda View Post
The server chooses, randomly, a set of primes p_i such that
(p_i - 1) | K
In fact the allowable set of p_i is: any p such that z(p) | K,

where z is the "multiplicative order of 2 mod p", i.e. 2^z==1 mod p. z | (p - 1)
preda is offline   Reply With Quote
Old 2018-09-24, 02:56   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

101001111112 Posts
Default

There are 742 (!) primes such that z(p) | 36756720.
See attached.
Attached Files
File Type: txt p.txt (5.4 KB, 44 views)
preda is offline   Reply With Quote
Old 2018-09-24, 03:00   #4
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

17·79 Posts
Default

Quote:
Originally Posted by preda View Post
There are 742 (!) primes such that z(p) | 36756720.
See attached.
And the *sorted* list of primes:
Attached Files
File Type: txt sp.txt (5.4 KB, 48 views)
preda is offline   Reply With Quote
Old 2018-09-24, 03:05   #5
axn
 
axn's Avatar
 
Jun 2003

4,861 Posts
Default

Quote:
Originally Posted by preda View Post
There are 742 (!) primes such that z(p) | 36756720.
See attached.
What happens if the attacker computes 3^((prod P_i)+1) ?
axn is offline   Reply With Quote
Old 2018-09-24, 03:15   #6
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

17×79 Posts
Default

Quote:
Originally Posted by axn View Post
What happens if the attacker computes 3^((prod P_i)+1) ?
It fails 3^(2^L)
preda is offline   Reply With Quote
Old 2018-09-24, 04:04   #7
axn
 
axn's Avatar
 
Jun 2003

4,861 Posts
Default

Quote:
Originally Posted by preda View Post
It fails 3^(2^L)
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 2018-09-24 at 04:11
axn is offline   Reply With Quote
Old 2018-09-24, 04:32   #8
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

17·79 Posts
Default

I think my initial idea doesn't work at all. I did some huge mistakes in my initial write-up. My apologies. Maybe a moderator could delete the whole thread, thanks!
preda is offline   Reply With Quote
Old 2018-09-24, 04:50   #9
axn
 
axn's Avatar
 
Jun 2003

12FD16 Posts
Default

Quote:
Originally Posted by preda View Post
I think my initial idea doesn't work at all.
Yep. The mod Mp destroys the structure and the GCD(X,S) wouldn't work
axn is offline   Reply With Quote
Old 2018-09-24, 04:54   #10
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

17·79 Posts
Default

Quote:
Originally Posted by axn View Post
Yep. The mod Mp destroys the structure and the GCD(X,S) wouldn't work
Yes, that's one of them huge mistakes :)

I was hypoglycemic or hypercaffeinated or underslept or worse.
preda is offline   Reply With Quote
Old 2018-09-24, 05:26   #11
SELROC
 

EC816 Posts
Default

Quote:
Originally Posted by preda View Post
Yes, that's one of them huge mistakes :)

I was hypoglycemic or hypercaffeinated or underslept or worse.

It happens to the best ones :-)
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Double checking gd_barnes Riesel Prime Search 68 2021-02-12 10:16
What about double-checking TF/P-1? 137ben PrimeNet 6 2012-03-13 04:01
Double checking Unregistered Information & Answers 19 2011-07-29 09:57
Double-checking milestone? jobhoti Math 17 2004-05-21 05:02
Any glory in double checking? Quacky Lounge 5 2003-12-03 02:20

All times are UTC. The time now is 00:41.

Sun Mar 7 00:41:13 UTC 2021 up 93 days, 20:52, 0 users, load averages: 1.35, 1.45, 1.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.