Hash Functions in a Post-Quantum World

This thesis is dedicated to the study of various applications of hash functions in cryptography. The main contribution of this thesis is an analysis of various hash-based signature schemes. Foremost, we achieve a tight proof of security for SPHINCS+, also known as SLH-DSA, which has been selected by NIST as a standard for post-quantum signature schemes. Furthermore, an improved variant of SPHINCS+ called SPHINCS+C is proposed, offering improved signature sizes and verification times. The practical application of hash-based signature schemes is examined through the example of the Ethereum protocol, with a specific goal of achieving efficient aggregation of multiple signatures. For this case, a modified version of the XMSS signature scheme is developed, incorporating novel techniques from SPHINCS+C.A secondary contribution of this thesis lies in the examination of hash function properties, where different properties utilized in the discussed schemes are investigated. We establish bounds for their generic security within the quantum random oracle model (QROM). Furthermore, we advance the techniques for analyzing specific types of hash function properties by introducing new tools for working with quantumly accessible random oracles. These enhanced techniques enable us to derive improved bounds for the security properties of hash functions, thus allowing better parameter choices. As a final contribution, this thesis delves into the Fujisaki–Okamoto transform, a method for constructing secure key encapsulation mechanisms from probabilistic public key encryption schemes, which relies on hash functions. The transform is categorized into two types based on how incorrect ciphertexts are handled: implicit and explicit rejection. A comprehensive analysis of these two types reveals that they are nearly equivalent, providing valuable insights into the underlying mechanisms. Overall, this thesis presents an in-depth exploration of different uses of hash functions in the context of post-quantum cryptography, shedding light on their applications, properties, and potential improvements.