International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Multi-key and Multi-input Predicate Encryption (for Conjunctions) from Learning with Errors

Authors:
Danilo Francati
Daniele Friolo
Giulio Malavolta
Daniele Venturi
Download:
DOI: 10.1007/s00145-024-09504-7
Search ePrint
Search Google
Abstract: AbstractWe 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.
BibTeX
@article{jofc-2024-34429,
  title={Multi-key and Multi-input Predicate Encryption (for Conjunctions) from Learning with Errors},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={37},
  pages={24},
  doi={10.1007/s00145-024-09504-7},
  author={Danilo Francati and Daniele Friolo and Giulio Malavolta and Daniele Venturi},
  year=2024
}