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.