Welcome to the resource topic for 2019/249
Title:
Revisiting Variable Output Length XOR Pseudorandom Function
Authors: Srimanta Bhattacharya, 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.
ePrint: https://eprint.iacr.org/2019/249
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .