Paper 2023/153

Almost Tight Multi-User Security under Adaptive Corruptions & Leakages in the Standard Model

Shuai Han, Shanghai Jiao Tong University
Shengli Liu, Shanghai Jiao Tong University
Dawu Gu, Shanghai Jiao Tong University
Abstract

In this paper, we consider tight multi-user security under adaptive corruptions, where the adversary can adaptively corrupt some users and obtain their secret keys. We propose generic constructions for a bunch of primitives, and the instantiations from the matrix decision Diffie-Hellman (MDDH) assumptions yield the following schemes: (1) the first digital signature (SIG) scheme achieving almost tight strong EUF-CMA security in the multi-user setting with adaptive corruptions in the standard model; (2) the first public-key encryption (PKE) scheme achieving almost tight IND-CCA security in the multi-user multi-challenge setting with adaptive corruptions in the standard model; (3) the first signcryption (SC) scheme achieving almost tight privacy and authenticity under CCA attacks in the multi-user multi-challenge setting with adaptive corruptions in the standard model. As byproducts, our SIG and SC naturally derive the first strongly secure message authentication code (MAC) and the first authenticated encryption (AE) schemes achieving almost tight multi-user security under adaptive corruptions in the standard model. We further optimize constructions of SC, MAC and AE to admit better efficiency. Furthermore, we consider key leakages besides corruptions, as a natural strengthening of tight multi-user security under adaptive corruptions. This security considers a more natural and more complete "all-or-part-or-nothing" setting, where secret keys of users are either fully exposed to adversary ("all"), or completely hidden to adversary ("nothing"), or partially leaked to adversary ("part"), and it protects the uncorrupted users even with bounded key leakages. All our schemes additionally support bounded key leakages and enjoy full compactness. This yields the first SIG, PKE, SC, MAC, AE schemes achieving almost tight multi-user security under both adaptive corruptions and leakages.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Keywords
public-key encryptiondigital signaturetightnessmulti-user securityleakage-resilience
Contact author(s)
dalen17 @ sjtu edu cn
slliu @ sjtu edu cn
dwgu @ sjtu edu cn
History
2023-02-15: approved
2023-02-09: received
See all versions
Short URL
https://ia.cr/2023/153
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/153,
      author = {Shuai Han and Shengli Liu and Dawu Gu},
      title = {Almost Tight Multi-User Security under Adaptive Corruptions & Leakages in the Standard Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/153},
      year = {2023},
      url = {https://eprint.iacr.org/2023/153}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.