Double-checking PRP

[preda]

Originally Posted by SELROC

It happens to the best ones :-)

If the thread stays, maybe somebody is challenged by my oh-so-broken idea to produce a better technique that actually works. I was just showing that.. the bar is not so high.. :)

[Uncwilly]

Originally Posted by preda

If the thread stays, maybe somebody is challenged by my oh-so-broken idea to produce a better technique that actually works. I was just showing that.. the bar is not so high.. :)

It is best not to delete the thread. We learn from our own (and others') failures. If someone sees that this path leads nowhere, then they can walk a different path.

[R. Gerbicz]

Originally Posted by 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.

If you can use hidden file(s), then there is a solution for this:

Let s(p)=sum(i=1,p-2,f(p,i))
where say (this is only an example)
f(p,i)=997*(i+2)^(2^64)+15*(i/2)+19*(i%3)+3*i*sqrtint(i+11)+6*nb(i+5)*(p/64) mod p
, where nb(x)=is the number of ones in the binary expansion of x.
To make it more messy instead of constant 997,15,19,3,6 use multipliers
that depends on p.

At each iteration you compute f(p,i) and update partial sum (modulo p).
if you want to save the residue at iteration=it, then ofcourse you need to save
also the partial sum(i=1,it,f(p,i)) for the possible rollback for Jacobi/strong error check.

At the end you return the standard, or extended res value and other stuff,
with the s(p) value. And knowing the function you could check it in O(p) time
(assuming that you can compute each f(p,i) in O(1) time, like above).
If the check fails, then the user cheated, or (and this is also possible) in
the check or at the user's side there was an error in the computation of s(p),
note that computing s(p) doesn't use FFT.


How hard would be to crack s(p) ? Very hard, if you make a mess function.
How hard would be to skip only a single iteration? Very hard, for this you would
need to guess f(p,i) mod p.
The same is true for skipping any length of iterations.

If we'd like the life/checking easier you could use use such functions, where
computing f(p,i) is still O(1), but computing s(p) is O(1). The above f(p,i) is such one
(at least with some precomputation) !

ps. for a "hard" function use also non-polynomial terms, like sqrtint(i), nb(i) or for other base>2.
(and avoid terms that involves non-integer arithmetic).