Kai Hu
School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China; State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, China; Suzhou Research Institute, Shandong University, Suzhou, China

Gregor Leander
Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany

Håvard Raddum
Simula UiB, Bergen, Norway

Arne Sandrib
Department of Informatics, University of Bergen, Bergen, Norway

Aleksei Udovenko
SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg

Keywords: Cryptanalysis, Weak PRF, Alternating Moduli, DarkMatter

Abstract

In this work, we present new cryptanalytic attacks on recently proposed theory-inspired constructions of weak pseudorandom functions. We demonstrate attacks on several such designs and show that the original 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.