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

协作研究：SaTC：核心：媒介：分组密码的理论基础

• 批准号: 2154174
• 负责人: Stefano Tessaro
• 金额: $ 60万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154174&HistoricalAwards=false
• 关键词: Collaborative; Research; SaTC; CORE; Medium

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.

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

项目成果

Optimal Security for Keyed Hash Functions: Avoiding Time-Space Tradeoffs for Finding Collisions

键控哈希函数的最佳安全性：避免寻找冲突时的时空权衡

• 发表时间: 2023
• 期刊: Advances in Cryptology - EUROCRYPT 2023
• 作者: Freitag, Cody;Ghoshal, Ashrujit;Komargodski, Ilan
• 通讯作者: Komargodski, Ilan