All reports by Author Yuval Ishai:

__
TR23-213
| 31st December 2023
__

Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai#### Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness

__
TR23-091
| 18th June 2023
__

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan#### Succinct Computational Secret Sharing

__
TR21-093
| 1st July 2021
__

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan#### Bounded Indistinguishability for Simple Sources

Revisions: 1

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

Revisions: 3

__
TR17-008
| 14th January 2017
__

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan#### Low-Complexity Cryptographic Hash Functions

__
TR15-182
| 13th November 2015
__

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson#### Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

__
TR15-094
| 10th June 2015
__

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi#### On Public Key Encryption from Noisy Codewords

__
TR15-045
| 1st April 2015
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

__
TR13-143
| 19th October 2013
__

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman#### Robust Pseudorandom Generators

Revisions: 1

__
TR13-107
| 7th August 2013
__

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum#### Efficient Multiparty Protocols via Log-Depth Threshold Formulae

__
TR12-058
| 5th May 2012
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### How to Garble Arithmetic Circuits

Revisions: 1

__
TR10-020
| 19th February 2010
__

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai#### Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

__
TR01-015
| 9th February 2001
__

Amos Beimel, Yuval Ishai#### Information-Theoretic Private Information Retrieval: A Unified Construction

Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai

The existence of "unstructured" hard languages in $\text{NP}\cap\text{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\text{P}$ is separated from $\text{NP}\cap\text{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\text{NP}\cap\text{coNP}$ can be constructed in a black-box way ... more >>>

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan

A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.

The question of minimizing the (largest) share size ... more >>>

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et ... more >>>

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set ... more >>>

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>>

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... 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 >>>

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves

security against a single corrupted party. Such protocols are typically easy

to construct as they may employ techniques that do not ...
more >>>

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$

into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each

input bit, such that $\hat{C}$ together with the $n$ keys

corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$.

The garbled circuit ...
more >>>

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

Amos Beimel, Yuval Ishai

A Private Information Retrieval (PIR) protocol enables a user to

retrieve a data item from a database while hiding the identity of the

item being retrieved. In a $t$-private, $k$-server PIR protocol the

database is replicated among $k$ servers, and the user's privacy is

protected from any collusion of up ...
more >>>