3 ms·
Oh interesting. Like I wrote, I'm aware there are certain problems that can be verified efficiently, that is, whose computation time is much larger than verific
by darkmighty 9y ago
Oh interesting. Like I wrote, I'm aware there are certain problems that can be verified efficiently, that is, whose computation time is much larger than verification time, ver_t/comp_t<<1, but is it possible to take a generic program and offload it with (1) cryptographically secure verification afterwards and (2) ver_t/comp_t << 1?
As a challenge, take the problem of computing 1000000 iterations of a memory-hard hash function, such as scrypt or argon2d. If someone presents you a hash (of length N), the best you can do to verify it is actually compute the iterated hash function (assuming it has no cryptographic weakness). This would prove, in particular, that my required method is impossible (i.e. there are at least some problems that can't be efficient offloaded).
What kind of problems can the technologies you cited offload?
- mhluongo 9y agoAll sorts, but those that are easy to convince yourself about are any arithmetic or Boolean circuit.