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

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.