M.Sc Student | Goren Yaron |
---|---|

Subject | Basing Weak Public-Key Cryptography on Strong One-Way Functions |

Department | Department of Computer Science |

Supervisor | Professor Yuval Ishai |

Full Thesis text |

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.