## CryptoDB

### Kobbi Nissim

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Separating Adaptive Streaming from Oblivious Streaming using the Bounded Storage Model
📺
Abstract

Streaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms typically work under the assumption that the input stream is chosen independently from the internal state of the algorithm. Algorithms that utilize this assumption are called oblivious algorithms. Recently, there is a growing interest in studying streaming algorithms that maintain utility also when the input stream is chosen by an adaptive adversary, possibly as a function of previous estimates given by the streaming algorithm. Such streaming algorithms are said to be adversarially-robust.
By combining techniques from learning theory with cryptographic tools from the bounded storage model, we separate the oblivious streaming model from the adversarially-robust streaming model. Specifically, we present a streaming problem for which every adversarially-robust streaming algorithm must use polynomial space, while there exists a classical (oblivious) streaming algorithm that uses only polylogarithmic space. This is the first general separation between the capabilities of these two models, resolving one of the central open questions in adversarial robust streaming.

2020

TCC

On the Round Complexity of the Shuffle Model
📺
Abstract

The shuffle model of differential privacy [Bittau et al. SOSP 2017; Erlingsson et al. SODA 2019; Cheu et al. EUROCRYPT 2019] was proposed as a viable model for performing distributed differentially private computations. Informally, the model consists of an untrusted analyzer that receives messages sent by participating parties via a shuffle functionality, the latter potentially disassociates messages from their senders. Prior work focused on one-round differentially private shuffle model protocols, demonstrating that functionalities such as addition and histograms can be performed in this model with accuracy levels similar to that of the curator model of differential privacy, where the computation is performed by a fully trusted party. A model closely related to the shuffle model was presented in the seminal work of Ishai et al. on establishing cryptography from anonymous communication [FOCS 2006].
Focusing on the round complexity of the shuffle model, we ask in this work what can be computed in the shuffle model of differential privacy with two rounds. Ishai et al. showed how to use one round of the shuffle to establish secret keys between every two parties. Using this primitive to simulate a general secure multi-party protocol increases its round complexity by one. We show how two parties can use one round of the shuffle to send secret messages without having to first establish a secret key, hence retaining round complexity. Combining this primitive with the two-round semi-honest protocol of Applebaum, Brakerski, and Tsabary [TCC 2018], we obtain that every randomized functionality can be computed in the shuffle model with an honest majority, in merely two rounds. This includes any differentially private computation.
We hence move to examine differentially private computations in the shuffle model that (i) do not require the assumption of an honest majority, or (ii) do not admit one-round protocols, even with an honest majority. For that, we introduce two computational tasks: common element, and nested common element with parameter $\alpha$. For the common element problem we show that for large enough input domains, no one-round differentially private shuffle protocol exists with constant message complexity and negligible $\delta$, whereas a two-round protocol exists where every party sends a single message in every round. For the nested common element we show that no one-round differentially private protocol exists for this problem with adversarial coalition size $\alpha n$. However, we show that it can be privately computed in two rounds against coalitions of size $cn$ for every $c < 1$. This yields a separation between one-round and two-round protocols. We further show a one-round protocol for the nested common element problem that is differentially private with coalitions of size smaller than $c n$ for all $0 < c < \alpha < 1 / 2$.

2019

CRYPTO

The Privacy Blanket of the Shuffle Model
📺
Abstract

This work studies differential privacy in the context of the recently proposed shuffle model. Unlike in the local model, where the server collecting privatized data from users can track back an input to a specific user, in the shuffle model users submit their privatized inputs to a server anonymously. This setup yields a trust model which sits in between the classical curator and local models for differential privacy. The shuffle model is the core idea in the Encode, Shuffle, Analyze (ESA) model introduced by Bittau et al. (SOPS 2017). Recent work by Cheu et al. (EUROCRYPT 2019) analyzes the differential privacy properties of the shuffle model and shows that in some cases shuffled protocols provide strictly better accuracy than local protocols. Additionally, Erlingsson et al. (SODA 2019) provide a privacy amplification bound quantifying the level of curator differential privacy achieved by the shuffle model in terms of the local differential privacy of the randomizer used by each user.In this context, we make three contributions. First, we provide an optimal single message protocol for summation of real numbers in the shuffle model. Our protocol is very simple and has better accuracy and communication than the protocols for this same problem proposed by Cheu et al. Optimality of this protocol follows from our second contribution, a new lower bound for the accuracy of private protocols for summation of real numbers in the shuffle model. The third contribution is a new amplification bound for analyzing the privacy of protocols in the shuffle model in terms of the privacy provided by the corresponding local randomizer. Our amplification bound generalizes the results by Erlingsson et al. to a wider range of parameters, and provides a whole family of methods to analyze privacy amplification in the shuffle model.

2012

JOFC

Efficient Set Operations in the Presence of Malicious Adversaries
Abstract

We revisit the problem of constructing efficient secure two-party protocols for the problems of set intersection and set union, focusing on the model of malicious parties. Our main results are constant-round protocols that exhibit linear communication and a (practically) linear number of exponentiations with simulation-based security. At the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC secure, and we discuss how to perform these transformations.

2006

EPRINT

Hard Instances of the Constrained Discrete Logarithm Problem
Abstract

The discrete logarithm problem (DLP) generalizes
to the constrained DLP, where the secret exponent $x$
belongs to a set known to the attacker. The complexity of
generic algorithms for solving the constrained DLP depends
on the choice of the set. Motivated by cryptographic
applications, we study sets with succinct representation
for which the constrained DLP is hard. We draw on earlier
results due to Erd\"os et~al. and Schnorr, develop
geometric tools such as generalized Menelaus' theorem for
proving lower bounds on the complexity of the constrained
DLP, and construct sets with succinct representation with
provable non-trivial lower bounds.

2001

EPRINT

Secure Multiparty Computation of Approximations
Abstract

Approximation algorithms can sometimes be used to obtain efficient
solutions where no efficient exact computation is known. In
particular, approximations are often useful in a distributed setting
where the inputs are held by different parties and are extremely
large. Furthermore, for some applications, the parties want to
cooperate to compute a function of their inputs without revealing more
information than they have to.
Suppose the function $\fhat$ is an approximation to the function $f$.
Secure multiparty computation of $f$ allows the parties to compute $f$
without revealing more than they have to, but it requires some
additional overhead in computation and communication. Hence, if
computation of $f$ is inefficient or just efficient enough to be
practical, then secure computation of $f$ may be impractically
expensive. Furthermore, a secure computation of $\fhat$ is not
necessarily as private as a secure computation of $f$, because the
output of $\fhat$ may reveal more information than the output of $f$.
In this paper, we present definitions and protocols of secure
multiparty approximate computation that show how to realize most of
the cost savings available by using $\fhat$ instead of $f$ without
losing the privacy of a secure computation of $f$.
We make three contributions. First, we give formal definitions of
secure multiparty approximate computations. Second, we present an
efficient, sublinear-communication, private approximate computation
for the Hamming distance; we also give an efficient,
polylogarithmic-communication solution for the $L^{2}$ distance
in a relaxed model. Finally, we give an efficient private
approximation of the permanent and other related \#P-hard problems.

2001

EPRINT

Communication Complexity and Secure Function Evaluation
Abstract

A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: ``any function $f$ that can be computed using polynomial resources can be computed securely using polynomial resources'' (where `resources' refers to communication and computation). This result follows by a general transformation from any circuit for $f$ to a secure protocol that evaluates $f$.
Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of $f$.
For the design of efficient secure protocols we suggest two new methodologies, that differ with respect to their underlying computational models. In one methodology we utilize the communication complexity tree (or branching program) representation of $f$. We start with an efficient (insecure) protocol for $f$ and transform it into
a secure protocol. In other words, ``any function $f$ that can be computed using communication complexity $c$ can be can be computed securely using communication complexity that is polynomial in $c$ and a security parameter''. The second methodology uses the circuit computing $f$, enhanced with look-up tables as its underlying computational model.
It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of $f$ on a RAM machine and transform it into a secure protocol.
We show many applications of these new methodologies resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the ``millionaires problem'', where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.

#### Program Committees

- TCC 2009
- Crypto 2006

#### Coauthors

- Borja Balle (1)
- Amos Beimel (6)
- James Bell (1)
- Dan Boneh (1)
- Ran Canetti (1)
- Cynthia Dwork (3)
- Joan Feigenbaum (1)
- Michael J. Freedman (2)
- Adrià Gascón (1)
- Eu-Jin Goh (1)
- Iftach Haitner (1)
- Renen Hallak (1)
- Carmit Hazay (3)
- Yuval Ishai (2)
- Seny Kamara (1)
- Marc Kaplan (1)
- Shiva Kasiviswanathan (1)
- Shiva Prasad Kasiviswanathan (1)
- Joe Kilian (1)
- George Kollios (1)
- Yehuda Lindell (1)
- Tal Malkin (4)
- Yishay Mansour (1)
- Frank McSherry (2)
- Xianrui Meng (1)
- Ilya Mironov (1)
- Anton Mityagin (1)
- Moni Naor (1)
- Eran Omri (1)
- Claudio Orlandi (1)
- Erez Petrank (1)
- Benny Pinkas (2)
- Sofya Raskhodnikova (1)
- Adam Smith (3)
- Uri Stemmer (2)
- Martin Strauss (1)
- Enav Weinreb (3)
- Rebecca N. Wright (1)