Thwarting Statistical and Algebraic Attacks on Two Alternating Moduli Weak PRFs

Recent advances in MPC have sparked the emergence of numerous candidates for symmetric-key primitives tailored to specific applications. We will focus in particular on two families of weak pseudorandom functions, which are functions that exhibit random behavior to an adversary observing uniformly random plaintext-ciphertext pairs. Both families use cyclic matrices to reduce the size of the secret key. Unfortunately, this optimization has led to the development of statistical attacks (by Cheon et al.) and algebraic attacks (by Hu et al.). In this paper, we propose to modify the structure of these matrices by using companion matrices of irreducible polynomials rather than a shift of the coefficients. This modification does not change the key size but renders existing attacks (both statistical and algebraic) ineffective.