Paper 2019/1157

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

Srimanta Bhattacharya and Mridul Nandi


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)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Cryptography and Communications
Random permutationpseudorandom functiontotal variation distancePinsker’s inequalitysum of random permutationtruncated random permutation.
Contact author(s)
mail srimanta @ gmail com
mridul nandi @ gmail com
2020-01-01: revised
2019-10-07: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.