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

Oded Goldreich; Shafi Goldwasser

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 1998/005

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

Oded Goldreich and 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): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: $\P\neq\NP$promise problems smart reductions.
Contact author(s): oded @ theory lcs mit edu
History: 1998-02-26: received
Short URL: https://ia.cr/1998/005
License: CC BY

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},
      note = {\url{https://eprint.iacr.org/1998/005}},
      url = {https://eprint.iacr.org/1998/005}
}