Technical Report MSC-2006-33

Title: Basing Weak Public-Key Cryptography on Strong One-Way Functions
Authors: Yaron Goren
Supervisors: Yuval Ishai
Abstract: The fundamental cryptographic primitives and protocols can be roughly divided into two categories: “private cryptography” which includes private key encryption, pseudo-random generators, pseudo-random functions, bit commitment and digital signatures, and “public cryptography” which includes public key encryption, key agreement, oblivious transfer, and secure function evaluation.

We consider the question of whether it is possible to base public key cryptography on one-way functions. One-way functions are the weakest assumption commonly used in cryptography. One-way functions can be used to construct “private key” cryptographic primitives, such as private-key encryption. In contrast, there is no known construction of “public-key” cryptographic primitives, such as public-key encryption, which is based on one-way functions. Moreover, a result by Impagliazzo and Rudich suggests that standard methods cannot be used to realize such constructions.

In this work we explore the possibility of basing a weak variant of public-key cryptography on one-way functions. We show key-agreement protocols which are based on exponentially strong one-way functions, in which the gap between the resources of the the honest parties and those of the adversary is nearly quadratic.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion