@InProceedings{GMR84a,
replaced-by = { GMR88 },
author = { Shafi Goldwasser and Silvio Micali and Ronald L. Rivest },
title = { A `Paradoxical' solution to the signature problem (brief abstract) },
pages = { 467 },
OPTurl = { http://dx.doi.org/10.1007/3-540-39568-7_37 },
doi = { 10.1007/3-540-39568-7_37 },
booktitle = { Advances in Cryptology -- Proceedings of CRYPTO 1984 },
date = { 1985 },
editor = { George Blakley and David Chaum },
publisher = { Springer },
isbn = { 978-3-540-15658-1 },
series = { Lecture Notes in Computer Science },
volume = { 196 },
organization = { IACR },
OPTyear = { 1985 },
OPTmonth = { August },
eventdate = { 1984-08-19/1984-08-22 },
eventtitle = { CRYPTO '84 },
venue = { Santa Barbara, California },
abstract = {
We present a general signature scheme which uses
any pair of trap-door permutations $(f_0, f_1)$ for
which it is infeasible to find any $x, y$ with $f_0(x) =
f_1(y)$. The scheme possesses the novel property of
being robust against an adaptive chosen message
attack: no adversary who first asks for and then
receives signatures for messages of his choice (which
may depend on previous signatures seen) can later
forge the signature of even a single additional
message.
\par
For specific instance of our general
scheme, we prove that (1) forging signatures is
provably equivalent to factoring (i.e., factoring is
polynomial-time reducible to forging signatures, and
vice versa) while (2) forging an additional
signature, after an adaptive chosen message attack
is still equivalent to factoring. Such scheme is
``paradoxical'' since the above two properties were
believed (and even ``proven'' in the folklore) to be
contradictory.
\par
The new scheme is potentially
practical: signing and verifying signatures are
reasonably fast, and signatures are not too long.
},
}