TWC: Small: Complexity Assumptions for Cryptographic Schemes

TWC：小：加密方案的复杂性假设

• 批准号: 1618026
• 负责人: Boaz Barak
• 金额: $ 50万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-01 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618026&HistoricalAwards=false
• 关键词: TWC; Small; Complexity; Assumptions; Cryptographic

This project investigates the foundational computational underpinnings of secure systems. Cryptographic constructions such as encryption, signatures, and more rely for their security on the conjectured computational difficulty of certain problems. For example, many public key encryption currently in use would be broken if someone discovered an efficient algorithm to factor large integers. Unfortunately, the current state of art is that we are unable to prove that these problems are truly hard, and so need to rely on unproven conjectures. Moreover, a handful of these conjectures serve as the foundations of many if not most of current cryptographic schemes, and so each such conjecture is a single point of failure whose refutation could have severe consequences for a large fraction of our systems. In particular, progress in quantum computing threatens some of these conjectures, and motivates reevaluation of the right basis for cryptography.The goal of this project is better understand and remedy these issues. Concretely, this project investigates cryptographic schemes, and particularly public key encryption, that are based on assumptions that are qualitatively different from current ones, and hence more likely to survive technological or algorithmic advances that would break current schemes. The project obtains new forms of evidence for computational assumptions, thus deriving some assurances that current schemes are secure. The project also explores assumptions for new cryptographic primitives such as software obfuscation that are more well founded by computational complexity considerations

本项目研究安全系统的基础计算基础。加密、签名等密码构造的安全性依赖于某些问题的计算难度。例如，如果有人发现了一种有效的算法来分解大整数，那么目前使用的许多公钥加密都会被破解。不幸的是，目前的技术水平是，我们无法证明这些问题是真正困难的，所以需要依赖于未经证实的假设。此外，这些猜想中的一小部分是许多（如果不是大多数）当前密码方案的基础，因此每个这样的猜想都是一个单点故障，其反驳可能会对我们系统的很大一部分产生严重后果。特别是，量子计算的进展威胁到了其中一些问题，并促使人们重新评估密码学的正确基础。本项目的目标是更好地理解和解决这些问题。具体地说，该项目研究加密方案，特别是公钥加密，这些方案基于与当前方案有质的不同的假设，因此更有可能在打破当前方案的技术或算法进步中生存下来。该项目获得了计算假设的新形式的证据，从而得出了一些保证，目前的计划是安全的。该项目还探讨了新的密码原语的假设，如软件混淆，这些假设更有理由考虑计算复杂性