TWC: Small: Complexity Assumptions for Cryptographic Schemes

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

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