Paper 2019/1157

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.