Scharfe Reduktionen in der Kryptographie

密码学的急剧减少

• 批准号: 265919409
• 负责人: Professor Dr.-Ing. Tibor Jager
• 金额: --
• 依托单位: Lehrstuhl für IT Security and Cryptography
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2018-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/265919409?language=en
• 关键词: Scharfe; Reduktionen; der; Kryptographie

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.

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

项目成果

On the Impossibility of Tight Cryptographic Reductions

• DOI: 10.1007/978-3-662-49896-5_10
• 发表时间: 2016-05
• 作者: Christoph Bader;Tibor Jager;Yong Li;Sven Schäge

Simple and More Efficient PRFs with Tight Security from LWE and Matrix-DDH

• DOI: 10.1007/978-3-030-03332-3_18
• 发表时间: 2018-12
• 作者: Tibor Jager;Rafael Kurek;Jiaxin Pan

Highly Efficient Key Exchange Protocols with Optimal Tightness - Enabling real-world deployments with theoretically sound parameters

• DOI: 10.1007/978-3-030-26954-8_25
• 发表时间: 2019-08
• 期刊: The New England journal of medicine
• 作者: Katriel Cohn-Gordon;Cas J. F. Cremers;Kristian Gjøsteen;Håkon Jacobsen;Tibor Jager

Short Digital Signatures and ID-KEMs via Truncation Collision Resistance

• DOI: 10.1007/978-3-030-03329-3_8
• 发表时间: 2018-12
• 作者: Tibor Jager;Rafael Kurek

Multi-key Authenticated Encryption with Corruptions: Reductions Are Lossy

具有损坏的多密钥认证加密：减少是有损的

• DOI: 10.1007/978-3-319-70500-2_14
• 发表时间: 2017
• 作者: Tibor Jager;Martijn Stam;Ryan Stanley-Oakes;Bogdan Warinschi
• 通讯作者: Bogdan Warinschi