SaTC: CORE: Small: Memory-hard Cryptography

密码学提供了保证数据机密性和完整性的基本工具。因此，它在保护我们的数字基础设施和执行个人隐私权方面发挥着关键作用。然而，安全密码技术的发展是困难的，容易出错，因为未知的攻击策略需要考虑在内。为了克服这一点，现代密码学倡导可证明安全的范式，其中威胁模型使用数学语言精确地形式化，并且密码系统的安全性在这些模型中得到证明。该项目旨在开发一种更好的量化方法来证明安全性。该项目的研究使人们更好地理解了正在使用的加密技术，从而有助于更安全地部署现有的加密解决方案，并支持未来的标准化进程。该项目的教育部分包括开发一个全面的计划，以教育本科生正确使用密码学，并使用密码学作为推广的工具。 该项目开发了更好的理论来证明攻击者所需的时间和内存组合的严格下限。这使我们能够更好地比较加密解决方案，并有利于那些在相同的时间资源，需要最大的内存量，以便被妥协。具体而言，该项目在沿着两个不同的方面做出贡献。第一个方向扩展了记忆困难函数的理论，记忆困难函数是相对于时间和记忆资源的某种组合来说比较难计算的函数。该项目介绍了更好的硬度指标，以及新的安全目标的内存硬功能，并分析新的结构。第二个方向重新审视了对称密码学中各种方案的安全性，并在将方案的一些底层组件建模为理想的情况下，在时间和内存存储方面提供了对手破坏它们的复杂性的下限。

Cryptography provides the basic tools to guarantee confidentiality and integrity of data. It hence plays a pivotal role in securing our digital infrastructure, and in enforcing the right for privacy of individuals. The development of secure cryptographic techniques is however difficult and error-prone, as unknown attack strategies need to be taken into account. To overcome this, modern cryptography advocates the paradigm of provable security, where threat models are precisely formalized using the language of mathematics, and the security of cryptosystems is proved within these models. This project aims to develop a better quantitative approach to provable security. The research of this project yields a better understanding of in-use cryptography, therefore contributing to the safer deployment of existing cryptographic solutions, as well as the support of future standardization processes. The educational component of this project includes the development of a comprehensive program to educate undergraduate students in the proper use of cryptography, and to use cryptography as a vehicle for outreach. This project develops better theory to prove rigorous lower bounds on the combination of time and memory needed by the attacker. This allows us to better compare cryptographic solutions, and to favor those which, for equal time resources, require the largest amount of memory in order to be compromised. Concretely, this project contributes along two different fronts. The first direction extends the theory of memory-hard functions, which are functions that are moderately hard to compute with respect to some combination of time and memory resources. This project introduces better hardness metrics as well as new security targets for memory-hard functions, and analyze new constructions. The second direction revisits the security of various schemes in symmetric cryptography, and provides lower bounds on the complexity of adversaries breaking them both in terms of time and memory storage, in the setting where some underlying component of scheme is modeled as ideal.