Finding the needles in the haystack
The server creates a set of secret random primek 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.
etc.
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 20200503 at 08:17
