Scharfe Reduktionen in der Kryptographie

在现代密码学中，新的密码系统通常是与安全证明一起构建的。通常，这种安全性证明包括(在复杂性理论意义上)从解决经过充分研究的、假定为困难的计算问题P到破解密码系统(在明确定义的意义上)的简化。例如，P的经典例子是整数因式分解问题，或者某些代数群中的离散对数问题。该约简将密码系统上假想的、有效的攻击者A转化为计算问题的有效算法R(A)。在假设问题P不存在有效算法的情况下，这也意味着A不可能存在，从而密码体制是安全的。通过比较算法R(A)的运行时间和成功概率与攻击者A的运行时间和成功概率来衡量约简的质量。理想情况下，R(A)与A具有大致相同的运行时间和成功概率。然而，大多数安全证明描述的是非紧缩减，其中R(A)的运行时间显著大于A或成功概率显著小于A(或两者兼而有之)。约简的紧密性直接影响到密码参数的大小，从而直接影响到密码系统的效率。它被认为是密码学中的一个重要课题。然而，当前这一方向的研究现状留下了几个重要的悬而未决的问题：-如何构造紧约简的密码系统？-密码系统必须满足哪些特定的标准才能允许或不允许紧约简？-我们能为现有密码系统找到更紧的约简，或证明它们不存在吗？-我们能改进已知的证明紧密性上界和下界的技术吗？本项目提案旨在回答这些问题。特别是，我们将详细阐述几个新想法(在提案中描述)，以回答重要的子问题。

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.