4 ms·
Forgive my ignorance, as I did read through everything you posted, but i'm not sure I fully understand how such a system avoids an attack of this form: functio
by darawk 11y ago
Forgive my ignorance, as I did read through everything you posted, but i'm not sure I fully understand how such a system avoids an attack of this form:
function check (bits) {
sleep(bits)
return false
}
Where 'sleep' may be replaced by some appropriately long-running, arbitrary computation (since presumably these proof programs are not allowed to actually wait). Obviously for input data as complex as a sudoku answer the sleep would be near-infinitely long, but you could surely extract at least several bits of the answer in this way and thereby iteratively extract the whole thing, no?
Is there some mitigation for this that i'm missing?
- cjg 11y agoYou are missing something: the seller can see the program that evaluates the solution.
- darawk 11y agoOf course, but if the seller has to manually inspect the program for every transaction, is this really all that useful? There are a myriad of ways to leak timing information from something like this, and to mask them amongst legitimate-seeming computations. It seems like if you're having to rely on manual program inspection, then you've already lost.
- nullc 11y agoThe amount of execution time is a simple public parameter of the system. These schemes require reducing the verification program to a circuit in advance, so its execution time is already fixed by virtue of that translation. (In practice the existing implementation is not using constant time cryptography; and so it could have timing/cache/EMI side-channels; but this is "just engineering")
- darawk 11y agoAh, of course, just fix the run time. I should have realized that. Thanks. Nice work!