Cryptology ePrint Archive: Report 2017/365

The Complexity of Public-Key Cryptography

Boaz Barak

Abstract: We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This survey/tutorial was published in the book "Tutorials on the Foundations of Cryptography", dedicated to Oded Goldreich on his 60th birthday.

Category / Keywords: Public key encryption, assumptions, post quantum cryptography

Original Publication (with minor differences): Book of tutorials in honor of Oded Goldreich's 60th birthday

Date: received 20 Apr 2017, last revised 27 Apr 2017

Contact author: b at boazbarak org

Available format(s): PDF | BibTeX Citation

Version: 20170428:163650 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]