Paper 2024/2055 Original: eprint.iacr.org/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 advances, 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 their 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. Our analysis reveals critical vulnerabilities, reducing the complexity of key recovery to $\mathcal{O}(2^{\lambda/2} \log_2 \lambda)$ for the Standard One-to-One wPRF and $\mathcal{O}(2^{0.84\lambda})$ for the Reversed Moduli variant -- both substantially below their claimed $\lambda$-bit security. We validate our findings through experimental evaluation, confirming alignment between predicted and observed attack complexities.