### A Note on the Chi-square Method : A Tool for Proving Cryptographic Security

Srimanta Bhattacharya and Mridul Nandi

##### Abstract

In CRYPTO 2017, Dai, Hoang, and Tessaro introduced the {\em Chi-square method} ($\chi^2$ method) which can be applied to obtain an upper bound on the statistical distance between two joint probability distributions. The authors applied this method to prove the {\em pseudorandom function security} (PRF-security) of sum of two random permutations. In this work, we revisit their proof and find a non-trivial gap in the proof and describe how to plug this gap as well; this has already been done by Dai {\em et al.} in the revised version of their CRYPTO 2017 paper. A complete, correct, and transparent proof of the full security of the sum of two random permutations construction is much desirable, especially due to its importance and two decades old legacy. The proposed $\chi^2$ method seems to have potential for application to similar problems, where a similar gap may creep into a proof. These considerations motivate us to communicate our observation in a formal way.\par On the positive side, we provide a very simple proof of the PRF-security of the {\em truncated random permutation} construction (a method to construct PRF from a random permutation) using the $\chi^2$ method. We note that a proof of the PRF-security due to Stam is already known for this construction in a purely statistical context. However, the use of the $\chi^2$ method makes the proof much simpler.

Note: This is the revised version of the article that was published in the journal Cryptography and Communications. Here, we have omitted Section 4 of the journal version and included a proof of Lemma 1 which was stated as an assumption in the journal version; the proof is similar but not same as the proof given by Dai et al. in the revised version of their Crypto 2017 paper. Also, we have added Section 5 where we have listed some recent applications of the $\chi^2$-method.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. MINOR revision.Cryptography and Communications
DOI
10.1007/s12095-017-0276-z
Keywords
Random permutationpseudorandom functiontotal variation distancePinsker’s inequalitysum of random permutationtruncated random permutation.
Contact author(s)
mail srimanta @ gmail com
mridul nandi @ gmail com
History
2020-01-01: revised
See all versions
Short URL
https://ia.cr/2019/1157

CC BY

BibTeX

@misc{cryptoeprint:2019/1157,
author = {Srimanta Bhattacharya and Mridul Nandi},
title = {A Note on the Chi-square Method : A Tool for Proving Cryptographic Security},
howpublished = {Cryptology ePrint Archive, Paper 2019/1157},
year = {2019},
doi = {10.1007/s12095-017-0276-z},
note = {\url{https://eprint.iacr.org/2019/1157}},
url = {https://eprint.iacr.org/2019/1157}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.