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

Automated Cryptography

Michael A. Guillen

Science NewsSep 18, 19760 citations

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$ -query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$ -qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$ . In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$ , with a trivial attack at $S = N$ . This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$ . Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$ . (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

quant-pharXiv:2610.02101Oct 2, 20260 citations

Some Further Cryptographic Protocols

Springer eBooksNov 10, 20080 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.

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a

T

-query adversary with

S

qubits of non-uniform advice can recover a random key

k

from the

n

-qubit binary phase state

|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle

with probability at most

O(\frac{T^2 + \sqrt{ST}}{N})

for

N=2^n

. In contrast, the best known bound for post-quantum one-way functions is

O(\frac{T^2 + ST}{N})

, with a trivial attack at

S = N

. This demonstrates a new advantage of quantum cryptography over classical cryptography:

n

qubits of communication suffice for security against preprocessing attacks with space up to

N^2

rather than

N

. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of

O(\frac{T^2}N + \sqrt{\frac{ST}N})

. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight

O(\frac{\sqrt{S}}N)

bound for the pseudorandomness of random binary phase states against space

S

distinguishers.