On the possibility of basing Cryptography on the assumption that $P \neq NP$

Oded Goldreich; Shafi Goldwasser

Paper 1998/005 Original: eprint.iacr.org/1998/005 ↗

On the possibility of basing Cryptography on the assumption that $P \neq NP$

Oded Goldreich

Shafi Goldwasser

Abstract

Recent works by Ajtai and by Ajtai and Dwork bring to light the old (general) question of whether it is at all possible to base the security of cryptosystems on the assumption that $\P\neq\NP$. We discuss this question and in particular review and extend a two-decade old result of Brassard regarding this question. Our conclusion is that the question remains open.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 1998-02-26: last updated; 1998-02-26: published
Short URL: https://ia.cr/1998/005
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:1998/005,
      author = {Oded Goldreich and Shafi Goldwasser},
      title = {On the possibility of basing Cryptography on the assumption that $P \neq NP$},
      howpublished = {Cryptology {ePrint} Archive, Paper 1998/005},
      year = {1998},
      url = {https://eprint.iacr.org/1998/005}
}