International Association for Cryptologic Research

International Association
for Cryptologic Research


Improved Multi-User Security Using the Squared-Ratio Method

Yu Long Chen , imec-COSIC, KU Leuven, Belgium and NIST, USA
Wonseok Choi , Purdue University, West Lafayette, IN, US
Changmin Lee , Korea Institute for Advanced Study, Seoul
DOI: 10.1007/978-3-031-38545-2_23 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Proving security bounds in contexts with a large number of users is one of the central problems in symmetric-key cryptography today. This paper introduces a new method for information-theoretic multi-user security proofs, called ``the Squared-Ratio method''. At its core, the method requires the expectation of the square of the ratio of observing the so-called good transcripts (from Patarin's H-coefficient technique) in the real and the ideal world. Central to the method is the observation that for information-theoretic adversaries, the KL-divergence for the multi-user security bound can be written as a summation of the KL-divergence of every single user. We showcase the Squared-Ratio method on three examples: the Xor of two Permutations by Bellare et al. (EUROCRYPT '98) and Hall et al. (CRYPTO '98), the Encrypted Davies-Mayer by Cogliati and Seurin (CRYPTO '16), and the two permutation variant of the nEHtM MAC algorithm by Dutta et al. (EUROCRYPT '19). With this new tool, we provide improved bounds for the multi-user security of these constructions. Our approach is modular in the sense that the multi-user security can be obtained directly from single-user results.
  title={Improved Multi-User Security Using the Squared-Ratio Method},
  author={Yu Long Chen and Wonseok Choi and Changmin Lee},