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} (\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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Submitted
Keywords
Timed-release cryptographyZero-knowledge protocols
Contact author(s)
wm @ hplb hpl hp com
History
2001-03-07: revised
2001-02-23: received
See all versions
Short URL
https://ia.cr/2001/014
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/014,
      author = {Wenbo Mao},
      title = {Timed-Release Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2001/014},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/014}},
      url = {https://eprint.iacr.org/2001/014}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.