Collaborative Research: SaTC: CORE: Medium: Theoretical Foundations of Block Ciphers

分组密码(如高级加密标准(AES))是基本的加密算法，在当今使用的大多数安全系统中充当基本构建块。作为传输层安全(TLS)等安全通信协议的组成部分，仅使用AES来保护很大一部分互联网流量的机密性。因此，必须尽可能地评估现有的和新的分组密码设计的安全性。按照密码学家在过去40年中开发的一个成熟的范例，安全验证的黄金标准将是基于一些经过充分研究的计算问题的猜测难度来证明安全性。然而，由于极端的效率要求，实用的分组密码避开了这一经典的可证明安全范例。相反，信心依赖于几十年的密码分析和无法找到具体的攻击。该项目的主要目标是缩小可证明安全和密码分析之间的现有差距，特别是针对有限类别的攻击开发安全证明，并最终基于该项目的新发现设计新的算法和范例。最初的重点将是针对一类统计攻击的安全性证明，这些攻击试图发现少量分组密码输出中的非随机属性。然后，第二个推力将开发出针对代数攻击证明安全性的技术。最后，该项目将启动对分组密码的重要组成部分的研究，特别是引入一种新的密钥调度理论。这种处理既包括替换-置换网络等经典设计，也包括加法-旋转-异或(ARX)密码等研究较少的设计。该项目的更广泛影响将包括一个旨在弥合理论密码学和密码分析之间差距的研讨会，以及一个本科生研究部分。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Block ciphers, such as the Advanced Encryption Standard (AES), are fundamental cryptographic algorithms which act as basic building blocks in most secure systems in use today. AES alone is used to protect the confidentiality of a large fraction of Internet traffic as a component of secure-communication protocols like Transport Layer Security (TLS). It is therefore imperative to assess the security of existing and new block cipher designs as far as possible. Following a well-established paradigm developed by cryptographers over the last four decades, the gold standard for security validation would be a proof of security based on the conjectured hardness of some well-studied computational problems. However, due to extreme efficiency demands, practical block ciphers evade this classical paradigm of provable security. Instead, confidence relies on decades of cryptanalysis and an inability to find concrete attacks.The main aim of this project is to narrow the existing gap between provable security and cryptanalysis, developing in particular security proofs against limited classes of attacks, and eventually designing new algorithms and paradigms based on the new findings of this project. The initial focus will be on proofs of security against classes of statistical attacks which attempt to uncover non-random properties in a small number of block-cipher outputs. A second thrust will then develop techniques to prove security against algebraic attacks. Finally, this project will initiate the study of important components of block ciphers which have not been studied rigorously so far, introducing in particular a new theory of key schedules. The treatment will cover both classical designs such as substitution-permutation networks, as well as less studied ones such as Add-Rotate-XOR (ARX) ciphers. The broader impacts of this project will include a workshop aimed at bridging the gap between theoretical cryptography and cryptanalysis, as well as an undergraduate research component.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.