Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange

Mihir Bellare; Doreen Riepel; Stefano Tessaro; Yizhao Zhang

Paper 2024/1258

Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange

Mihir Bellare

, University of California, San Diego

Doreen Riepel

, University of California, San Diego

Stefano Tessaro

, University of Washington

Yizhao Zhang, University of California, San Diego

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: A major revision of an IACR publication in ASIACRYPT 2024
Keywords: Tight proofs signatures authenticated key exchange KEMs
Contact author(s): mbellare @ ucsd edu
driepel @ ucsd edu
tessaro @ cs washington edu
yiz191 @ ucsd edu
History: 2024-10-07: revised; 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}
}