טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGoren Yaron
SubjectBasing Weak Public-Key Cryptography on Strong One-Way
Functions
DepartmentDepartment of Computer Science
Supervisor Professor Yuval Ishai
Full Thesis textFull thesis text - English Version


Abstract

The fundamental cryptographic primitives and protocols can be roughly divided into two categories: “private cryptography” hich 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.