All reports by Author Amit Sahai:

__
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

__
TR20-126
| 19th August 2020
__

Aayush Jain, Huijia Lin, Amit Sahai#### Indistinguishability Obfuscation from Well-Founded Assumptions

__
TR18-200
| 29th November 2018
__

Ashutosh Kumar, Raghu Meka, Amit Sahai#### Leakage-Resilient Secret Sharing

__
TR18-009
| 9th January 2018
__

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

__
TR17-100
| 7th June 2017
__

Dakshita Khurana, Amit Sahai#### How to Achieve Non-Malleability in One or Two Rounds

__
TR13-143
| 19th October 2013
__

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

Revisions: 1

__
TR10-020
| 19th February 2010
__

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

__
TR07-053
| 27th April 2007
__

Jens Groth, Amit Sahai#### Efficient Non-interactive Proof Systems for Bilinear Groups

__
TR06-110
| 15th August 2006
__

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai#### Improved Algorithms for Optimal Embeddings

__
TR05-097
| 31st August 2005
__

Jens Groth, Rafail Ostrovsky, Amit Sahai#### Perfect Non-Interactive Zero Knowledge for NP

__
TR05-096
| 26th August 2005
__

Boaz Barak, Amit Sahai#### How To Play Almost Any Mental Game Over The Net --- Concurrent Composition via Super-Polynomial Simulation

__
TR05-093
| 24th August 2005
__

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan#### Concurrent Zero Knowledge without Complexity Assumptions

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

__
TR00-084
| 6th November 2000
__

Salil Vadhan, Amit Sahai#### A Complete Problem for Statistical Zero Knowledge

__
TR99-013
| 28th May 1999
__

Oded Goldreich, Amit Sahai, Salil Vadhan#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

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

Aayush Jain, Huijia Lin, Amit Sahai

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:

Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, and the parameters $\ell,k,n$ below ... more >>>

Ashutosh Kumar, Raghu Meka, Amit Sahai

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some ``leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an ... more >>>

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

Dakshita Khurana, Amit Sahai

Despite over 25 years of research on non-malleable commitments in the plain model, their round complexity has remained open. The goal of achieving non-malleable commitment protocols with only one or two rounds has been especially elusive. Pass (TCC 2013, CC 2016) captured this difficulty by proving important impossibility results regarding ... 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 >>>

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

Jens Groth, Amit Sahai

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as ... more >>>

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

In the last decade, the notion of metric embeddings with

small distortion received wide attention in the literature, with

applications in combinatorial optimization, discrete mathematics, functional

analysis and bio-informatics. The notion of embedding is, given two metric

spaces on the same number of points, to find a bijection that minimizes

more >>>

Jens Groth, Rafail Ostrovsky, Amit Sahai

Non-interactive zero-knowledge (NIZK) systems are

fundamental cryptographic primitives used in many constructions,

including CCA2-secure cryptosystems, digital signatures, and various

cryptographic protocols. What makes them especially attractive, is

that they work equally well in a concurrent setting, which is

notoriously hard for interactive zero-knowledge protocols. However,

while for interactive zero-knowledge we ...
more >>>

Boaz Barak, Amit Sahai

We construct a secure protocol for any multi-party functionality

that remains secure (under a relaxed definition of security) when

executed concurrently with multiple copies of itself and other

protocols. We stress that we do *not* use any assumptions on

existence of trusted parties, common reference string, honest

majority or synchronicity ...
more >>>

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

We provide <i>unconditional</i> constructions of <i>concurrent</i>

statistical zero-knowledge proofs for a variety of non-trivial

problems (not known to have probabilistic polynomial-time

algorithms). The problems include Graph Isomorphism, Graph

Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a

restricted version of Statistical Difference, and approximate

versions of the (<b>coNP</b> forms of the) Shortest Vector ...
more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Salil Vadhan, Amit Sahai

We present the first complete problem for SZK, the class of (promise)

problems possessing statistical zero-knowledge proofs (against an

honest verifier). The problem, called STATISTICAL DIFFERENCE, is to

decide whether two efficiently samplable distributions are either

statistically close or far apart. This gives a new characterization

of SZK that makes ...
more >>>

Oded Goldreich, Amit Sahai, Salil Vadhan

We extend the study of non-interactive statistical zero-knowledge

proofs. Our main focus is to compare the class NISZK of problems

possessing such non-interactive proofs to the class SZK of problems

possessing interactive statistical zero-knowledge proofs. Along these

lines, we first show that if statistical zero knowledge is non-trivial

then so ...
more >>>