Paper 2001/014

Timed-Release Cryptography

Wenbo Mao

Abstract

Let $n$ be a large composite number. Without factoring $n$, the validation of $a^{2^t}(modn)$ 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 $$ standard crypto operations, the correctness of $$ with respect to $$ where $$ is an RSA encryption exponent. With such a proof, a {\em Timed-release RSA Encryption} of a message $$ can be given as $$ with the assertion that the correct decryption of the RSA ciphertext $$ can be obtained by performing $$ squarings modulo $$ starting from $$. {\em Timed-release RSA signatures} can be constructed analogously.