Paper 2019/1157

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

Srimanta Bhattacharya and Mridul Nandi

Abstract

Very recently (in CRYPTO 2017) Dai, Hoang, and Tessaro have introduced the Chi-square method ($\chi^2$ method) which can be ap- plied to obtain an upper bound on the statistical distance between two joint probability distributions. The authors have applied this method to prove the 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. We plug this gap for two specific cases and state the general case as an assumption whose proof is essential for the completeness of the proof by Dai et al.. A complete, correct, and trans- parent 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. On the positive side, we provide a very simple proof of the PRF-security of the truncated random permutation construction (a method to con- struct 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 same article that was published in the journal Cryptography and Communications. Here we have only fixed typos that were present in couple of our results.