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

Danilo Francati; Daniele Friolo; Giulio Malavolta; Daniele Venturi

doi:10.1007/978-3-031-30620-4_19

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

Danilo Francati^*, Daniele Friolo, Giulio Malavolta, Daniele Venturi

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

14 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2023 : 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III
Editors	Carmit Hazay, Martijn Stam
Number of pages	32
Place of publication	Cham
Publisher	Springer
Publication date	Apr 2023
Pages	573-604
ISBN (Print)	978-3-031-30619-8
ISBN (Electronic)	978-3-031-30620-4
DOIs	https://doi.org/10.1007/978-3-031-30620-4_19
Publication status	Published - Apr 2023
Event	42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 - Lyon, France Duration: 23 Apr 2023 → 27 Apr 2023

Conference

Conference	42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023
Country/Territory	France
City	Lyon
Period	23/04/2023 → 27/04/2023

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14006
ISSN	0302-9743

Keywords

LWE
matchmaking encryption
non-interactive MPC
predicate encryption

Access to Document

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

Library access?

Check availability with the Royal Danish Library

Cite this

Francati, D., Friolo, D., Malavolta, G., & Venturi, D. (2023). Multi-key and Multi-input Predicate Encryption from Learning with Errors. In C. Hazay, & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III (pp. 573-604). Springer. https://doi.org/10.1007/978-3-031-30620-4_19

Francati, Danilo ; Friolo, Daniele ; Malavolta, Giulio et al. / Multi-key and Multi-input Predicate Encryption from Learning with Errors. Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III. editor / Carmit Hazay ; Martijn Stam. Cham : Springer, 2023. pp. 573-604 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14006).

@inproceedings{f1bd919526e7482391e2265f77a57894,

title = "Multi-key and Multi-input Predicate Encryption from Learning with Errors",

abstract = "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.",

keywords = "LWE, matchmaking encryption, non-interactive MPC, predicate encryption",

author = "Danilo Francati and Daniele Friolo and Giulio Malavolta and Daniele Venturi",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 ; Conference date: 23-04-2023 Through 27-04-2023",

year = "2023",

month = apr,

doi = "10.1007/978-3-031-30620-4\_19",

language = "English",

isbn = "978-3-031-30619-8",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "573--604",

editor = "Carmit Hazay and Martijn Stam",

booktitle = "Advances in Cryptology – EUROCRYPT 2023",

address = "Netherlands",

}

Francati, D, Friolo, D, Malavolta, G & Venturi, D 2023, Multi-key and Multi-input Predicate Encryption from Learning with Errors. in C Hazay & M Stam (eds), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III. Springer, Cham, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14006, pp. 573-604, 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023, Lyon, France, 23/04/2023. https://doi.org/10.1007/978-3-031-30620-4_19

Multi-key and Multi-input Predicate Encryption from Learning with Errors. / Francati, Danilo; Friolo, Daniele; Malavolta, Giulio et al.
Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III. ed. / Carmit Hazay; Martijn Stam. Cham: Springer, 2023. p. 573-604 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14006).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

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

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 -

Francati D, Friolo D, Malavolta G, Venturi D. Multi-key and Multi-input Predicate Encryption from Learning with Errors. In Hazay C, Stam M, editors, Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III. Cham: Springer. 2023. p. 573-604. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14006). doi: 10.1007/978-3-031-30620-4_19