International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Oded Goldreich
Shafi Goldwasser
Download:
URL: http://eprint.iacr.org/1998/005
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1998-11302,
  title={On the possibility of basing Cryptography on the assumption that $P \neq NP$},
  booktitle={IACR Eprint archive},
  keywords={$\P\neq\NP$, promise problems, smart reductions.},
  url={http://eprint.iacr.org/1998/005},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. oded@theory.lcs.mit.edu 10500 received February 26, 1998.},
  author={Oded Goldreich and Shafi Goldwasser},
  year=1998
}