Paper 2023/871
Improved Multi-User Security Using the Squared-Ratio Method
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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A major revision of an IACR publication in CRYPTO 2023
- Keywords
- symmetric-key cryptographyprovable securitymulti-user securitypseudorandom function
- Contact author(s)
-
yulong chen @ kuleuven be
wonseok @ purdue edu
changminlee @ kias re kr - History
- 2023-07-01: revised
- 2023-06-07: received
- See all versions
- Short URL
- https://ia.cr/2023/871
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/871,
author = {Yu Long Chen and Wonseok Choi and Changmin Lee},
title = {Improved Multi-User Security Using the Squared-Ratio Method},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/871},
year = {2023},
url = {https://eprint.iacr.org/2023/871}
}
