All reports by Author Omer Reingold:

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

Revisions: 1

__
TR20-176
| 26th November 2020
__

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona#### Outcome Indistinguishability

__
TR18-112
| 5th June 2018
__

Raghu Meka, Omer Reingold, Avishay Tal#### Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

__
TR18-031
| 15th February 2018
__

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff#### On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

__
TR18-022
| 1st February 2018
__

Omer Reingold, Guy Rothblum, Ron Rothblum#### Efficient Batch Verification for UP

__
TR17-171
| 6th November 2017
__

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

__
TR16-061
| 17th April 2016
__

Omer Reingold, Ron Rothblum, Guy Rothblum#### Constant-Round Interactive Proofs for Delegating Computation

Revisions: 2

__
TR13-086
| 13th June 2013
__

Omer Reingold, Thomas Steinke, Salil Vadhan#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

__
TR12-123
| 28th September 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan#### Better pseudorandom generators from milder pseudorandom restrictions

__
TR12-060
| 16th May 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold#### DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

__
TR11-106
| 6th August 2011
__

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan#### The Limits of Two-Party Differential Privacy

__
TR11-068
| 27th April 2011
__

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder#### Balls and Bins: Smaller Hash Families and Faster Evaluation

__
TR10-176
| 15th November 2010
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman#### Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

__
TR10-089
| 26th May 2010
__

Iftach Haitner, Omer Reingold, Salil Vadhan#### Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

__
TR09-045
| 20th May 2009
__

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee#### Inaccessible Entropy

__
TR08-045
| 23rd April 2008
__

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Dense Subsets of Pseudorandom Sets

__
TR07-038
| 23rd April 2007
__

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev#### Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

__
TR07-030
| 29th March 2007
__

Kai-Min Chung, Omer Reingold, Salil Vadhan#### S-T Connectivity on Digraphs with a Known Stationary Distribution

__
TR06-096
| 10th August 2006
__

Iftach Haitner, Omer Reingold#### A New Interactive Hashing Theorem

__
TR06-002
| 4th January 2006
__

Eyal Kaplan, Moni Naor, Omer Reingold#### Derandomized Constructions of k-Wise (Almost) Independent Permutations

__
TR05-135
| 19th November 2005
__

Iftach Haitner, Danny Harnik, Omer Reingold#### On the Power of the Randomized Iterate

__
TR05-061
| 15th June 2005
__

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma#### On the Error Parameter of Dispersers

__
TR05-022
| 19th February 2005
__

Omer Reingold, Luca Trevisan, Salil Vadhan#### Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

__
TR04-094
| 10th November 2004
__

Omer Reingold#### Undirected ST-Connectivity in Log-Space

__
TR03-060
| 7th September 2003
__

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen#### Completeness in Two-Party Secure Computation - A Computational View

__
TR01-064
| 10th September 2001
__

Moni Naor, Omer Reingold, Alon Rosen#### Pseudo-Random Functions and Factoring

__
TR01-018
| 23rd February 2001
__

Omer Reingold, Salil Vadhan, Avi Wigderson#### Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

__
TR00-059
| 11th August 2000
__

Omer Reingold, Ronen Shaltiel, Avi Wigderson#### Extracting Randomness via Repeated Condensing

__
TR99-046
| 17th November 1999
__

Ran Raz, Omer Reingold, Salil Vadhan#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

__
TR97-061
| 12th November 1997
__

Eli Biham, Dan Boneh, Omer Reingold#### Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

__
TR97-005
| 17th February 1997
__

Moni Naor, Omer Reingold#### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

__
TR95-045
| 4th September 1995
__

Moni Naor, Omer Reingold#### Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

Raghu Meka, Omer Reingold, Avishay Tal

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

Omer Reingold, Guy Rothblum, Ron Rothblum

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

Omer Reingold, Ron Rothblum, Guy Rothblum

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>

Omer Reingold, Thomas Steinke, Salil Vadhan

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold

Given a DNF formula $f$ on $n$ variables, the two natural size measures are the number of terms or size $s(f)$, and the maximum width of a term $w(f)$. It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our ... more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

We put forth a new computational notion of entropy, which measures the

(in)feasibility of sampling high entropy strings that are consistent

with a given protocol. Specifically, we say that the i'th round of a

protocol (A, B) has _accessible entropy_ at most k, if no

polynomial-time strategy A^* can generate ...
more >>>

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

A theorem of Green, Tao, and Ziegler can be stated (roughly)

as follows: if R is a pseudorandom set, and D is a dense subset of R,

then D may

be modeled by a set M that is dense in the entire domain such that D and

more >>>

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

Kai-Min Chung, Omer Reingold, Salil Vadhan

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>

Iftach Haitner, Omer Reingold

Interactive hashing, introduced by Naor et al. [NOVY98], plays

an important role in many cryptographic protocols. In particular, it

is a major component in all known constructions of

statistically-hiding commitment schemes and of zero-knowledge

arguments based on general one-way permutations and on one-way

functions. Interactive hashing with respect to a ...
more >>>

Eyal Kaplan, Moni Naor, Omer Reingold

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

Iftach Haitner, Danny Harnik, Omer Reingold

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Optimal dispersers have better dependence on the error than

optimal extractors. In this paper we give explicit disperser

constructions that beat the best possible extractors in some

parameters. Our constructions are not strong, but we show that

having such explicit strong constructions implies a solution

to the Ramsey graph construction ...
more >>>

Omer Reingold, Luca Trevisan, Salil Vadhan

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

Omer Reingold

We present a deterministic, log-space algorithm that solves

st-connectivity in undirected graphs. The previous bound on the

space complexity of undirected st-connectivity was

log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and

Zhou. As undirected st-connectivity is

complete for the class of problems solvable by symmetric,

non-deterministic, log-space computations (the class SL), ...
more >>>

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate

f(x,y) in a manner where neither party learns ``more than is necessary". A rich body of work deals with the study of completeness for secure ...
more >>>

Moni Naor, Omer Reingold, Alon Rosen

Factoring integers is the most established problem on which

cryptographic primitives are based. This work presents an efficient

construction of {\em pseudorandom functions} whose security is based

on the intractability of factoring. In particular, we are able to

construct efficient length-preserving pseudorandom functions where

each evaluation requires only a ...
more >>>

Omer Reingold, Salil Vadhan, Avi Wigderson

The main contribution of this work is a new type of graph product, which we call the zig-zag

product. Taking a product of a large graph with a small graph, the resulting graph inherits

(roughly) its size from the large one, its degree from the small one, and ...
more >>>

Omer Reingold, Ronen Shaltiel, Avi Wigderson

On an input probability distribution with some (min-)entropy

an {\em extractor} outputs a distribution with a (near) maximum

entropy rate (namely the uniform distribution).

A natural weakening of this concept is a condenser, whose

output distribution has a higher entropy rate than the

input distribution (without losing

much of ...
more >>>

Ran Raz, Omer Reingold, Salil Vadhan

We give explicit constructions of extractors which work for a source of

any min-entropy on strings of length n. These extractors can extract any

constant fraction of the min-entropy using O(log^2 n) additional random

bits, and can extract all the min-entropy using O(log^3 n) additional

random bits. Both of these ...
more >>>

Eli Biham, Dan Boneh, Omer Reingold

The Diffie-Hellman key-exchange protocol may naturally be

extended to k>2 parties. This gives rise to the generalized

Diffie-Hellman assumption (GDH-Assumption).

Naor and Reingold have recently shown an efficient construction

of pseudo-random functions and reduced the security of their

construction to the GDH-Assumption.

In this note, we ...
more >>>

Moni Naor, Omer Reingold

Luby and Rackoff showed a method for constructing a pseudo-random

permutation from a pseudo-random function. The method is based on

composing four (or three for weakened security) so called Feistel

permutations each of which requires the evaluation of a pseudo-random

function. We reduce somewhat the complexity ...
more >>>

Moni Naor, Omer Reingold

A pseudo-random function is a fundamental cryptographic primitive

that is essential for encryption, identification and authentication.

We present a new cryptographic primitive called pseudo-random

synthesizer and show how to use it in order to get a

parallel construction of a pseudo-random function.

We show an $NC^1$ implementation of synthesizers ...
more >>>