View Single Post
Old 2020-05-03, 08:17   #58
retina's Avatar
"The unspeakable one"
Jun 2006
My evil lair

32·643 Posts
Default Finding the needles in the haystack

The server creates a set of secret random prime-k values and computes the remainders.
Send the remainders to the client.
The clients task is to find the k values that generate the remainders.
Client sends the found k values to the server for verification.

How would that affect the client code if it needs to find some specific remainder values instead of just a remainder of zero, or the smallest remainder?

If you had one remainder then on average the client needs to run 50% of the work before finding the k value.
If you had two remainders then on average the client needs to run 75% of the work before finding both k values.

Considerations: The set of k values might not exactly match each other when two k values generate the same remainder, so just send one of them and the server can still verify the remainder is correct. The server doesn't need to remember the k values it chooses, just the remainders it sends.

Last fiddled with by retina on 2020-05-03 at 08:17
retina is online now   Reply With Quote