## CryptoDB

### Eyal Kushilevitz

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Secure Computation from One-Way Noisy Communication, or: Anti-Correlation via Anti-Concentration
📺
Abstract

Can a sender encode a pair of messages (m_0,m_1) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one?
Garg et al. (Crypto 2015) showed that this is information-theoretically impossible.
We show how to circumvent this impossibility by assuming that the receiver is computationally bounded, settling for an inverse-polynomial security error (which is provably necessary), and relying on ideal obfuscation.
Our solution creates a ``computational anti-correlation'' between the events of receiving m_0 and receiving m_1 by exploiting the anti-concentration of the binomial distribution.
The ideal obfuscation primitive in our construction can either be directly realized using (stateless) tamper-proof hardware, yielding an unconditional result, or heuristically instantiated using existing indistinguishability obfuscation schemes. We put forward a new notion of obfuscation that suffices to securely instantiate our construction.
As a corollary, we get similar feasibility results for general secure computation of sender-receiver functionalities by leveraging the completeness of the above ``random oblivious transfer'' functionality.

2020

ASIACRYPT

Cryptography from One-Way Communication: On Completeness of Finite Channels
📺
Abstract

Garg et al. (Crypto 2015) initiated the study of cryptographic protocols over noisy channels in the non-interactive setting, namely when only one party speaks. A major question left open by this work is the completeness of {\em finite} channels, whose input and output alphabets do not grow with the desired level of security. In this work, we address this question by obtaining the following results:
Completeness of Bit-ROT with Inverse Polynomial Error: We show that bit-ROT (i.e., Randomized Oblivious Transfer channel, where each of the two messages is a single bit) can be used to realize general randomized functionalities with inverse polynomial error. Towards this, we provide a construction of string-ROT from bit-ROT with inverse polynomial error.
No Finite Channel is Complete with Negligible Error: To complement the above, we show that {\it no} finite channel can be used to realize string-ROT with negligible error, implying that the inverse polynomial error in the completeness of bit-ROT is inherent. This holds even with semi-honest parties and for computational security, and is contrasted with the (negligible-error) completeness of string-ROT shown by Garg et al.
Characterization of Finite Channels Enabling Zero-Knowledge Proofs: An important instance of secure computation is zero-knowledge proofs.
Noisy channels can potentially be used to realize truly non-interactive zero-knowledge proofs, without trusted common randomness, and with non-transferability and deniability features that cannot be realized in the plain model. Garg et al. obtain such zero-knowledge proofs from the binary erasure channel (BEC) and the binary symmetric channel (BSC). We complete the picture by showing that in fact any non-trivial channel suffices.

2019

CRYPTO

Cryptographic Sensing
📺
Abstract

Is it possible to measure a physical object in a way that makes the measurement signals unintelligible to an external observer? Alternatively, can one learn a natural concept by using a contrived training set that makes the labeled examples useless without the line of thought that has led to their choice? We initiate a study of “cryptographic sensing” problems of this type, presenting definitions, positive and negative results, and directions for further research.

2019

PKC

Sub-logarithmic Distributed Oblivious RAM with Small Block Size
Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to securely execute RAM programs over data that is stored in an untrusted server. Distributed Oblivious RAM is a variant of ORAM, where the data is stored in $$m>1$$ servers. Extensive research over the last few decades have succeeded to reduce the bandwidth overhead of ORAM schemes, both in the single-server and the multi-server setting, from $$O(\sqrt{N})$$ to O(1). However, all known protocols that achieve a sub-logarithmic overhead either require heavy server-side computation (e.g. homomorphic encryption), or a large block size of at least $$\varOmega (\log ^3 N)$$.In this paper, we present a family of distributed ORAM constructions that follow the hierarchical approach of Goldreich and Ostrovsky [17]. We enhance known techniques, and develop new ones, to take better advantage of the existence of multiple servers. By plugging efficient known hashing schemes in our constructions, we get the following results:1.For any number $$m\ge 2$$ of servers, we show an m-server ORAM scheme with $$O(\log N/\log \log N)$$ overhead, and block size $$\varOmega (\log ^2 N)$$. This scheme is private even against an $$(m-1)$$-server collusion.2.A three-server ORAM construction with $$O(\omega (1)\cdot \log N/\log \log N)$$ overhead and a block size almost logarithmic, i.e. $$\varOmega (\log ^{1+\epsilon }N)$$.
We also investigate a model where the servers are allowed to perform a linear amount of light local computations, and show that constant overhead is achievable in this model, through a simple four-server ORAM protocol. From theoretical viewpoint, this is the first ORAM scheme with asymptotic constant overhead, and polylogarithmic block size, that does not use homomorphic encryption. Practically speaking, although we do not provide an implementation of the suggested construction, evidence from related work (e.g. [12]) confirms that despite the linear computational overhead, our construction is practical, in particular when applied to secure computation.

2019

TCC

On Fully Secure MPC with Solitary Output
Abstract

We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities?We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness-based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way.On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.

2019

TCC

Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND
Abstract

We consider multi-party information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource, and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [12, 17].More concretely, we consider the randomness complexity of the basic boolean function and, that serves as a building block in the design of many private protocols. We show that and cannot be privately computed using a single random bit, thus giving the first non-trivial lower bound on the 1-private randomness complexity of an explicit boolean function, $$f: \{0,1\}^n \rightarrow \{0,1\}$$. We further show that the function and, on any number of inputs n (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of $$n=3$$ players), improving the upper bound of 73 random bits implicit in [17]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for xor, which is trivially 1-random, and for several degenerate functions).

2018

TCC

Best Possible Information-Theoretic MPC
Abstract

We reconsider the security guarantee that can be achieved by general protocols for secure multiparty computation in the most basic of settings: information-theoretic security against a semi-honest adversary. Since the 1980s, we have elegant solutions to this problem that offer full security, as long as the adversary controls a minority of the parties, but fail completely when that threshold is crossed. In this work, we revisit this problem, questioning the optimality of the standard notion of security. We put forward a new notion of information-theoretic security which is strictly stronger than the standard one, and which we argue to be “best possible.” This notion still requires full security against dishonest minority in the usual sense, and adds a meaningful notion of information-theoretic security even against dishonest majority.We present protocols for useful classes of functions that satisfy this new notion of security. Our protocols have the unique feature of combining the efficiency benefits of protocols for an honest majority and (most of) the security benefits of protocols for dishonest majority. We further extend some of the solutions to the malicious setting.

2010

EPRINT

On Achieving the "Best of Both Worlds" in Secure Multiparty Computation
Abstract

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide ``full security'' (and, in particular, guarantee output delivery and fairness) when this assumption holds; unfortunately, these protocols are completely insecure if this assumption is violated. On the other hand, protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a \emph{single} party is dishonest.
It is natural to wonder whether it is possible to achieve the ``best of both worlds'': namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) but show some positive results regarding what \emph{can} be achieved.

2010

EPRINT

Black-Box Constructions of Protocols for Secure Computation
Abstract

It is well known that secure computation without an honest majority requires computational assumptions. An interesting question that therefore arises relates to the way such computational assumptions are used. Specifically, can the secure protocol use the underlying primitive (e.g., a one-way trapdoor permutation) in a {\em black-box} way, treating it as an oracle, or must it be {\em nonblack-box} (by referring to the code that computes the primitive)? Despite the fact that many general constructions of cryptographic schemes refer to the underlying primitive in a black-box wayonly, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).
In this paper, we study whether such nonblack-box use is essential. We answer this question in the negative. Concretely, we present a \emph{fully black-box reduction} from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we get the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a {\em black-box} use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption.

2007

EPRINT

Public Key Encryption that Allows PIR Queries
Abstract

Consider the following problem: Alice wishes to maintain her email
using a storage-provider Bob (such as a Yahoo! or hotmail e-mail
account). This storage-provider should provide for Alice the ability
to collect, retrieve, search and delete emails but, at the same
time, should learn neither the content of messages sent from the
senders to Alice (with Bob as an intermediary), nor the search
criteria used by Alice. A trivial solution is that messages will be
sent to Bob in encrypted form and Alice, whenever she wants to
search for some message, will ask Bob to send her a copy of the
entire database of encrypted emails. This however is highly
inefficient. We will be interested in solutions that are communication-efficient and, at the same time, respect the privacy of Alice. In this paper, we show how to create a public-key encryption scheme for Alice that allows PIR searching over encrypted documents. Our solution provides a theoretical solution to an open problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on ``Public-key Encryption with Keyword Search'', providing the first scheme that does not reveal any partial information regarding user's search (including the access pattern) in the public-key setting and with non-trivially
small communication complexity.
The main technique of our solution also allows for Single-Database PIR writing with sub-linear communication complexity, which we consider of independent interest.

2006

JOFC

2006

EPRINT

Cryptography from Anonymity
Abstract

There is a vast body of work on {\em implementing} anonymous
communication. In this paper, we study the possibility of using
anonymous communication as a {\em building block}, and show that
one can leverage on anonymity in a variety of cryptographic
contexts. Our results go in two directions.
\begin{itemize}
\item{\bf Feasibility.} We show that anonymous communication
over {\em insecure} channels can be used to implement
unconditionally secure point-to-point channels, and hence
general multi-party protocols with unconditional security in the
presence of an honest majority. In contrast, anonymity cannot be
generally used to obtain unconditional security when there is no
honest majority.
\item{\bf Efficiency.} We show that anonymous channels can yield
substantial efficiency improvements for several natural secure
computation tasks. In particular, we present the first solution
to the problem of private information retrieval (PIR) which can
handle multiple users while being close to optimal with respect
to {\em both} communication and computation. A key observation
that underlies these results is that {\em local randomization}
of inputs, via secret-sharing, when combined with the {\em
global mixing} of the shares, provided by anonymity, allows to
carry out useful computations on the inputs while keeping the
inputs private.
\end{itemize}

2004

EPRINT

On the Limitations of Universally Composable Two-Party Computation Without Set-up Assumptions
Abstract

The recently proposed {\em universally composable {\em (UC)} security} framework for analyzing security of cryptographic protocols provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when run concurrently with arbitrary other protocols. It has been shown that if a majority of the parties are honest, then universally composable protocols exist for essentially any cryptographic task in the {\em plain model} (i.e., with no setup assumptions beyond that of authenticated communication). When honest majority is not guaranteed, general feasibility results are known only given trusted set-up, such as in the common reference string model. Only little was known regarding the existence of universally composable protocols in the plain model without honest majority, and in particular regarding the important special case of two-party protocols.
We study the feasibility of universally composable two-party {\em function evaluation} in the plain model. Our results show that in this setting, very few functions can be securely computed in the
framework of universal composability. We demonstrate this by providing broad impossibility results that apply to large classes of deterministic and probabilistic functions. For some of these classes, we also present full characterizations of what can and cannot be securely realized in the framework of universal composability. Specifically, our characterizations are for the classes of deterministic functions in which (a) both parties receive the same output, (b) only one party receives output, and (c) only one party has input.

2003

EUROCRYPT

2003

EPRINT

Efficient Multi-Party Computation over Rings
Abstract

Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite {\em fields}. We are motivated by two limitations of these techniques:
{\sc Generality.} Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures).
{\sc Efficiency.} The best known {\em constant-round} protocols do not efficiently scale even to the case of large finite fields.
Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite {\em ring}, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a {\em black-box access} to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function.

2000

EUROCRYPT

1998

EPRINT

Randomness versus Fault-Tolerance
Abstract

We investigate the relations between two major requirements of multiparty
protocols: {\em fault tolerance} (or {\em resilience}) and {\em randomness}.
Fault-tolerance is measured in terms of the maximum number of colluding faulty
parties, t, that a protocol can withstand and still maintain the privacy of the inputs and the correctness of the outputs (of the honest parties). Randomness
is measured in terms of the total number of random bits needed by the parties
in order to execute the protocol.
Previously, the upper bound on the amount of randomness required by general
constructions for securely computing any non-trivial function f was polynomial
both in $n$, the total number of parties, and the circuit-size C(f). This was
the state of knowledge even for the special case t=1 (i.e., when there is at
most one faulty party). In this paper, we show that for any linear-size
circuit, and for any number t < n/3 of faulty parties, O(poly(t) * log n)
randomness is sufficient. More generally, we show that for any function f
with circuit-size C(f), we need only O(poly(t) * log n + poly(t) * C(f)/n)
randomness in order to withstand any coalition of size at most t.
Furthermore, in our protocol only t+1 parties flip coins and the rest of
the parties are deterministic. Our results generalize to the case of adaptive
adversaries as well.

1997

EPRINT

Protecting Data Privacy in Private Information Retrieval Schemes
Abstract

Private Information Retrieval (PIR) schemes allow a user to retrieve the
i-th bit of a data string x, replicated in k>=2 databases, while keeping
the value of i private. The main cost measure for such a scheme is its
communication complexity.
We study PIR schemes where in addition to the user's privacy we require
data privacy. That is, in every invocation of the retrieval protocol the
user learns exactly a single physical bit of x and no other information.
Further, we require that even a dishonest user would not learn more than a
single physical data bit.
We present general transformations that allow translating PIR schemes
satisfying certain properties into PIR schemes that respect data privacy
as well, with a small penalty in the communication complexity. Using our
machinery we are able to translate currently known PIR solutions into
schemes satisfying the newly introduced, stronger privacy constraint. In
particular we get: a k-database scheme of complexity
O(log(n) n^{1/(2k-1)}) for every k>=2; an O(log(n))-database scheme of
poly-logarithmic complexity; a 2-database computational PIR of complexity
O(n^c), for every constant c>0. All these require only a single
round of interaction.

#### Program Committees

- Eurocrypt 2020
- TCC 2018
- Eurocrypt 2017
- TCC 2016 (Program chair)
- TCC 2014
- Crypto 2013
- Crypto 2010
- TCC 2008
- TCC 2006
- Eurocrypt 2005
- Crypto 2003
- PKC 2002

#### Coauthors

- Shweta Agrawal (2)
- Benny Applebaum (4)
- Amos Beimel (4)
- Alex Biryukov (2)
- Dan Boneh (2)
- Ran Canetti (6)
- Benny Chor (3)
- Ronald Cramer (2)
- Yevgeniy Dodis (1)
- Serge Fehr (2)
- Ariel Gabizon (1)
- Sanjam Garg (1)
- Rosario Gennaro (1)
- Mihály Geréb-Graus (1)
- Oded Goldreich (2)
- Iftach Haitner (1)
- Shai Halevi (3)
- Danny Harnik (2)
- William E. Skeith III (2)
- Yuval Ishai (31)
- Jonathan Katz (1)
- Ranjit Kumaresan (2)
- Yehuda Lindell (6)
- Nikolaos Makriyannis (1)
- Sigurd Meldgaard (2)
- Tamer Mour (1)
- Varun Narayanan (2)
- Jesper Buus Nielsen (1)
- Pnina Nissim (1)
- Claudio Orlandi (1)
- Rafail Ostrovsky (12)
- Anat Paskin (1)
- Anat Paskin-Cherniavsky (3)
- Erez Petrank (3)
- Vinod Prabhakaran (1)
- Manoj Prabhakaran (5)
- Vinod M. Prabhakaran (1)
- Emmanuel Prouff (1)
- Tal Rabin (3)
- Alon Rosen (2)
- Adi Rosén (4)
- Amit Sahai (7)
- Adrian Thillard (1)
- Damien Vergnaud (1)
- Brent Waters (1)
- Jürg Wullschleger (1)
- Ching-Hua Yu (1)