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 decisional

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-partor-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