Paper 2024/1258
Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange
Abstract
In the multi-user with corruptions (muc) setting there are $n\geq 1$ users, and the goal is to prove that, even in the face of an adversary that adaptively corrupts users to expose their keys, un-corrupted users retain security. This can be considered for many primitives including signatures and encryption. Proofs of muc security, while possible, generally suffer a factor n loss in tightness, which can be large. This paper gives new proofs where this factor is reduced to the number c of corruptions, which in practice is much smaller than n. We refer to this as corruption-parametrized muc (cp-muc) security. We give a general result showing it for a class of games that we call local. We apply this to get cp-muc security for signature schemes (including ones in standards and in TLS 1.3) and some forms of public-key and symmetric encryption. Then we give dedicated cp-muc security proofs for some important schemes whose underlying games are not local, including the Hashed ElGamal and Fujisaki-Okamoto KEMs and authenticated key exchange. Finally, we give negative results to show optimality of our bounds.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Tight proofssignaturesauthenticated key exchangeKEMs
- Contact author(s)
-
mbellare @ ucsd edu
driepel @ ucsd edu
tessaro @ cs washington edu
yiz191 @ ucsd edu - History
- 2024-08-09: approved
- 2024-08-08: received
- See all versions
- Short URL
- https://ia.cr/2024/1258
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1258, author = {Mihir Bellare and Doreen Riepel and Stefano Tessaro and Yizhao Zhang}, title = {Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1258}, year = {2024}, url = {https://eprint.iacr.org/2024/1258} }