Welcome to the resource topic for 2019/1157
Title:
A Note on the Chi-square Method : A Tool for Proving Cryptographic Security
Authors: Srimanta Bhattacharya, 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.
ePrint: https://eprint.iacr.org/2019/1157
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .