Welcome to the resource topic for 2017/537
Title:
Information-theoretic Indistinguishability via the Chi-squared Method
Authors: Wei Dai, Viet Tung Hoang, Stefano Tessaro
Abstract:Proving tight bounds on information-theoretic indistinguishability is a central problem in symmetric cryptography. This paper introduces a new method for information-theoretic indistinguishability proofs, called ``the chi-squared method’'. At its core, the method requires upper-bounds on the so-called \chi^2 divergence (due to Neyman and Pearson) between the output distributions of two systems being queries. The method morally resembles, yet also considerably simplifies, a previous approach proposed by Bellare and Impagliazzo (ePrint, 1999), while at the same time increasing its expressiveness and delivering tighter bounds. We showcase the chi-squared method on some examples. In particular: (1) We prove an optimal bound of q/2^n for the XOR of two permutations, and our proof considerably simplifies previous approaches using the H-coefficient method, (2) we provide improved bounds for the recently proposed encrypted Davies-Meyer PRF construction by Cogliati and Seurin (CRYPTO '16), and (3) we give a tighter bound for the Swap-or-not cipher by Hoang, Morris, and Rogaway (CRYPTO '12).
ePrint: https://eprint.iacr.org/2017/537
Talk: https://www.youtube.com/watch?v=YHeqvm94OTc
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 .