Paper 2017/537
Information-theoretic Indistinguishability via the Chi-squared Method
Wei Dai, 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).
Note: The proceeding version of this paper contains a glitch in the proof of the XOR construction, which is corrected in this version.
Metadata
- Available format(s)
-
PDF
- Publication info
- A minor revision of an IACR publication in CRYPTO 2017
- Keywords
- Symmetric cryptographyinformation-theoretic indistinguishabilityprovable security
- Contact author(s)
- hviettung @ gmail com
- History
- 2019-11-16: last of 5 revisions
- 2017-06-08: received
- See all versions
- Short URL
- https://ia.cr/2017/537
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/537,
author = {Wei Dai and Viet Tung Hoang and Stefano Tessaro},
title = {Information-theoretic Indistinguishability via the Chi-squared Method},
howpublished = {Cryptology ePrint Archive, Paper 2017/537},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/537}},
url = {https://eprint.iacr.org/2017/537}
}
