Laconic cryptography focuses on designing two-message protocols that allow secure computation over large datasets while minimizing communication costs. While laconic cryptography protocols achieve asymptotically optimal communication complexity for many tasks, their concrete efficiency is prohibitively expensive, due to heavy use of public-key techniques or non-black-box cryptographic primitives. In this work, we initiate the study of \emph{laconic cryptography with preprocessing}, introducing a model that includes an offline phase to generate database-dependent correlations, which are then used in a lightweight online phase. These correlations are conceptually simple, relying on linear-algebraic techniques. This enables us to develop a protocol for private laconic vector oblivious linear evaluation (plvOLE). In such a protocol, the receiver holds a large database $\mathsf{DB}$ , and the sender has two messages $v$ and $w$ along with an index $i$ . The receiver learns the value $v \cdot \mathsf{DB}_i + w$ without revealing any other information. Our protocol, which draws from ideas developed in the context of private information retrieval with preprocessing, serves as the backbone for two applications of interest: laconic private set intersection (lPSI) for large universes and laconic function evaluation for RAM programs (RAM-LFE). Based on our plvOLE protocol, we provide efficient instantiations of these two primitives in the preprocessing model.Laconic cryptography focuses on designing two-message protocols that allow secure computation over large datasets while minimizing communication costs. While laconic cryptography protocols achieve asymptotically optimal communication complexity for many tasks, their concrete efficiency is prohibitively expensive, due to heavy use of public-key techniques or non-black-box cryptographic primitives. In this work, we initiate the study of \emph{laconic cryptography with preprocessing}, introducing a model that includes an offline phase to generate database-dependent correlations, which are then used in a lightweight online phase. These correlations are conceptually simple, relying on linear-algebraic techniques. This enables us to develop a protocol for private laconic vector oblivious linear evaluation (plvOLE). In such a protocol, the receiver holds a large database $\mathsf{DB}$, and the sender has two messages $v$ and $w$ along with an index $i$. The receiver learns the value $v \cdot \mathsf{DB}_i + w$ without revealing any other information. Our protocol, which draws from ideas developed in the context of private information retrieval with preprocessing, serves as the backbone for two applications of interest: laconic private set intersection (lPSI) for large universes and laconic function evaluation for RAM programs (RAM-LFE). Based on our plvOLE protocol, we provide efficient instantiations of these two primitives in the preprocessing model.

Jun 23, 20260 citations

Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits

Damiano Abram, Giulio Malavolta, Lawrence Roy

We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors x λ- y, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of x. We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a host of cryptographic primitives, all with security reducible to LWE, such as: (a) Adaptively secure laconic function evaluation for depth-D functions f:{0, 1}m→{0, 1}λ.," with communication m+λ.,"+D· poly(λ); (b) A trapdoor hash function for all functions; (c) An (optimally) succinct homomorphic secret sharing for all functions; (d) A rate-1/2 laconic oblivious transfer for batch messages, which is best possible. In particular, we obtain the first laconic function evaluation scheme that is adaptively secure from the standard LWE assumption, improving upon Quach, Wee, and Wichs (FOCS 2018). As a key technical ingredient, we introduce a new notion of adaptive lattice encodings, which may be of independent interest.We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors x λ- y, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of x. We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a host of cryptographic primitives, all with security reducible to LWE, such as: (a) Adaptively secure laconic function evaluation for depth-D functions f:{0, 1}m→{0, 1}λ.," with communication m+λ.,"+D· poly(λ); (b) A trapdoor hash function for all functions; (c) An (optimally) succinct homomorphic secret sharing for all functions; (d) A rate-1/2 laconic oblivious transfer for batch messages, which is best possible. In particular, we obtain the first laconic function evaluation scheme that is adaptively secure from the standard LWE assumption, improving upon Quach, Wee, and Wichs (FOCS 2018). As a key technical ingredient, we introduce a new notion of adaptive lattice encodings, which may be of independent interest.

ACM Symposium on Theory of Computing (STOC)Jun 15, 202510 citations

Laconic Function Evaluation and Applications

Willy Quach, Hoeteck Wee, Daniel Wichs

We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of f. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties: We construct a 2-round 2PC protocol between Alice and Bob with respective inputs xA, xBin which Alice learns the output f(xA, xB) in the second round. This is the first such protocol which is “Bob-optimized”, meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit f or even Alice's input xA. In contrast, prior solutions based on fully homomorphic encryption are “Alice-optimized”. . We construct an MPC protocol, which allows N parties to securely evaluate a function f(x1, ..., xN) over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit f before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size.We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of f. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties: We construct a 2-round 2PC protocol between Alice and Bob with respective inputs xA, xBin which Alice learns the output f(xA, xB) in the second round. This is the first such protocol which is “Bob-optimized”, meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit f or even Alice's input xA. In contrast, prior solutions based on fully homomorphic encryption are “Alice-optimized”. . We construct an MPC protocol, which allows N parties to securely evaluate a function f(x1, ..., xN) over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit f before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size.

Annual Symposium on Foundations of Computer ScienceOct 1, 201867 citations

\mathsf{DB}

, and the sender has two messages

v

and

w

along with an index

i

. The receiver learns the value

v \cdot \mathsf{DB}_i + w

without revealing any other information. Our protocol, which draws from ideas developed in the context of private information retrieval with preprocessing, serves as the backbone for two applications of interest: laconic private set intersection (lPSI) for large universes and laconic function evaluation for RAM programs (RAM-LFE). Based on our plvOLE protocol, we provide efficient instantiations of these two primitives in the preprocessing model.