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.