Double-checking PRP

[preda]

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]

Originally Posted by preda

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]

There are 742 (!) primes such that z(p) | 36756720.
See attached.

[preda]

Originally Posted by preda

There are 742 (!) primes such that z(p) | 36756720.
See attached.

And the *sorted* list of primes:

[axn]

Originally Posted by preda

There are 742 (!) primes such that z(p) | 36756720.
See attached.

What happens if the attacker computes 3^((prod P_i)+1) ?

[preda]

Originally Posted by axn

What happens if the attacker computes 3^((prod P_i)+1) ?

It fails 3^(2^L)

[axn]

Originally Posted by preda

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

[preda]

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!

[axn]

Originally Posted by preda

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

[preda]

Originally Posted by axn

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.

Originally Posted by preda

Yes, that's one of them huge mistakes :)

I was hypoglycemic or hypercaffeinated or underslept or worse.

It happens to the best ones :-)