On the Number of Restricted Solutions to Constrained Systems and their Applications

Benoît Cogliati; Jordan Ethan; Ashwin Jha; Mridul Nandi; Abishanka Saha

Paper 2024/1163

On the Number of Restricted Solutions to Constrained Systems and their Applications

Benoît Cogliati

, Thales DIS France SAS, Meudon, France

Jordan Ethan

, CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Ashwin Jha

, Ruhr-Universität Bochum, Bochum, Germany

Mridul Nandi

, Indian Statistical Institute, Kolkata, India

Abishanka Saha

, Indian Statistical Institute, Kolkata, India

Abstract

In this paper, we formulate a special class of systems of linear equations over finite fields and derive lower bounds on the number of solutions adhering to some predefined restrictions. We then demonstrate the applications of these lower bounds to derive tight PRF security (up to $2^{3n/4}$ queries) for single-keyed variants of the Double-block Hash-then-Sum (DBHtS) paradigm, specifically PMAC+ and LightMAC+. Additionally, we show that the sum of $r$ independent copies of the Even-Mansour cipher is a secure PRF up to $2^{\frac{r}{r+1}n}$ queries.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: PMAC+LightMAC+Sum of Even-Mansour tight security
Contact author(s): benoit cogliati @ gmail com
jordan ethan @ cispa de
letterstoashwin @ gmail com
mridul nandi @ gmail com
sahaa 1993 @ gmail com
History: 2024-07-19: approved; 2024-07-18: received; See all versions
Short URL: https://ia.cr/2024/1163
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1163,
      author = {Benoît Cogliati and Jordan Ethan and Ashwin Jha and Mridul Nandi and Abishanka Saha},
      title = {On the Number of Restricted Solutions to Constrained Systems and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1163},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1163}},
      url = {https://eprint.iacr.org/2024/1163}
}