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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2018
DOI
10.13154/tosc.v2018.i1.314-335
Keywords
PRFPRPchi-squared methodmirror theoryCENC.
Contact author(s)
mail srimanta @ gmail com
mridul nandi @ gmail com
History
2019-02-28: received
Short URL
https://ia.cr/2019/249
License
Creative Commons Attribution
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.314-335},
      note = {\url{https://eprint.iacr.org/2019/249}},
      url = {https://eprint.iacr.org/2019/249}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.