The Quest for the Minimal Hardness Assumptions

Since most interesting cryptographic tasks are impossible to achieve with absolute, information-theoretic security, modern cryptography aims to design cryptographic primitives (i.e., algorithms/protocols) that are computationally infeasible to break. Proving lower bounds of the type needed, however, seems beyond the reach of current techniques in complexity theory. Thus, research in the Foundations of Cryptography has aimed to design primitives based on complexity assumptions that are as weak as possible. The Golden Grail is basing Cryptography on the minimal hardness assumption of the existence of one-way functions. We will overview this fascinating research area and describe our recent contributions. On one hand, we will describe new implications and constructions with improved efficiency based on one-way functions. On the other hand, we will see new lower bound on the efficiency of such constructions.