Paper 2024/2055

Zeroed Out: Cryptanalysis of Weak PRFs in Alternating Moduli

Abstract

The growing adoption of secure multi-party computation (MPC) has driven the development of efficient symmetric key primitives tailored for MPC. Recent advancements, such as the alternating moduli paradigm, have shown promise but leave room for cryptographic and practical improvements. In this paper, we analyze a family of weak pseudorandom functions (wPRF) proposed at Crypto 2024, focusing on the One-to-One parameter sets. We demonstrate that these configurations fail to achieve their intended one-to-one mappings and exploit this observation to develop an efficient key recovery attack. The attacks reveal significant vulnerabilities, reducing the complexity of key recovery to O(2^(λ/2) log_2 (λ)) for the Standard One-to-One wPRF and O(2^(0.84λ)) for the Reversed Moduli variant– both substantially below their claimed λ-bit security. We validate our findings through experimental evaluations, confirming alignment between predicted and observed attack complexities.