Efficient Laconic Cryptography from Learning with Errors

Nico Döttling, Dimitris Kolonelos, Russell W.F. Lai*, Chuanwei Lin, Giulio Malavolta, Ahmadreza Rahimi

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

3 Sitaatiot (Scopus)

Abstrakti

Laconic cryptography is an emerging paradigm that enables cryptographic primitives with sublinear communication complexity in just two messages. In particular, a two-message protocol between Alice and Bob is called laconic if its communication and computation complexity are essentially independent of the size of Alice’s input. This can be thought of as a dual notion of fully-homomorphic encryption, as it enables “Bob-optimized” protocols. This paradigm has led to tremendous progress in recent years. However, all existing constructions of laconic primitives are considered only of theoretical interest: They all rely on non-black-box cryptographic techniques, which are highly impractical. This work shows that non-black-box techniques are not necessary for basic laconic cryptography primitives. We propose a completely algebraic construction of laconic encryption, a notion that we introduce in this work, which serves as the cornerstone of our framework. We prove that the scheme is secure under the standard Learning With Errors assumption (with polynomial modulus-to-noise ratio). We provide proof-of-concept implementations for the first time for laconic primitives, demonstrating the construction is indeed practical: For a database size of 2 50, encryption and decryption are in the order of single digit milliseconds. Laconic encryption can be used as a black box to construct other laconic primitives. Specifically, we show how to construct: Laconic oblivious transferRegistration-based encryption schemeLaconic private-set intersection protocol All of the above have essentially optimal parameters and similar practical efficiency. Furthermore, our laconic encryption can be preprocessed such that the online encryption step is entirely combinatorial and therefore much more efficient. Using similar techniques, we also obtain identity-based encryption with an unbounded identity space and tight security proof (in the standard model).

AlkuperäiskieliEnglanti
OtsikkoAdvances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2023, Proceedings
ToimittajatCarmit Hazay, Martijn Stam
KustantajaSpringer
Sivut417-446
Sivumäärä30
ISBN (painettu)978-3-031-30619-8
DOI - pysyväislinkit
TilaJulkaistu - 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaAnnual International Conference on the Theory and Applications of Cryptographic Techniques - Lyon, Ranska
Kesto: 23 huhtik. 202327 huhtik. 2023
Konferenssinumero: 42

Julkaisusarja

NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
KustantajaSpringer
Vuosikerta14006 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Conference

ConferenceAnnual International Conference on the Theory and Applications of Cryptographic Techniques
LyhennettäEUROCRYPT
Maa/AlueRanska
KaupunkiLyon
Ajanjakso23/04/202327/04/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Efficient Laconic Cryptography from Learning with Errors'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä