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 multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the hardness of the standard 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 matchmaking encryption (ME) and non-interactive multi-party computation (NI-MPC). As a corollary, plugging in our concrete constructions of multi-key and multi-input PE, we obtain the first construction of ME for arbitrary policies, as well as NI-MPC with partial re-usability for all-or-nothing functions and a constant number of parties, under the standard LWE assumption. Prior to our work, all of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption.

Available format(s)
Publication info
predicate encryption matchmaking encryption non-interactive MPC LWE
Contact author(s)
dfrancati @ cs au dk
friolo @ di uniroma1 it
giulio malavolta @ hotmail it
venturi @ di uniroma1 it
2022-06-23: approved
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.