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

TY - GEN

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

AU - Francati, Danilo

AU - Friolo, Daniele

AU - Malavolta, Giulio

AU - Venturi, Daniele

N1 - Publisher Copyright: © 2023, International Association for Cryptologic Research.

PY - 2023/4

Y1 - 2023/4

N2 - 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.

AB - 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.

KW - LWE

KW - matchmaking encryption

KW - non-interactive MPC

KW - predicate encryption

U2 - 10.1007/978-3-031-30620-4_19

DO - 10.1007/978-3-031-30620-4_19

M3 - Article in proceedings

AN - SCOPUS:85161724772

SN - 978-3-031-30619-8

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 573

EP - 604

BT - Advances in Cryptology – EUROCRYPT 2023

A2 - Hazay, Carmit

A2 - Stam, Martijn

PB - Springer

CY - Cham

T2 - 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023

Y2 - 23 April 2023 through 27 April 2023

ER -