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 nontrivial gaps. As an application of mirror theory, $XORP[w]$ (known as XOR construction) which returns $(w1)$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 PRFsecurity 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 PRFsecurity. Using this tool, the authors have provided a proof of the PRFsecurity 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 AESGCM and provides much higher security} than those at the cost of one extra blockcipher call for every message.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in FSE 2018
 DOI
 10.13154/tosc.v2018.i1.314335
 Keywords
 PRFPRPchisquared methodmirror theoryCENC.
 Contact author(s)

mail srimanta @ gmail com
mridul nandi @ gmail com  History
 20190228: received
 Short URL
 https://ia.cr/2019/249
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/249, author = {Srimanta Bhattacharya and Mridul Nandi}, title = {Revisiting Variable Output Length XOR Pseudorandom Function}, howpublished = {Cryptology ePrint Archive, Paper 2019/249}, year = {2019}, doi = {10.13154/tosc.v2018.i1.314335}, note = {\url{https://eprint.iacr.org/2019/249}}, url = {https://eprint.iacr.org/2019/249} }