CAREER: New Analytic Frontiers for Symmetric Cryptography

证明现实世界密码系统的安全性往往是具有挑战性的，因为这些遗留系统最初的设计并没有考虑可证明的安全目标，因此理论解释可能不能令人满意，未能捕捉到系统的真正优势。在其他一些情况下，可证明安全的设计对于渴望性能的应用程序来说过于昂贵，因此实践者不得不求助于启发式解决方案。这个项目朝着这个长期目标迈出了关键的一步，开发了对称密码学的新证明技术，以了解真实世界方案的确切安全性，并弥合了可证明安全设计和启发式设计之间的性能差距。该项目研究如何建立实用且可证明安全的格式保持加密方案，这是一种广泛用于加密信用卡号码的工具。该项目回顾了几个广泛使用的随机数生成器的安全分析，用新的分析方法加强了它们，以获得严格的界限。该项目研究如何为对称加密方案提供严格的时间-内存权衡。调查人员开发了一门独创的问题解决课程，在该课程中，学生通过试错、猜测、形成攻击计划并验证它们来体验整个发现过程。这门课程的目标是大四的本科生和一年级的研究生，让他们具备从事理论计算机科学研究的适当背景。其中一些材料被用于青年学者计划，这是一个面向佛罗里达州高中高年级学生的暑期科学和数学计划。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Justifying security of real-world cryptographic systems is often challenging because those legacy systems were not originally designed with a provable-security goal in mind, and consequently theoretical explanations may be unsatisfactory, failing to capture the real strength of the systems. In some other cases, provably secure designs are too expensive for performance-hungry applications, and practitioners therefore have to resort to heuristic solutions. This project takes a critical step towards this long-term goal by developing new proof techniques for symmetric cryptography to understand the exact security of real-world schemes, and bridge the performance gap between provable-security designs and heuristic ones. The project studies how to build practical and provably secure Format-Preserving Encryption schemes, a tool that is widely used for encrypting credit-card numbers. The project revisits the security analyses of several widely used Random Number Generators, strengthening them with new analytic methods to obtain tight bounds. The project investigates how to give tight time-memory trade-offs for symmetric encryption schemes. The investigator develops an original problem-solving course in which students experience the full discovery process with trial-and-error, guessing, forming attack plans, and validating them. This class targets senior undergraduate students and first-year graduate students, preparing them with a proper background for doing research in theoretical computer science. Some of this material is used in the Young Scholars Program, a summer science and math program for high-school seniors in Florida.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.