Paper 2018/169
Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the $\chi^2$ Method
Srimanta Bhattacharya and Mridul Nandi
Abstract
The construction $\mathsf{XORP}$ (bitwisexor of outputs of two independent $n$bit random permutations) has gained broad attention over the last two decades due to its high security. Very recently, Dai \textit{et al.} (CRYPTO'17), by using a method which they term the {\em Chisquared method} ($\chi^2$ method), have shown $n$bit security of $\mathsf{XORP}$ when the underlying random permutations are kept secret to the adversary. In this work, we consider the case where the underlying random permutations are publicly available to the adversary. The best known security of $\mathsf{XORP}$ in this security game (also known as {\em indifferentiable security}) is $\frac{2n}{3}$bit, due to Mennink \textit{et al.} (ACNS'15). Later, Lee (IEEEIT'17) proved a better $\frac{(k1)n}{k}$bit security for the general construction $\mathsf{XORP}[k]$ which returns the xor of $k$ ($\geq 2$) independent random permutations. However, the security was shown only for the cases where $k$ is an even integer. In this paper, we improve all these known bounds and prove full, {\em i.e.,} $n$bit (indifferentiable) security of $\mathsf{XORP}$ as well as $\mathsf{XORP}[k]$ for any $k$. Our main result is $n$bit security of $\mathsf{XORP}$, and we use the $\chi^2$ method to prove it.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in EUROCRYPT 2018
 Keywords
 random permutationindifferentiable security$\chi^2$ methodXOR constructionsimulator.
 Contact author(s)
 mail srimanta @ gmail com
 History
 20180211: received
 Short URL
 https://ia.cr/2018/169
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/169, author = {Srimanta Bhattacharya and Mridul Nandi}, title = {Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the $\chi^2$ Method}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/169}, year = {2018}, url = {https://eprint.iacr.org/2018/169} }