IACR News item: 01 December 2025
Davide Li Calsi, Dominique Schröder, Julian Thomas
ePrint Report
A message authentication code (MAC) ensures authenticity and integrity in symmetric-key settings. The Carter–Wegman–Shoup (CWS) paradigm establishes that MACs for arbitrary-length messages can be built in a black-box way using a single call to a pseudorandom function (PRF) on a random input. More than a decade ago, Dodis, Kiltz, Pietrzak, and Wichs left open whether weak pseudorandom functions (wPRFs) would suffice in this construction.
This work establishes tight upper and lower bounds that precisely characterize the minimal computational assumptions needed for the security of the CWS paradigm. On the negative side, we prove that weak PRFs are insufficient to instantiate the CWS paradigm. On the positive side, we introduce a new primitive, the 1-adaptive weak pseudorandom function (1-awPRF), which guarantees pseudorandomness for polynomially many non-adaptive queries followed by one adaptive query. We show that 1-awPRFs are sufficient to secure CWS in a black-box manner.
Finally, we construct 1-adaptive weak pseudorandom functions in a black-box way from standard cryptographic assumptions, using a new randomized design paradigm that treats randomization as a fundamental structural element. Instantiating our generic construction under the Decisional Diffie Hellman and Learning with Errors assumptions yields concrete and efficient realizations. These lead to more efficient MAC schemes and illustrate how weak and abstract building blocks can be transformed into stronger and practically useful cryptographic constructions.
This work establishes tight upper and lower bounds that precisely characterize the minimal computational assumptions needed for the security of the CWS paradigm. On the negative side, we prove that weak PRFs are insufficient to instantiate the CWS paradigm. On the positive side, we introduce a new primitive, the 1-adaptive weak pseudorandom function (1-awPRF), which guarantees pseudorandomness for polynomially many non-adaptive queries followed by one adaptive query. We show that 1-awPRFs are sufficient to secure CWS in a black-box manner.
Finally, we construct 1-adaptive weak pseudorandom functions in a black-box way from standard cryptographic assumptions, using a new randomized design paradigm that treats randomization as a fundamental structural element. Instantiating our generic construction under the Decisional Diffie Hellman and Learning with Errors assumptions yields concrete and efficient realizations. These lead to more efficient MAC schemes and illustrate how weak and abstract building blocks can be transformed into stronger and practically useful cryptographic constructions.
Additional news items may be found on the IACR news page.