**Timed-Release Cryptography**

*Wenbo Mao*

**Abstract: **Let $n$ be a large composite number. Without factoring $n$, the
validation of $a^{2^t} (\bmod \, n)$ given $a$, $t$ with $gcd(a, n) =
1$ and $t < n$ can be done in $t$ squarings modulo $n$. For $t \ll n$
(e.g., $n > 2^{1024}$ and $t < 2^{100}$), no lower complexity than $t$
squarings is known to fulfill this task (even considering massive
parallelisation). Rivest et al suggested to use such constructions as
good candidates for realising timed-release crypto problems.

We argue the necessity for zero-knowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in $\log_2 t$ standard crypto operations, the correctness of $(a^e)^{2^t} (\bmod\,n)$ with respect to $a^e$ where $e$ is an RSA encryption exponent. With such a proof, a {\em Timed-release RSA Encryption} of a message $M$ can be given as $a^{2^t} M (\bmod \,n)$ with the assertion that the correct decryption of the RSA ciphertext $M^e (\bmod \, n)$ can be obtained by performing $t$ squarings modulo $n$ starting from $a$. {\em Timed-release RSA signatures} can be constructed analogously.

**Category / Keywords: **public-key cryptography / Timed-release cryptography, Zero-knowledge protocols

**Publication Info: **Submitted

**Date: **received 22 Feb 2001, last revised 7 Mar 2001

**Contact author: **wm at hplb hpl hp com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20010515:150359 (All versions of this report)

**Short URL: **ia.cr/2001/014

[ Cryptology ePrint archive ]