Cryptanalysis of Two Alternating Moduli Weak PRFs

[en] In this work, we present new cryptanalytic attacks on recently proposed, theory-inspired constructions of weak pseudorandom functions (weak-PRFs). We demonstrate attacks on several such designs, showing that the initial security arguments require significant refinement. Methodologically, our approach relies on novel observations about the structure of cyclic matrices, applications of Wagner’s generalized birthday technique, and conversion into polynomial systems over F3. These findings highlight the need for a more careful analysis of those weak-PRF candidates.

Disciplines :

Computer science

Author, co-author :

Hu, Kai

Leander, Gregor

Raddum, Håvard

Sandrib, Arne

UDOVENKO, Aleksei ; University of Luxembourg

External co-authors :

yes

Language :

English

Title :

Cryptanalysis of Two Alternating Moduli Weak PRFs

Publication date :

16 March 2026

Journal title :

IACR Transactions on Symmetric Cryptology

eISSN :

2519-173X

Publisher :

Universitatsbibliothek der Ruhr-Universitat Bochum

Volume :

2026

Issue :

Pages :

95-118

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://tosc.iacr.org/index.php/ToSC/article/view/12780

FnR Project :

PQseal - C24/IS/18978392 (PI Udovenko)

Funders :

FNR - Fonds National de la Recherche

Funding number :

C24/IS/18978392; 2025NCSF02007; 2025HWYQ-025; BK20240420; 101097056

Funding text :

This work started at the ALPSY 2025 workshop organized by Arnab Roy and ChristianRechberger at the Obergurgl center of the University of Innsbruck. We are grateful for theorganizers for providing a great opportunity for joint research. Kai Hu is supported bythe National Cryptologic Science Fund of China (2025NCSF02007), the Natural ScienceFoundation of Shandong Province (2025HWYQ-025), and the Natural Science Foundationof Jiangsu Province (BK20240420). This work was (in part) supported by the European Re-search Council (ERC) project 101097056 (SYMTRUST). Aleksei Udovenko was supportedby Luxembourg’s FNR project PQseal (C24/IS/18978392).

Available on ORBilu :

since 16 March 2026

Statistics

Number of views

32 (0 by Unilu)

Number of downloads

7 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

[ABG+ 14] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC0◦ MOD2. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 251–260. ACM, 2014. doi:10.1145/2554797.2554821.95
[APRR24] Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, and Peter Rindal. Improved Alternating-Moduli PRFs and Post-quantum Signatures. In Advances in Cryptology-CRYPTO 2024-44th Annual International Cryptol-ogy Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VIII, volume 14927 of Lecture Notes in Computer Science, pages 274–308. Springer, 2024. doi:10.1007/978-3-031-68397-8_9.96
[AR25] Irati Manterola Ayala and Håvard Raddum. Zeroed Out: Cryptanalysis of Weak PRFs in Alternating Moduli. IACR Trans. Symmetric Cryptol., 2025(2):1–15, 2025. doi:10.46586/TOSC.V2025.I2.1-15.96
[ARS+ 15] Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology-EUROCRYPT 2015-34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 430–454. Springer, 2015. doi:10.1007/978-3-662-46800-5_17.96
[BCPR25] Christina Boura, Geoffroy Couteau, Léo Perrin, and Yann Rotella. SoK: On Shallow Weak PRFs A Common Symmetric Building Block for MPC Protocols. IACR Trans. Symmetric Cryptol., 2025(3):289–336, 2025. doi: 10.46586/TOSC.V2025.I3.289-336.96
[BIP+ 18a] Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. Exploring crypto dark matter: New simple PRF candidates and their ap-plications. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, pages 699–729. Springer, Cham, November 2018. doi:10.1007/978-3-030-03810-6_25. 95, 96, 97, 98, 99, 113, 115, 116
[BIP+ 18b] Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. Exploring crypto dark matter: New simple PRF candidates and their ap-plications. Cryptology ePrint Archive, Report 2018/1218, 2018. URL: https://eprint.iacr.org/2018/1218. 96
[BKW00] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. In 32nd Annual ACM Symposium on Theory of Computing, pages 435–440, Portland, OR, USA, May 21–23, 2000. ACM Press. doi:10.1145/335305.335355. 97, 113
[CCKK21] Jung Hee Cheon, Wonhee Cho, Jeong Han Kim, and Jiseung Kim. Adventures in crypto dark matter: Attacks and fixes for weak pseudorandom functions. In Juan Garay, editor, PKC 2021, Part II, volume 12711 of LNCS, pages 739–760. Springer, Cham, May 2021. doi:10.1007/978-3-030-75248-4_26. 96, 97, 99, 113
[DEG+ 18] Christoph Dobraunig, Maria Eichlseder, Lorenzo Grassi, Virginie Lallemand, Gregor Leander, Eik List, Florian Mendel, and Christian Rechberger. Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit. In Advances in Cryptology-CRYPTO 2018-38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, volume 10991 of Lecture Notes in Computer Science, pages 662–692. Springer, 2018. doi: 10.1007/978-3-319-96884-1_22. 96
[DGH+ 21a] Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmetric cryptography from alternating moduli: Candidates, protocols, and applications. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 517–547, Virtual Event, August 2021. Springer, Cham. doi: 10.1007/978-3-030-84259-8_18. 95, 96, 97, 98, 99, 100, 106, 116
[DGH+ 21b] Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmetric cryptography from alternating moduli: Candidates, protocols, and applications. Cryptology ePrint Archive, Report 2021/885, 2021. URL: https://eprint.iacr.org/2021/885. 96
[EKM17] Andre Esser, Robert Kübler, and Alexander May. LPN decoded. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part II, volume 10402 of Lecture Notes in Computer Science, pages 486–514, Santa Barbara, CA, USA, August 20–24, 2017. Springer, Cham, Switzerland. doi:10.1007/978-3-319-63715-0_17. 113, 115
[JMN23] Thomas Johansson, Willi Meier, and Vu Nguyen. Differential cryptanalysis of Mod-2/Mod-3 constructions of binary weak PRFs. In IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023, pages 477–482. IEEE, 2023. doi:10.1109/ISIT54713.2023.10206853.96, 97
[KGH+ 25] Hu Kai, Leander Gregor, Raddum Håvard, Sandrib Arne, and Udovenko Aleksei. Cryptanalysis of (2,3)-wPRF: Supporting code, September 2025. doi:10.5281/zenodo.18677322.97
[LM90] Xuejia Lai and James L. Massey. A proposal for a new block encryption standard. In Ivan Damgård, editor, Advances in Cryptology-EUROCRYPT ’90, Workshop on the Theory and Application of of Cryptographic Techniques, Aarhus, Denmark, May 21-24, 1990, Proceedings, volume 473 of Lecture Notes in Computer Science, pages 389–404. Springer, 1990. doi:10.1007/3-540-46877-3_35. 95
[Str69] Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 1969. 114
[SW26] Antoine Sidem and Qingju Wang. General key recovery attack on pointwise-keyed functions. In Goichiro Hanaoka and Bo-Yin Yang, editors, Advances in Cryptology – ASIACRYPT 2025, pages 131–154, Singapore, 2026. Springer Nature Singapore. doi:10.1007/978-981-95-5018-0_5. 96
[Wag02] David Wagner. A generalized birthday problem. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 288–303. Springer, Berlin, Heidelberg, August 2002. doi:10.1007/3-540-45708-9_19. 97, 113