
Click here for full text:
TimedRelease Cryptography
Mao, Wenbo
HPL200137
Keyword(s): timedrelease cryptography; timelock puzzles; timed commitments; efficient zeroknowledge protocols
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. Let n be a large composite number. Without t factoring n, the validation of a2 (mod n ) given a, t with gcd (a, n) = 1 and t < n can be done in t squarings modulo n. For t" n (e.g., n > 2 1024 and t < 2 100 ), no lower complexity than t squarings is known to fulfil this task (even considering massive parallelisation). Rivest et al suggested to use such constructions as good candidates for realising timedrelease crypto problems. We argue the necessity for zeroknowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in log2 t standard crypto operations, the correctness of t (ae ) 2 (mod n ) with respect to ae where e is an RSA encryption exponent. With such a proof, a Timedrelease RSA Encryption of a message M t can be given as a2 M (mod n ) with the assertion that the correct decryption of the RSA ciphertext Me (mod n ) can be obtained by performing t squarings modulo n starting from a. Timedrelease RSA signatures can be constructed analogously.
17 Pages
Back to Index
