## CryptoDB

### Benny Pinkas

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Oblivious Key-Value Stores and Amplification for Private Set Intersection
Abstract

Many recent private set intersection (PSI) protocols encode input sets as polynomials. We consider the more general notion of an oblivious key-value store (OKVS), which is a data structure that compactly represents a desired mapping $k_i$ to $v_i$. When the $v_i$ values are random, the OKVS data structure hides the $k_i$ values that were used to generate it. The simplest (and size-optimal) OKVS is a polynomial $p$ that is chosen using interpolation such that $p(k_i)=v_i$.
We initiate the formal study of oblivious key-value stores, and show new constructions resulting in the fastest OKVS to date.
Similarly to cuckoo hashing, current analysis techniques are insufficient for finding *concrete* parameters to guarantee a small failure probability for our OKVS constructions. Moreover,
it would cost too much to run experiments to validate a small upperbound on the failure probability. We therefore show novel techniques to amplify an OKVS construction which has a failure probability $p$, to an OKVS with a similar overhead and failure probability $p^c$. Setting $p$ to be moderately small enables to validate it by running a relatively small number of $O(1/p)$ experiments. This validates a $p^c$ failure probability for the amplified OKVS.
Finally, we describe how OKVS can significantly improve the state of the art of essentially all variants of PSI. This leads to the fastest two-party PSI protocols to date, for both the semi-honest and the malicious settings. Specifically, in networks with moderate bandwidth (e.g., 30 - 300 Mbps) our malicious two-party PSI protocol has 40\% less communication and is 20-40% faster than the previous state of the art protocol, even though the latter only has heuristic confidence.

2020

EUROCRYPT

PSI from PaXoS: Fast, Malicious Private Set Intersection
📺
Abstract

We present a 2-party private set intersection (PSI) protocol which provides security against malicious participants, yet is almost as fast as the fastest known semi-honest PSI protocol of Kolesnikov et al. (CCS 2016).
Our protocol is based on a new approach for two-party PSI, which can be instantiated to provide security against either malicious or semi-honest adversaries. The protocol is unique in that the only difference between the semi-honest and malicious versions is an instantiation with different parameters for a linear error-correction code. It is also the first PSI protocol which is concretely efficient while having linear communication and security against malicious adversaries, while running in the OT-hybrid model (assuming a non-programmable random oracle).
State of the art semi-honest PSI protocols take advantage of cuckoo hashing, but it has proven a challenge to use cuckoo hashing for malicious security. Our protocol is the first to use cuckoo hashing for malicious- secure PSI. We do so via a new data structure, called a probe-and-XOR of strings (PaXoS), which may be of independent interest. This abstraction captures important properties of previous data structures, most notably garbled Bloom filters. While an encoding by a garbled Bloom filter is larger by a factor of $\Omega(\lambda)$ than the original data, we describe a significantly improved PaXoS based on cuckoo hashing that achieves constant rate while being no worse in other relevant efficiency measures.

2019

EUROCRYPT

Efficient Circuit-Based PSI with Linear Communication
📺
Abstract

We present a new protocol for computing a circuit which implements the private set intersection functionality (PSI). Using circuits for this task is advantageous over the usage of specific protocols for PSI, since many applications of PSI do not need to compute the intersection itself but rather functions based on the items in the intersection.Our protocol is the first circuit-based PSI protocol to achieve linear communication complexity. It is also concretely more efficient than all previous circuit-based PSI protocols. For example, for sets of size
$$2^{20}$$
it improves the communication of the recent work of Pinkas et al. (EUROCRYPT’18) by more than 10 times, and improves the run time by a factor of 2.8x in the LAN setting, and by a factor of 5.8x in the WAN setting.Our protocol is based on the usage of a protocol for computing oblivious programmable pseudo-random functions (OPPRF), and more specifically on our technique to amortize the cost of batching together multiple invocations of OPPRF.

2019

JOFC

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ
Abstract

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present a constant-round multi-party secure computation protocol that is fully secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round protocol of Beaver et al. (the BMR protocol) and is the first version of that protocol that is concretely efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase, we present both a generic construction (using any underlying MPC protocol) and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully secure multi-party protocols.

2019

CRYPTO

SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension
📺
Abstract

We describe a novel approach for two-party private set intersection (PSI) with semi-honest security. Compared to existing PSI protocols, ours has a more favorable balance between communication and computation. Specifically, our protocol has the lowest monetary cost of any known PSI protocol, when run over the Internet using cloud-based computing services (taking into account current rates for CPU + data). On slow networks (e.g., 10 Mbps) our protocol is actually the fastest.Our novel underlying technique is a variant of oblivious transfer (OT) extension that we call sparse OT extension. Conceptually it can be thought of as a communication-efficient multipoint oblivious PRF evaluation. Our sparse OT technique relies heavily on manipulating high-degree polynomials over large finite fields (i.e. elements whose representation requires hundreds of bits). We introduce extensive algorithmic and engineering improvements for interpolation and multi-point evaluation of such polynomials, which we believe will be of independent interest.Finally, we present an extensive empirical comparison of state-of-the-art PSI protocols in several application scenarios and along several dimensions of measurement: running time, communication, peak memory consumption, and—arguably the most relevant metric for practice—monetary cost.

2018

CRYPTO

Fast Distributed RSA Key Generation for Semi-honest and Malicious Adversaries
📺
Abstract

We present two new, highly efficient, protocols for securely generating a distributed RSA key pair in the two-party setting. One protocol is semi-honestly secure and the other maliciously secure. Both are constant round and do not rely on any specific number-theoretic assumptions and improve significantly over the state-of-the-art by allowing a slight leakage (which we show to not affect security).For our maliciously secure protocol our most significant improvement comes from executing most of the protocol in a “strong” semi-honest manner and then doing a single, light, zero-knowledge argument of correct execution. We introduce other significant improvements as well. One such improvement arrives in showing that certain, limited leakage does not compromise security, which allows us to use lightweight subprotocols. Another improvement, which may be of independent interest, comes in our approach for multiplying two large integers using OT, in the malicious setting, without being susceptible to a selective-failure attack.Finally, we implement our malicious protocol and show that its performance is an order of magnitude better than the best previous protocol, which provided only semi-honest security.

2018

PKC

Committed MPC
Abstract

We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol.Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest:1.Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality.2.Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach.
Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.

2015

JOFC

2012

JOFC

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer
Abstract

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao’s protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

2010

EPRINT

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer
Abstract

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven secure under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao's protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

2010

EPRINT

Oblivious RAM Revisited
Abstract

We reinvestigate the oblivious RAM concept introduced by Goldreich and Ostrovsky, which enables a client, that can store locally only a constant amount of data, to store remotely $n$ data items, and access them while hiding the identities of the items which are being accessed. Oblivious RAM is often cited as a powerful tool, which can be used, for example, for search on encrypted data or for preventing cache attacks. However, oblivious RAM it is also commonly considered to be impractical due to its overhead, which is asymptotically efficient but is quite high: each data request is replaced by $O(\log^4 n)$ requests, or by $O(\log^3 n)$ requests where the constant in the ``$O$'' notation is a few thousands. In addition, $O(n \log n)$ external memory is required in order to store the $n$ data items. We redesign the oblivious RAM protocol using modern tools, namely Cuckoo hashing and a new oblivious sorting algorithm. The resulting protocol uses only $O(n)$ external memory, and replaces each data request by only $O(\log^2 n)$ requests (with a small constant). This analysis is validated by experiments that we ran.

2008

EPRINT

Secure Multiparty Computation for Privacy-Preserving Data Mining
Abstract

In this paper, we survey the basic paradigms and notions of secure multiparty computation and discuss their relevance to the field of privacy-preserving data mining. In addition to reviewing definitions and constructions for secure multiparty computation, we discuss the issue of efficiency and demonstrate the difficulties involved in constructing highly efficient protocols. We also present common errors that are prevalent in the literature when secure multiparty computation techniques are applied to privacy-preserving data mining. Finally, we discuss the relationship between secure multiparty computation and privacy-preserving data mining, and show which problems it solves and which problems it does not.

2008

EPRINT

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries
Abstract

We show an efficient secure two-party protocol, based on Yao's construction, which provides security against malicious adversaries. Yao's original protocol is only secure in the presence of semi-honest adversaries, and can be transformed into a protocol that achieves security against malicious adversaries by applying the compiler of Goldreich, Micali and Wigderson (the ``GMW compiler''). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs.
Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the {\sf ideal/real simulation paradigm}, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running $O(1)$ oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao's protocol does \emph{not} yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security.
Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party computation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a statistical security parameter. These two reductions are comparable to Kilian's reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit~\cite{Kil}.

2007

EUROCRYPT

2007

EPRINT

Cryptanalysis of the Random Number Generator of the Windows Operating System
Abstract

The pseudo-random number generator (PRNG) used by the Windows operating system is the most commonly used PRNG. The pseudo-randomness of the output of this generator is crucial for the security of almost any application running in Windows. Nevertheless, its exact algorithm was never published.
We examined the binary code of a distribution of Windows 2000, which is still the second most popular operating system after Windows XP. (This investigation was done without any help from Microsoft.) We
reconstructed, for the first time, the algorithm used by the pseudo-random number generator (namely, the function CryptGenRandom). We analyzed the security of the algorithm and found a non-trivial attack: given the internal state of the generator, the previous state can be computed in $O(2^{23})$ work (this is an attack on the forward-security of the generator, an $O(1)$ attack on backward security is trivial). The attack on forward-security demonstrates that the design of the generator is flawed, since it is well known how to prevent such attacks.
We also analyzed the way in which the generator is run by the operating system, and found that it amplifies the effect of the
attacks: The generator is run in user mode rather than in kernel mode, and therefore it is easy to access its state even without administrator privileges. The initial values of part of the state of the generator are not set explicitly, but rather are defined by whatever values are present on the stack when the generator is
called.Furthermore, each process runs a different copy of the generator, and the state of the generator is refreshed with system generated entropy only after generating 128 KBytes of output for the process running it. The result of combining this observation with our attack is that learning a single state may reveal 128 Kbytes of the past and future output of the generator.
The implication of these findings is that a buffer overflow attack or a similar attack can be used to learn a single state of the generator, which can then be used to predict all random values, such as SSL keys, used by a process in all its past and future operation. This attack is more severe and more efficient than known attacks, in which an attacker can only learn SSL keys if it is controlling the attacked machine at the time the keys are used.

2006

EPRINT

Analysis of the Linux Random Number Generator
Abstract

Linux is the most popular open source project. The
Linux random number generator is part of the kernel of
all Linux distributions and is based on generating randomness from entropy of operating
system events. The output of this generator is used for almost every
security protocol, including TLS/SSL key generation, choosing TCP sequence numbers,
and file system and email encryption. Although the
generator is part of an open source project, its source code (about $2500$ lines of code) is poorly documented, and patched with hundreds of code patches.
We used dynamic and static reverse engineering to learn the operation of this generator. This paper presents
a description of the underlying algorithms and exposes several security vulnerabilities. In particular, we show an attack on the forward security of the generator which enables an adversary who exposes the state of the generator
to compute previous states and outputs. In addition we present a few cryptographic
flaws in the design of the generator, as well as measurements of
the actual entropy collected by it, and a critical analysis of the use of the generator in Linux distributions on disk-less devices.

2004

EPRINT

A Proof of Yao's Protocol for Secure Two-Party Computation
Abstract

In the mid 1980's, Yao presented a constant-round protocol for
securely computing any two-party functionality in the presence of
semi-honest adversaries (FOCS 1986). In this paper, we provide a
complete description of Yao's protocol, along with a rigorous
proof of security. Despite the importance of Yao's protocol to the
field of secure computation, to the best of our knowledge, this is
the first time that a proof of security has been published.

1997

EPRINT

Visual Authentication and Identification
Abstract

The problems of authentication and identification have
received wide interest in cryptographic research.
However, there has been no satisfactory solution for the problem of
authentication by a human recipient
who does not use any trusted computational device.
The problem of authentication arises for example in
the context of smartcard--human interaction, in particular in
the context of electronic wallets. The problem of identification is ubiquitous
in communication over insecure networks.
This paper introduces visual authentication and visual
identification methods, which are
authentication and identification methods for human users
based on visual cryptography. These methods are
very natural and easy to use, and can be implemented using very
common ``low tech'' technology. The methods we suggest are efficient
in the sense that a single transparency can be used
for several authentications or for several identifications. The visual
authentication methods we suggest are not limited to authenticating
textual messages, and can be used to authenticate any image.
An important contribution of this paper is the introduction of a
framework for proving the security of protocols in which humans take an
active part. We rigorously prove the security of our schemes using this
framework.

#### Program Committees

- PKC 2019
- Crypto 2019
- Crypto 2016
- PKC 2014
- Crypto 2011
- PKC 2010
- Crypto 2009
- PKC 2009
- PKC 2006
- Eurocrypt 2005
- Crypto 2003

#### Coauthors

- Ittai Abraham (1)
- Arash Afshar (2)
- Gagan Aggarwal (2)
- David W. Archer (1)
- N. Asokan (1)
- Dan Bogdanov (1)
- Leo Dorrendorf (1)
- Christopher W. Fletcher (1)
- Tore Kasper Frederiksen (1)
- Tore K. Frederiksen (1)
- Michael J. Freedman (3)
- Gayathri Garimella (1)
- Shay Gueron (2)
- Zvi Gutterman (2)
- Shai Halevi (1)
- Carmit Hazay (1)
- Yuval Ishai (1)
- Yehuda Lindell (19)
- Jian Liu (1)
- James L. McInnes (1)
- Nina Mishra (2)
- Payman Mohassel (2)
- Moni Naor (8)
- Kartik Nayak (1)
- Kobbi Nissim (2)
- Ariel Nof (2)
- Valery Osheter (1)
- Eli Oxman (1)
- Pille Pullonen (1)
- Omer Reingold (2)
- Tzachy Reinman (4)
- Ling Ren (1)
- Ben Riva (2)
- Mike Rosulek (3)
- Thomas Schneider (5)
- Gil Segev (1)
- Nigel P. Smart (4)
- Oleksandr Tkachenko (1)
- Ni Trieu (3)
- Christian Weinert (1)
- Udi Wieder (1)
- Stephen C. Williams (1)
- Avishay Yanai (8)
- Michael Zohner (2)