This thesis develops a provable security framework for keyed hash functions built from public functions, motivated by the compression layer of Farfalle. It introduces the Key-Then-Hash (KTH) framework, in which a secret key is combined with message blocks before applying an unkeyed public primitive. Two variants, Serial and Parallel KTH, are formalized and analyzed. Tight universality bounds are derived for permutation-based constructions, with the Parallel variant shown to achieve security at least as strong as, and often better than, the Serial variant. The framework is then generalized from public permutations to non-invertible public functions, enabling arithmetic-based universal hashing and supporting the Multi-265 design. The thesis further studies KTH security under stronger attack models. It proves that, because of offset invariance, existential forgery and partial key recovery have equivalent security for efficient attackers, eliminating the conventional distinction between weak and strong keys in this setting. Finally, it introduces Catch Attacks and Group Attacks, generic multi-query strategies that can achieve a quadratic increase in adversarial advantage and, under certain conditions, attain the proven security bounds.
Jonathan Fuchs is a researcher in symmetric cryptography and a PhD candidate at Radboud University, working within the ESCADA research team under the supervision of Prof. Joan Daemen. He studied computer science through the Etgar program at the University of Haifa and later continued his studies at the Université libre de Bruxelles, where he completed his Master’s degree in 2019. During his Master’s studies, he specialized in cryptography and completed an internship with the Keccak Team at STMicroelectronics. His doctoral research focuses on the provable security of keyed hash functions constructed from public permutations and public functions, with particular emphasis on Key-Then-Hash constructions, universal hashing, key-recovery attacks, and multi-query cryptanalysis. His research has contributed to publications presented at CRYPTO 2023 and AFRICACRYPT 2023, including work on permutation-based keyed hashing and universal hashing based on field multiplication and near-MDS matrices. He also authored work on forgery, key recovery, and multi-query attacks.