PROJECT
Quantum Security of Memory-Hard Functions
DOCTORATE CANDIDATE
Supervisors
Schaffner (UvA), Speelman (UvA), Jeffery (CWI), May (RUB), Huelsing (TU/e), Vredendaal (NXP).
Objectives
Investigate and establish the quantum security of memory-hard functions.
Expected Results
Framework of post-quantum security definitions and proofs for memory-hard functions, proofs of space, proofs of sequential work and verifiable delay functions.
Description
Memory-hard functions (MHFs) are moderately hard to evaluate when using a large amount of memory, but in case only a small amount of memory is available, they are slow to evaluate. Such functions are useful for the application of password hashing in order to prevent brute-force attacks when password hashes are stolen. MHFs can also be used to build proofs of space, proofs of sequential work or verifiable-delay functions. Partly fueled by the rise of cryptocurrencies, there has been a lot of (non-quantum) research in this area over the last few years. However, we are not aware of any post-quantum analysis of these primitives. The underlying principle for constructing MHFs are evaluations of hash functions, therefore, security proofs are usually given in the random-oracle model (ROM) where the hash functions are assumed to be perfectly random functions. It is a very natural and timely problem to investigate the post-quantum security of these constructions against quantum attackers. In practice, if fully specified hash functions such as SHA2 or SHA3 are used, a quantum attacker can run these functions in superposition on its quantum computer. Hence, it is imperative to revisit the security proofs in the quantum ROM (QROM) [ASIACRYPT, 41-69 (2011), EUROCRYPT, 552-586 (2018)].
Methodology
In this project, the Doctoral Candidate will define quantum security notions of MHFs as well as their derivatives. We then investigate which ROM proofs can be upgraded to the QROM.
Risks
The current QROM proof techniques might be insufficient to analyze all of the existing constructions. If the development of stronger tools turns out to be infeasible during the project period, the schemes will be modified (at the cost of efficiency) in order to be able to prove QROM security.
