Cryptology ePrint Archive: Report 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.
Category / Keywords: $\P\neq\NP$, promise problems, smart reductions.
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: received February 26, 1998.
Contact author: oded at theory lcs mit edu
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]