**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.

**Category / Keywords: **secret-key cryptography / Random permutation, pseudorandom function, total variation distance, Pinsker’s inequality, sum of random permutation, truncated random permutation.

**Original Publication**** (with minor differences): **Cryptography and Communications
**DOI: **10.1007/s12095-017-0276-z

**Date: **received 5 Oct 2019

**Contact author: **mail srimanta at gmail com, mridul nandi@gmail com

**Available format(s): **PDF | BibTeX Citation

**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.

**Version: **20191007:082458 (All versions of this report)

**Short URL: **ia.cr/2019/1157

[ Cryptology ePrint archive ]