Paper 2019/249

Revisiting Variable Output Length XOR Pseudorandom Function

Srimanta Bhattacharya and Mridul Nandi

Abstract

Let $\sigma$ be some positive integer and $\mathcal{C}\subseteq \{(i,j):1\le i<j\le \sigma \}$. The theory behind finding a lower bound on the number of distinct blocks $P_1,\dots ,P_{\sigma }\in \{0,1{\}}^n$ satisfying a set of linear equations $\{P_i\oplus P_j=c_{i,j}:(i,j)\in \mathcal{C}\}$ for some $c_{i,j}\in \{0,1{\}}^n$, is called {\em mirror theory}. Patarin introduced the mirror theory and provided a proof for this. However, the proof, even for a special class of equations, is complex and contains several non-trivial gaps. As an application of mirror theory, $XORP[w]$ (known as XOR construction) which returns $(w-1)$-block output, is a {\em pseudorandom function} (PRF) for some parameter $w$, called {\em width}. The XOR construction can be seen as a basic structure of some encryption algorithms, e.g., the CENC encryption and the CHM authenticated encryption, proposed by Iwata in 2006. Due to potential application of $$ and the nontrivial gaps in the proof of mirror theory, an alternative simpler analysis of the PRF-security of $$ would be much desired. Recently (in Crypto 2017), Dai {\em et al.} have introduced a tool, called the $$ method, for analyzing PRF-security. Using this tool, the authors have provided a proof of the PRF-security of $$ without relying on the mirror theory. In this paper, we resolve the general case; we apply the $$ method to obtain {\em a simpler security proof of $$ for any $$}. For $$, we obtain {\em a tighter bound for a wider range of parameters} than that of Dai {\em et al.}. Moreover, we consider variable width construction $$ (in which the widths are chosen by the adversary adaptively), and also provide {\em variable output length pseudorandom function} (VOLPRF) security analysis for it. As an application of VOLPRF, we propose {\em an authenticated encryption which is a simple variant of CHM or AES-GCM and provides much higher security} than those at the cost of one extra blockcipher call for every message.