Cryptology ePrint Archive: Report 2017/537

Information-theoretic Indistinguishability via the Chi-squared Method

Wei Dai and Viet Tung Hoang and 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).

Category / Keywords: Symmetric cryptography, information-theoretic indistinguishability, provable security

Original Publication (in the same form): IACR-CRYPTO-2017

Date: received 5 Jun 2017, last revised 16 Jun 2017

Contact author: weidai at eng ucsd edu, tvhoang@cs fsu edu, tessaro@cs ucsb edu