Paper 2023/1230

Almost Tight Multi-User Security under Adaptive Corruptions from LWE in the Standard Model

Shuai Han, Shanghai Jiao Tong University
Shengli Liu, Shanghai Jiao Tong University
Zhedong Wang, Shanghai Jiao Tong University
Dawu Gu, Shanghai Jiao Tong University

In this work, we construct the first digital signature (SIG) and public-key encryption (PKE) schemes with almost tight multi-user security under adaptive corruptions based on the learning-with-errors (LWE) assumption in the standard model. Our PKE scheme achieves almost tight IND-CCA security and our SIG scheme achieves almost tight strong EUF-CMA security, both in the multi-user setting with adaptive corruptions. The security loss is quadratic in the security parameter, and independent of the number of users, signatures or ciphertexts. Previously, such schemes were only known to exist under number-theoretic assumptions or in classical random oracle model, thus vulnerable to quantum adversaries. To obtain our schemes from LWE, we propose new frameworks for constructing SIG and PKE with a core technical tool named probabilistic quasi-adaptive hash proof system (pr-QA-HPS). As a new variant of HPS, our pr-QA-HPS provides probabilistic public and private evaluation modes that may toss coins. This is in stark contrast to the traditional HPS [Cramer and Shoup, Eurocrypt 2002] and existing variants like approximate HPS [Katz and Vaikuntanathan, Asiacrypt 2009], whose public and private evaluations are deterministic in their inputs. Moreover, we formalize a new property called evaluation indistinguishability by requiring statistical indistinguishability of the two probabilistic evaluation modes, even in the presence of the secret key. The evaluation indistinguishability, as well as other nice properties resulting from the probabilistic features of pr-QA-HPS, are crucial for the multi-user security proof of our frameworks under adaptive corruptions. As for instantiations, we construct pr-QA-HPS from the LWE assumption and prove its properties with almost tight reductions, which admit almost tightly secure LWE-based SIG and PKE schemes under our frameworks. Along the way, we also provide new almost-tight reductions from LWE to multi-secret LWE, which may be of independent interest.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
public-key encryptiondigital signaturetightnessmulti-user securitylattice-based cryptography
Contact author(s)
dalen17 @ sjtu edu cn
slliu @ sjtu edu cn
wzdstill @ sjtu edu cn
dwgu @ sjtu edu cn
2023-08-15: approved
2023-08-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shuai Han and Shengli Liu and Zhedong Wang and Dawu Gu},
      title = {Almost Tight Multi-User Security under Adaptive Corruptions from {LWE} in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1230},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.