# Ensuring that an operation takes a relatively specific amount of time, but easily verify the result

I want an algorithm of some sort that can ensure that an operation takes a fairly specific amount of time, but proof that this operation was done can be completed relatively inexpensively.

For instance, I can prove that an operation will probably take around 30 seconds by doing a cycle with a hashing algorithm such as SHA256 such that the output of the hash feeds directly back into the input. If I count how many hashes are computed within 30 seconds on a modern computer I can be relatively sure that it can't be significantly faster on better hardware.

So, you can ensure that another user waits for around 30 seconds by giving them the amount of rounds they must do of the hash.

And then, for the receiver to verify that they did the hash, they would calculate the given input X amount of rounds and verify that the result matches what they were given.

However, this is hard, because to verify they took that amount of time, the verifier must also take that amount of time.

Is there a way to do such a thing with the verification taking significantly less time than the actual computation?

For instance, one idea is to use asymmetric RSA encryption. Usually, signing a given input is slower than verifying the signature. So, you could possibly sign the input for X amount of rounds and then verifying X amount of rounds would be significantly faster. However the actual amount of data that would get signed would explode (because each round requires adding another signature) and I think RSA would not be secure to use in this manner.

Is there some way to do this securely and without exploding amounts of data for each required round?

-
– Ricky Demer Mar 21 '14 at 5:01
@RickyDemer very interesting and seems to solve my problem. However, I had rather not be reliant on prime numbers due to the possibilities of quantum computers becoming practical – Earlz Mar 21 '14 at 5:06
– Ricky Demer Mar 21 '14 at 5:26
@RickyDemer wow this looks like exactly the kind of reading material I was looking for. I just wish I knew more to understand it all easier :) – Earlz Mar 21 '14 at 5:31
Note that the eprint paper does not appear to claim that solutions to its puzzles are anything like unique. $\:$ If they're not close enough to unique, then giving a solution is not necessarily "proof that this operation was done". $\;\;\;\;$ – Ricky Demer Mar 21 '14 at 5:50

For instance, consider the function $f(x) = x^{2^t} \bmod n$, where $n$ is a RSA modulus and $t$ is large. For people who don't know the factorization of $n$, computing $f$ takes $t$ squarings modulo $n$. If you do know the factorization of $n$ (the private key), then computing $f$ can be done with $O(\lg n)$ squarings, regardless of how large $t$ is, by first reducing $t$ modulo $\varphi(n)$. This lets you create a puzzle that will take a controllable amount of time for someone else to solve, and where you can very efficiently verify the answer: e.g., choose $n$ to be a 2048-bit prime and $t$ to be a million, or whatever you want $t$ to be to make computing $f$ take exactly as long as you want for the other person.