Paper 2022/806

Multi-key and Multi-input Predicate Encryption from Learning with Errors

Danilo Francati, Aarhus University
Daniele Friolo, Sapienza University of Rome
Giulio Malavolta, Max Planck Institute for Security and Privacy
Daniele Venturi, Sapienza University of Rome

We put forward two natural generalizations of predicate encryption (PE), dubbed multi-key and multi-input PE. More in details, our contributions are threefold. - Definitions. We formalize security of multi-key PE and multi-input PE following the standard indistinguishability paradigm, and modeling security both against malicious senders (i.e., corruption of encryption keys) and malicious receivers (i.e., collusions). - Constructions. We construct adaptively secure multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the sub-exponential hardness of the learning with errors (LWE) problem. - Applications. We show that multi-key and multi-input PE for expressive enough predicates suffices for interesting cryptographic applications, including non-interactive multi-party computation (NI-MPC) and matchmaking encryption (ME). In particular, plugging in our constructions of multi-key and multi-input PE, under the sub-exponential LWE assumption, we obtain the first ME supporting arbitrary policies with unbounded collusions, as well as robust (resp. non-robust) NI-MPC for so-called all-or-nothing functions satisfying a non-trivial notion of reusability and supporting a constant (resp. polynomial) number of parties. Prior to our work, both of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
predicate encryptionmatchmaking encryptionnon-interactive MPCLWE
Contact author(s)
danilofrancati @ gmail com
friolo @ di uniroma1 it
giulio malavolta @ hotmail it
venturi @ di uniroma1 it
2023-02-24: last of 3 revisions
2022-06-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Danilo Francati and Daniele Friolo and Giulio Malavolta and Daniele Venturi},
      title = {Multi-key and Multi-input Predicate Encryption from Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2022/806},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.