CryptoDB
Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2024 |
| 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. |
BibTeX
@inproceedings{asiacrypt-2024-34629,
title={Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange},
publisher={Springer-Verlag},
author={Mihir Bellare and Doreen Riepel and Stefano Tessaro and Yizhao Zhang},
year=2024
}