Minimal assumptions in cryptography

Abstract

Virtually all of modern cryptography relies on unproven assumptions. This is necessary, as the existence of cryptography would have wide ranging implications. In particular, it would hold that P =/= NP, which is not known to be true. Nevertheless, there clearly is a risk that the assumptions may be wrong. Therefore, an important field of research explores which assumptions are strictly necessary under different circumstances. This thesis contributes to this field by establishing lower bounds on the minimal assumptions in three different areas of cryptography. We establish that assuming the existence of physically uncloneable functions (PUF), a specific kind of secure hardware, is not by itself sufficient to allow for secure two-party computation protocols without trusted setup. Specifically, we prove that unconditionally secure oblivious transfer can in general not be constructed from PUFs. Secondly, we establish a bound on the potential tightness of security proofs for Schnorr signatures. Essentially, no security proof based on virtually arbitrary non-interactive assumptions defined over an abstract group can be significantly tighter than the known, forking lemma based, proof. Thirdly, for very weak forms of program obfuscation, namely approximate indistinguishability obfuscation, we prove that they cannot exist with statistical security and computational assumptions are therefore necessary. This result holds unless the polynomial hierarchy collapses or one-way functions do not exist.

Fast die gesamte moderne Kryptographie beruht auf unbewiesenen Annahmen. Dies ist notwendig, da die Existenz von Kryptographie weitreichende Folgen hätte. Insbesondere, müsste gelten, dass P =/= NP, was aber unbekannt ist. Dennoch besteht das Risiko, dass die Annahmen falsch sind. Deshalb ist die Untersuchung, welche Annahmen unter verschiedenen Umständen unbedingt notwendig sind, ein wichtiges Forschungsgebiet. Diese Dissertation trägt zu diesem Gebiet bei, indem untere Schranken für minimale Annahmen in drei Gebieten der Kryptographie bewiesen werden. Wir zeigen, dass es nicht ausreicht anzunehmen, dass Physically Uncloneable Functions (PUF), eine Art von sicherer Hardware, existieren, um Protokolle für sichere Zweiparteienberechnungen ohne sogenanntes "Trusted Setup" zu konstruieren. Genauer beweisen wir, dass bedingungslos sicherer Oblivious Transfer nicht aus PUFs konstruiert werden kann. Zweitens zeigen wir eine Schranke für die mögliche "Tightness" von Sicherheitsbeweisen für Schnorrsignaturen. Im Wesentlichen kann kein Sicherheitsbeweis, basierend auf nahezu beliebigen nicht-interaktiven Annahmen über eine abstrakte Gruppe, signifikant "tighter" sein als der bekannte "Forking Lemma"-Beweis. Drittens beweisen wir für sehr schwache Formen von Program Obfuscation, nämlich "Approximate Indistinguishability Obfuscation", dass sie nicht mit statistischer Sicherheit existieren können, sondern Annahmen notwendig sind. Dieses Resultat gilt unter der Annahme, dass die polynomielle Hierarchie nicht kollabiert und One-Way-Funktionen existieren.