Scharfe Reduktionen in der Kryptographie

• Applicant: Professor Dr.-Ing. Tibor Jager
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 265919409

In modern cryptography, new cryptosystems are usually constructed together with a proof of security. Often this security proof consists of a reduction (in a complexity-theoretic sense) from solving a well-studied, assumed-to-be-hard computational problem P to breaking the cryptosystem (in a well-defined sense). Classical examples for P are the integer factorization problem, or the discrete logarithm problem in certain algebraic groups, for instance. The reduction turns an hypothetical, efficient attacker A on the cryptosystem into an efficient algorithm R(A) for the computational problem. Under the assumption that there exists no efficient algorithm for problem P, this implies also that A can not exist, thus the cryptosystem is secure.The "quality" of a reduction can be measured by comparing the running time and success probability of algorithm R(A) to the running time and success probability of attacker A. Ideally, R(A) has about the same running time and success probability as A. Such a reduction is said to be "tight". However, most security proofs describe non-tight reductions, where R(A) has either a significantly larger running time or a significantly smaller success probability than A (or both). Thus, the reduction "loses" efficiency and/or efficacy.The tightness of reduction directly influences the size of cryptographic parameters, and thus has a direct impact to the efficiency of cryptosystems. It is considered an important topic in cryptography. However, the current state-of-the-art of research in this direction leaves several important open questions:- How can cryptosystems with tight reduction be constructed?- Which specific criterions does a cryptosystem have to meet in order to allow or disallow a tight reduction?- Can we find tighter reductions for existing cryptosystems, or prove their inexistence?- Can we improve known techniques for proving upper and lower tightness bounds?This project proposal aims at making progress towards answering these questions. In particular, we will elaborate on several new ideas (which are described in the proposal) to answer important sub-questions.

• DFG Programme: Research Grants