Non-Interactive Cryptography in the RAM Model of Computation.

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

Cryptography in an Unbounded Computational Model

David Paul Woodruff, Marten van Dijk

Lecture notes in computer scienceJan 1, 20023 citations

Black-Box Garbled RAM.

Sanjam Garg, Steve Lu, Rafail Ostrovsky

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao’s garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives. In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the OT-hybrid model.Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao’s garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives. In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the OT-hybrid model.

Electronic colloquium on computational complexityJan 1, 20154 citations

Efficient Non-interactive Secure Computation

Yuval Ishai, Eyal Kushilevitz Z, Rafail Ostrovsky +2 more

Lecture notes in computer scienceJan 1, 2011115 citations

Non-Interactive Secure Computation Based on Cut-and-Choose.

Arash Afshar, Payman Mohassel, Benny Pinkas B +1 more

Jan 1, 20151 citation

\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.