Yehuda Lindell, Benny Pinkas

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

Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

Many approximation algorithms have been presented in the last decades

for hard search problems. The focus of this paper is on cryptographic

applications, where it is desired to design algorithms which do not

leak unnecessary information. Specifically, we are interested in

private approximation algorithms -- efficient algorithms ...
more >>>

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman

Let $G:\{0,1\}^n\to\{0,1\}^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is $(k,q)$-robust if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ ... more >>>

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

Benny Applebaum, Jonathan Avron, Christina Brzuska

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a ... more >>>

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>