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 \leq i < j \leq \sigma \}$. The theory behind finding a lower bound on the number of distinct blocks $P_1, \ldots, 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 $XORP[w]$ and the nontrivial gaps in the proof of mirror theory, an alternative simpler analysis of the PRF-security of $XORP[w]$ would be much desired. Recently (in Crypto 2017), Dai {\em et al.} have introduced a tool, called the $\chi^2$ method, for analyzing PRF-security. Using this tool, the authors have provided a proof of the PRF-security of $XORP[2]$ without relying on the mirror theory. In this paper, we resolve the general case; we apply the $\chi^2$ method to obtain {\em a simpler security proof of $XORP[w]$ for any $w \geq 2$}. For $w =2$, 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 $XORP[*]$ (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.