All reports by Author Eyal Kushilevitz:

__
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

__
TR17-008
| 14th January 2017
__

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

__
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

__
TR12-058
| 5th May 2012
__

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

Revisions: 1

__
TR96-059
| 12th November 1996
__

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz#### A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

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

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

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

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

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

This paper solves the open problem of exact learning

geometric objects bounded by hyperplanes (and more generally by any constant

degree algebraic surfaces) in the constant

dimensional space from equivalence queries only (i.e., in the on-line learning

model).

We present a novel approach that allows, under ...
more >>>