A complete public-key cryptosystem

Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev

Research output

11 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalGroups, Complexity, Cryptology
Issue number1
Publication statusPublished - 1 Apr 2009

Scopus subject areas

  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A complete public-key cryptosystem'. Together they form a unique fingerprint.

  • Cite this