Paper 2024/1163 Original: eprint.iacr.org/2024/1163 ↗

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

Abstract

In this paper, we formulate a special class of systems of linear equations over finite fields that appears naturally in the provable security analysis of several MAC and PRF modes of operation. We derive lower bounds on the number of solutions for such systems adhering to some predefined restrictions, and apply these lower bounds to derive tight PRF security for several constructions. We show security up to $2^{3n/4}$ queries for the single-keyed variant of the Double-block Hash-then-Sum (DBHtS) construction, called 1k-DBHtS, under appropriate assumptions on the underlying hash function. We show that the single-key variants of PMAC+ and LightMAC+, called 1k-PMAC+ and 1k-LightMAC+ achieve the required hash function properties, and thus, achieve $3n/4$-bit security. 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.