Efficient Laconic Cryptography from Learning With Errors

Abstract. 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 transfer

– Registration-based encryption scheme

– Laconic 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).

这篇好文章是转载于：学新通技术网