Groups -- Complexity -- Cryptology 01 (2009), No. 1, 001--012
Copyright Heldermann Verlag 2009
A Complete Public-Key Cryptosystem
Dima Grigoriev
IRMAR, Université de Rennes, Campus de Beaulieu, 35042 Rennes, France
dmitry.grigoryev@univ-rennes1.fr
Edward A. Hirsch
Steklov Institute of Mathematics, 27 Fontanka, 191023 St. Petersburg, Russia
hirsch@pdmi.ras.ru
Konstantin Pervyshev
Dept. of Computer Science and Engineering, University of California, 9500 Gilman Drive, La Jolla, CA 92093-0404, U.S.A.
pervyshev@gmail.com
We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal and probabilistic encryption of Goldwasser and Micali, this class contains also Ajtai-Dwork and NTRU cryptosystems. The latter two make errors with a small positive probability.
[ Fulltext-pdf (136 KB)] for subscribers only.