Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
    
@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 at 5:06
    
eprint.iacr.org/2011/553.pdf $\;$ –  Ricky Demer Mar 21 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 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 at 5:50
add comment

1 Answer 1

up vote 4 down vote accepted

Timelock puzzles solve this problem.

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.

See, e.g., Time Capsule cryptography? and Parallel-resistant proof-of-work scheme? and What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?


If you want a proof of work puzzle that requires the other person to do 30 seconds of work, I don't see any practical reason to worry much about quantum computers. Right now there are no quantum computers that could pose a serious threat to this scheme. If they ever become possible, you can always change the scheme out. The scheme only needs to be secure for 30 seconds, not for 30 years....

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.