Tight Reductions in Cryptography
The construction of modern cryptographic systems involves cryptographic proofs. These proofs are usually based on a reduction of a well-studied computational problem P to the breaking of the system's security, where P is deemed not to be efficiently solvable. Common examples for such a problem P are the factoring of large numbers and the discrete logarithm problem in certain algebraic groups. The reduction is an algorithm R(A) solving the computational problem P built on a hypothetical efficient attacker A on the cryptographic system. Assuming such an efficient algorithm for P does not exist, A does not exist either, accordingly. Hence, the system is secure.
The "quality" of a reduction can be measured by comparing the runtime and probability of success of R(A) with those of A. Ideally, R(A)'s and A's runtime are about the same. The reduction is then called "tight". Most cryptographic proofs, however, describe non-tight reductions, where R(A) either runs significantly longer than A or provides significantly less probability of success (or even both). Thus, the reduction loses in either efficiency or effectiveness.
The tightness of reductions has immediate influence on the choice of cryptographic parameters and with that also on the efficiency of the security system. That is why tight reductions are an interesting field of research in cryptography. The current state of research leaves a number of questions open:
- How can cryptographic systems with tight reductions be constructed?
- Which requirements are put on a cryptographic system, in order to allow for tight reductions?
- Can tight reductions for existing cryptographic system be found or can their non-existence be proven?
- Can conventional techniques be improved, that prove lower and upper bounds on the tightness of reductions?
Das Ziel dieses Projektes ist, Fortschritte bei der Beantwortung dieser Fragen zu machen. Insbesondere werden im Projekt verschiedene konkrete Ideen zur Beantwortung wichtiger Teilfragen bearbeitet.
The goal of this project is answering these questions. Particularly, ideas on important aspects of the problem are pursued.
