SPECIAL ISSUE ON WORST-CASE VERSUS AVERAGE-CASE COMPLEXITY (2009)
Average-case complexity, which examines the tractability of computational problems on ‘random instances, ’ is a major topic in complexity theory with at least two distinct motivations. On one...
Cryptography in Constant Parallel Time (2009)
Omer Reingold, Ronny Roth, Amir Shpilka, Amnon Ta-shma, Enav Weinreb, Emanuele Viola, ...
Acknowledgements I would like to sincerely thank my supervisors Yuval Ishai and Eyal Kushilevitz. During the last years, I have spent many hours in conversations with Yuval and Eyal. These long...
Extended Abstract, Oded Goldreich, Amit Sahai, Salil Vadhan
Abstract. We extend the study of non-interactive statistical zeroknowledge proofs. Our main focus is to compare the class NISZK of problems possessing such non-interactive proofs to the class SZK of...
On Proximity Oblivious Testing (2009)
We initiate a systematic study of a special type of property testers. These testers consist of repeating a basic test for a number of times that depends on the proximity parameter, whereas the basic...
Hierarchy Theorems for Property Testing (2009)
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
Referring to the query complexity of property testing, we prove the existence of a rich hierarchy of corresponding complexity classes. That is, for any relevant function q, we prove the existence of...
Oded Goldreich, Siltnb Micali, Avi Wigderson
We present a polynomial-time algorithm that, given ss a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that ‘leaks...
PROFESSIONAL EXPERIENCE TEACHING (2008)
Curriculum Vitae Yoad Lustig, Advisor Prof, Orna Kupferman, Advisor Prof, Oded Goldreich
CONTACT INFORMATION RESEARCH
A Randomized Protocol for Signing Contracts (2008)
Ellis Horowitz, Shimon Even, Oded Goldreich, Abraham Lempel
ABSTRACT: Randomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a Z-out-of-2 oblivious transfer subprotocol which is axiomatically defined....
Proposed running head: The Complexity of Radio Broadcast Mailing address: (2008)
Reuven Bar-yehuda, Oded Goldreich, Alon Itai, Oded Goldreich
ABSTRACT- 3-The time-complexity of deterministic and randomized protocols for achieving broadcast (distributing a message from a source to all other nodes) in arbitrary multi-hop radio net-works is...
ABSTRACT On Basing One-Way Functions on NP-Hardness (2008)
Adi Akavia, Shafi Goldwasser, Oded Goldreich, Dana Moshkovitz
We consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a...
A Sublinear Bipartiteness Tester, Oded Goldreich, Dana Ron
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length d, and the...
Inductive and Co-inductive Techniques (2008)
Miklos Ajtai, Oded Goldreich, Mark Jerrum, Noam Nisan, Er Razborov
WelcometothefirstissueoftheBRICSnewsletter.Itspurposeistoinformyouofappointments, publications,coursesandotheractivitieswithin BRICS.Furtherdetailscanbeobtainedbycontactingtheaddressesbelow....
Algorithmic aspects of property testing in the dense graphs model. ECCC (2008)
In this paper we consider two basic questions regarding the query complexity of testing graph properties in the adjacency matrix model. The first question refers to the relation between adaptive and...
Hierarchy Theorems for Property Testing (2008)
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
Referring to the query complexity of property testing, we prove the existence of a rich hierarchy of corresponding complexity classes. That is, for any relevant function q, we prove the existence of...
Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is...
Computational Randomness (2007)
A recent behaviouristic approach to randomness is surveyed. In this approach a probability distribution is considered "pseudorandom" if no "efficient procedure" can distinguish it...
On the Number of Monochromatic Close Pairs of Beads in a Rosary (2007)
September Revised May, Oded Goldreich
We consider the following problem: Let r be a n-bead rosary with m white beads and n \Gamma m black beads. Let t be an integer, t n. Denote by MC t (r) the number of pairs, of monochromatic beads...
Bpp Ph, Oded Goldreich, Rehovot Israel, David Zuckerman
We provide another proof of the Sipser--Lautemann Theorem by which BPP ` MA (` PH). The current proof is based on strong results regarding the amplification of BPP , due to Zuckerman. Given these...
A Note on Testing Monotonicity (2007)
Oded Goldreich, Shafi Goldwasser, Dana Ron
We show that under a certain conjecture regarding the boolean lattice, there exists an efficient algorithm for testing whether a function is monotone or ffl-far from monotone. Note: The said...
Eccc Tr Electronic, Oded Goldreich, Rehovot Israel, Shafi Goldwasser
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of p n, of optimization problems in integer lattices; specifically, the closest...
Simple Constructions of Almost (2007)
Wise Independent Random, Noga Alon, Oded Goldreich, Johan Hastad
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
On Universal Learning Algorithms (2007)
We observe that there exists a universal learning algorithm which PAC-learns every concept class within complexity which is linearly related to the complexity of the best learning algorithm for this...
Simple Constructions of Almost (2007)
Wise Independent, Noga Alon, Oded Goldreich, Johan Hastad
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
On Universal Learning Algorithms (2007)
We observe that there exists a universal learning algorithm that pac-learns every concept class within complexity that is linearly related to the complexity of the best learning algorithm for this...
Theory of Computing: A Scientific Perspective (2007)
Preliminary Version, Oded Goldreich, Avi Wigderson
We are gravely concerned with the contents, spirit and recommendations in the Aho et. al. Report on the Theory of Computing (TOC). This report "assesses the current goals and directions of the...
Oded Goldreich, Avi Wigderson, Givat Ram
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
Ran Canetti, Oded Goldreich, Shai Halevi
the random-oracle methodology as applied to length-restricted signature schemes
Oded Goldreich, Rehovot Israel
Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, non-codewords are rejected with probability...
More than ten years have elapsed since the first completeness theorems for two-party and multi-party fault-tolerant computation have been announced (by Yao and Goldreich, Micali and Wigderson,...
On the Implementation of Huge Random Objects (Preliminary Version) (2007)
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
We initiate a general study of pseudo-random implementations of huge random objects, and apply it to a few areas in which random objects occur naturally. For example, a random object being considered...
On the possibility of basing Cryptography (2007)
Oded Goldreich, Rehovot Israel, Shafi Goldwasser
on the assumption that P 6 = NP
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f: f0; 1g n 7! f0; 1g at arguments of its choice, the test always accepts...
Preface to Special Issue on General Secure Multi-Party Computation (2007)
More than a decade has passed since general results concerning secure two-party and multiparty computations were first announced in [15, 24, 16] (see details in [14]). In a nutshell, assuming the...
Interleaved Zero-Knowledge (A Preliminary Version) (2007)
Oded Goldreich, Shafi Goldwasser, Silvio Micali
We introduce the notion of Interleaved Zero-Knowledge (iZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge, in a way suitable for...
Ran Canetti, Uri Feige, Oded Goldreich, Moni Naor
A fundamental problem in designing secure multi-party protocols is how to deal with adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the...
, and approximating the (2007)
This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) the approximability of NP-optimization problems. The emphasis is on proving tight...
for Bounded Degree Graphs (2007)
A Sublinear, Bipartiteness Tester, Oded Goldreich, Dana Ron
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length d, and the...
Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
We prove that if a linear error-correcting code C: f0; 1g
Oded Goldreich, Rehovo Israel, To Dana
Several years ago, Shaft Goldwasser and myself have decided to write together' a book titled "Foundations of Cryptography". In a first burst of energy, Ive written most of the...
Oded Goldreich, Yoad Lustig, Moni Naor
Previous treatments of encryption schemes secure under chosen ciphertext attacks (CCA) has referred to the technical definition of indistinguishability of encryptions. As in the case of security...
Oded Goldreich, Yoad Lustig, Moni Naor
We consider the security of multiple and possibly related plaintexts in the context of a chosen ciphertext attack. That is the attacker in addition and concurrently to obtaining encryptions of...
Noga Alon, Oded Goldreich, Rehovot Israel, Yishay Mansour
We say that a distribution over f0; 1g n is almost k-wise independent if its restriction to every k coordinates results in a distribution that is close to the uniform distribution. A natural question...
On the (Im)possibility of Obfuscating Programs* (2007)
Boaz Barak I, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhanl, ...
Informally, an obfuscator (9 is an (efficient, probabilistic) "compiler " that takes as input a program (or circuit) P and produces a new program (9(P) that has the same...
Oded Goldreich, Rehovot Israel
Locally testable codes are error-correcting codes that admit very ecient codeword tests. Speci cally, using a constant number of (random) queries, non-codewords are rejected with probability...
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, ...
Informally, an obfuscator O is an (ecient, probabilistic) \compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is...
Interleaved Zero-Knowledge (A Preliminary Version) (2007)
Oded Goldreich, Shafi Goldwasser, Silvio Micali
We introduce the notion of Interleaved Zero-Knowledge (iZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge, in a way suitable for...
On the possibility of basing Cryptography (2007)
Oded Goldreich, Rehovot Israel, Shafi Goldwasser
on the assumption that P 6 = NP
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, ...
Informally, an obfuscator O is an (ecient, probabilistic) \compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is...
Technion Haifa, Israel. (2007)
All known fast randomized Byzantine Agreement (BA) protocols have (rare) infinite runs. We present a method of combining randomized BA protocols of a certain class with any deterministic BA protocol...
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell
Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound...
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, ...
Informally, an obfuscator
A Probabilistic Error-Correcting Scheme (2007)
Scott Decatur, Oded Goldreich, Dana Ron
In the course of research in Computational Learning Theory, we found ourselves in need of an error-correcting encoding scheme for which few bits in the codeword yield no information about the plain...
A Probabilistic Error-Correcting Scheme (2007)
Scott Decatur, Oded Goldreich, Dana Ron
In the course of research in Computational Learning Theory, we found ourselves in need of an error-correcting encoding scheme for which few bits in the codeword yield no information about the plain...
How to use my 1989 Lecture Notes on Encryption, Signatures and Crypto-Protocols (2007)
This document is written to complement my 1989 lecture notes on Encryption, Signatures and Cryptographic Protocols. In it I sketch what I believe should be done when trying to use these notes as part...
Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Salil Vadhan, Ke Yang
Abstract. Informally, an obfuscator O is an (ecient, probabilistic) \compiler " that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality...
Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is...
Free Bits, PCPs and Non-Approximability--- (2007)
Towards Tight Results, Mihir Bellare, Oded Goldreich
This paper continues the investigation of the connection between proof systems and approximation. The emphasis is on proving tight non-approximability results via consideration of measures like the...
from Lattice Reduction Problems (2007)
Public-key Cryptosystems, Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
, and approximating the (2007)
This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) the approximability of NP-optimization problems. The emphasis is on proving tight...
Eli Ben-sasson, Oded Goldreich
Abstract. We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any 2-locally testable code with minimal distance n...
Oded Goldreich, Rehovot Israel
We initiate a systematic study of locally testable codes; that is, error-correcting codes that admit very efficient membership tests. Specifically, these are codes accompanied with tests that make a...
Three Theorems Regarding Testing (2007)
Graph Properties, Oded Goldreich, Luca Trevisan
ABSTRACT: Property testing is a relaxation of decision problems in which it is required to distinguish YES-instances (i.e., objects having a predetermined property) from instances that are far from...
Ran Canetti, Oded Goldreich, Shai Halevi
the random-oracle methodology as applied to length-restricted signature schemes
On Estimating the Average Degree of a Graph (2007)
Oded Goldreich Department, Oded Goldreich, Rehovot Israel, Dana Ron, Department Of Ee{systems
Following Feige, we consider the problem of estimating the average degree of a graph. Using \neighbor queries" as well as \degree queries", we show that the average degree can be...
Almost K-Wise Independence Versus K-Wise Independence (2007)
Noga Alon Sackler, Noga Alon, Oded Goldreich, Rehovot Israel, Yishay Mansour
We say that a distribution over f0; 1g is almost k-wise independent if its restriction to every k coordinates results in a distribution that is close to the uniform distribution. A natural question...
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph...
Randomized Broadcasting in Radio Networks, 1992; (2007)
Reuven Bar-yehuda, Oded Goldreich, Alon Itai, Entry Alon Itai
SYNONYMS: Multi-hop radio networks, ad hoc networks.
Mathematisches Forschungsinstitut Oberwolfach Report No. 31/2007 Complexity Theory (2007)
Joachim Von Zur Gathen, Universität Bonn, Oded Goldreich
Abstract. Computational Complexity Theory is the mathematical study of the intrinsic power and limitations of computational resources like time, space, or randomness. The current workshop focused on...
Randomness and Computation (2006)
The interplay of randomness and computation is at the heart of modern Cryptography and plays a fundamental role in the design of algorithms and in the study of computation at large. Specifically,...
On basing one-way functions on NP-hardness (2006)
Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz
We consider the question of whether it is possible to base the existence of one-way functions on N P-hardness. That is we study the the possibility of reductions from a worst-case N P-hard decision...
Approximating Average Parameters of Graphs (2006)
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph...
Contemplations on Testing Graph Properties (2006)
This note documents two programmatic comments regarding testing graph properties, which I made during the workshop. The first comment advocates paying more attention to the dependence of the tester's...
Session-Key Generation Using Human Passwords Only (2005)
Oded Goldreich, Yehuda Lindell
We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password, and there is no additional setup assumption in the network.
Oded Goldreich, Yehuda Lindell
We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password, and there is no additional setup assumption in the network. Our protocol...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Salil Vadhan
We continue the study of the trade-o between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisability of circuits of size n): 1....
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan
Abstract. We continue the study of the trade-off between the length of probabilistically checkable proofs (PCPs) and their query complexity, establishing the following main results (which refer to...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size n):...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Salil Vadhan
We continue the study of the trade-o between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisability of circuits of size n): 1....
The Power of Verification Queries in Message Authentication and Authenticated Encryption (2004)
Mihir Bellare, Oded Goldreich, Anton Mityagin
This paper points out that, contrary to popular belief, allowing a message authentication adversary multiple verification attempts towards forgery is not equivalent to allowing it a single one, so...
Robust PCPs of proximity, shorter PCPs and applications to coding (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
Abstract We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
Mihir Bellare, Oded Goldreich, Anton Mityagin
This paper points out that, contrary to popular belief, allowing a message authentication adversary multiple verification attempts towards forgery is not equivalent to allowing it a single one, so...
Short PCPs verifiable in polylogarithmic time (2004)
Eli Ben-sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
We show that every language in NP has a probabilistically checkable proof of proximity (i.e., proofs asserting that an instance is “close ” to a member of the language), where the verifier’s...
On the Implementation of Huge Random Objects (2003)
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
We initiate a general study of pseudo-random implementations of huge random objects, and apply it to a few areas in which random objects occur naturally. For example, a random object being considered...
On the Implementation of Huge Random Objects (2003)
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
We initiate a general study of pseudo-random implementations of huge random objects, and apply it to a few areas in which random objects occur naturally. For example, a random object being considered...
Bounds on 2-Query Codeword Testing (2003)
Eli Ben-sasson, Oded Goldreich
We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any 2-locally testable code with minimal distance ffin over a...
Bounds on 2-Query Codeword Testing (2003)
Eli Ben-sasson, Oded Goldreich
We present upper bounds on the size of codes that are locally testable by querying only two input symbols. For linear codes, we show that any 2-locally testable code with minimal distance n over a...
Ran Canetti, Oded Goldreich, Shai Halevi
the random-oracle methodology as applied to length-restricted
On the Implementation of Huge Random Objects (2003)
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
We initiate a general study of pseudo-random implementations of huge random objects, and apply it to a few areas in which random objects occur naturally. For example, a random object being considered...
Noga Alon, Ramat-aviv Israel, Yishay Mansour, Oded Goldreich
We say that a distribution over {0, 1} n is (ɛ, k)-wise independent if its restriction to every k coordinates results in a distribution that is ɛ-close to the uniform distribution. A natural...
Zero-knowledge twenty years after its invention (2002)
Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge...
The GGM Construction does NOT yield Correlation Intractable Function Ensembles (2002)
We consider the function ensembles emerging from the construction of Goldreich, Goldwasser and Micali (GGM), when applied to an arbitrary pseudoramdon generator. We show that, in general, such...
Locally Testable Codes and PCPs of Almost-Linear Length (2002)
Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, non-codewords are rejected with probability...
Concurrent Zero-Knowledge With Timing Revisited (2002)
Oded Goldreich, Rehovot Israel
Following Dwork, Naor, and Sahai (30th STOC, 1998), we consider concurrent execution of protocols in a semi-synchronized network. Specifically, we assume that each party holds a local clock such that...
Universal Arguments and Their Applications (2002)
Boaz Barak, Rehovot Israel, Oded Goldreich
We put forward a new type of computationally-sound proof systems, called universal-arguments, which are related but different from both CS-proofs (as defined by Micali) and arguments (as defined by...
Universal Arguments and Their Applications (2002)
Boaz Barak, Rehovot Israel, Oded Goldreich
We put forward a new type of computationally-sound proof systems, called universal-arguments, which are related but di#erent from both CS-proofs (as defined by Micali) and arguments (as defined by...
Derandomization That is Rarely Wrong From Short Advice That is Typically Good (2002)
For every ffl ? 0, we present a deterministic log-space algorithm that correctly decides undirected graph connectivity on all but at most 2 of the n-vertex graphs. The same holds for every problem in...
1.1.1 The Random Oracle Model............................ 3 (2002)
Ran Canetti, Oded Goldreich, Shai Halevi
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle...
Session-Key Generation using Human Passwords Only (2001)
Oded Goldreich, Yehuda Lindell
We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password. The security guarantee holds with respect to probabilistic polynomial-time...
On the (im)possibility of obfuscating programs (extended abstract (2001)
Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Salil Vadhan, Ke Yang
Abstract. Informally, an obfuscator O is an (efficient, probabilistic) “compiler ” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as...
On the (im)possibility of obfuscating programs (2001)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, ...
Informally, an obfuscator O is an (efficient, probabilistic) “compiler ” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is...
Resettably-Sound Zero-Knowledge and its Applications (2001)
Boaz Barak, Oded Goldreich, Sha Goldwasser, Yehuda Lindell
Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verier to use the same random coins in repeated executions of the protocol. We show that resettably-sound...
Oded Goldreich, Rehovot Israel
Using known results regarding PCP, we present simple proofs of the inapproximability of vertex cover for hypergraphs. Specifically, we show that 1. Approximating the size of the minimum vertex cover...
Resettably-Sound Zero-Knowledge and its Applications (2001)
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell
Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound...
Session-Key Generation using Human Passwords Only (2001)
Oded Goldreich, Rehovot Israel, Yehuda Lindell
We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password. The security guarantee holds with respect to probabilistic polynomial-time...
Session-Key Generation using Human Passwords Only (2001)
Oded Goldreich, Rehovot Israel, Yehuda Lindell
We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password. The security guarantee holds with respect to probabilistic polynomial-time...
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval (2001)
Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan
We prove that if a linear error correcting code C : f0; 1g is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m =...
On the (im)possibility of obfuscating programs (2001)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, ...
Informally, an obfuscator O is an (efficient, probabilistic) “compiler ” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is...
Resettably-Sound Zero-Knowledge and its Applications (2001)
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell
Abstract Resettably-sound proofs and arguments remain sound even when the prover can reset theverifier, and so force it to use the same random coins in repeated executions of the protocol.
Resettably-Sound Zero-Knowledge and its Applications (2001)
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell
Resettably-sound proofs and arguments remain sound even when the prover can reset the verifier, and so force it to use the same random coins in repeated executions of the protocol. We show that...
The Random Oracle Methodology, Revisited (2000)
Canetti, Ran, Goldreich, Oded, Halevi, Shai
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle...
Session-Key Generation using Human Passwords Only (2000)
Oded Goldreich, Yehuda Lindell
We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password. The security guarantee holds with respect to probabilistic polynomial-time...
Resettable zero-knowledge (2000)
Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is...
Candidate one-way functions based on expander graphs (2000)
Oded Goldreich, Rehovot Israel
We suggest a candidate one-way function using combinatorial constructs such as expander graphs. These graphs are used to determine a sequence of small overlapping subsets of input bits, to which a...
Oded Goldreich, Rehovot Israel, Vered Rosen
Assuming the inractability of factoring, we show that the output of the exponentiation modulo a composite function fN;g (x) = g x mod N (where N = P \Delta Q) is pseudorandom, even when its input is...
On testing expansion in bounded-degree graphs (2000)
We consider testing graph expansion in the bounded-degree graph model (as formulated in [1]). Specifically, we refer to algorithms for testing whether the graph has a second eigenvalue bounded above...
Simplified derandomization of BPP using a hitting set generator (2000)
Oded Goldreich, Salil Vadhan, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Simplified derandomization of BPP using a hitting set generator (2000)
Oded Goldreich, Salil Vadhan, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Simplified derandomization of BPP using a hitting set generator (2000)
Oded Goldreich Salil, Oded Goldreich, Salil Vadhan, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
We postulate that a distribution is pseudorandom if it cannot be told apart from the uniform distribution by any efficient procedure. This yields a robust definition of pseudorandom generators as...
Improved Testing Algorithms for Monotonicity (2000)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f : \Sigma n 7! \Xi, where \Sigma and \Xi are finite ordered sets, the...
Computational Complexity (2000)
Oded Goldreich, Rehovot Israel
Introduction Computational Complexity (a.k.a Complexity Theory) is a central field of Computer Science 1 with a remarkable list of celebrated achievements as well as a very vibrant research activity....
On Pseudorandomness with respect to Deterministic Observers (2000)
Oded Goldreich, Rehovot Israel, Avi Wigderson
In the theory of pseudorandomness, potential (uniform) observers are modeled as probabilistic polynomial-time machines. In fact many of the central results in that theory are proven via probabilistic...
Candidate One-Way Functions Based on Expander Graphs (2000)
Oded Goldreich, Israel Odedgoldreich
We suggest a candidate one-way function using combinatorial constructs such as expander graphs. These graphs are used to determine a sequence of small overlapping subsets of input bits, to which a...
Uniform Generation of NP-Witnesses Using an NP-Oracle (2000)
Mihir Bellare, Oded Goldreich, Erez Petrank
A Uniform Generation procedure for NP is an algorithm which given any input in a xed NP-language, outputs a uniformly distributed NP-witness for membership of the input in the language. We present a...
microsoft.public.platformsdk.security: Re: Encrypt a Dll (2000)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Sali Vadhan, Benjamin Lynn, ...
> Valery, i'm reading your blog posts.. i want this list of papers, i'm very> glad with your help.. thanks!> VP
Computational sample complexity (1999)
Scott E. Decatur, Oded Goldreich, Dana Ron
In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information...
Improved testing algorithms for monotonicity (1999)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f: \Sigma n 7! \Xi, where \Sigma and \Xi are finite ordered sets, the test...
Improved derandomization of BPP using a hitting set generator (1999)
Oded Goldreich, Rehovot Israel, Avi Wigderson
A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily...
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich
The input to the Graph Clustering Problem consists of a sequence of integers m 1;:::; m t and a sequence of P t i=1 m i graphs. The question is whether the equivalence classes, under the graph...
Chinese remaindering with errors (1999)
z The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1; : : : ; p k, provided m! Q k i=1 p i. Thus the residues...
Chinese remaindering with errors (1999)
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1; : : : ; p k, provided m! Q k i=1 p i. Thus the residues...
Chinese remaindering with errors (1999)
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p1; : : : ; pk, provided m! Q k i=1 p i. Thus the residues of...
Computational Indistinguishability: A Sample Hierarchy (1999)
We consider the existence of pairs of probability ensembles which may be efficiently distinguished from each other given k samples but cannot be efficiently distinguished given k 0 samples. It is...
Computational Indistinguishability: A Sample Hierarchy (1999)
We consider the existence of pairs of probability ensembles which may be efficiently distinguished given k samples but cannot be efficiently distinguished given k 0 ! k samples. It is well known that...
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of (1999)
Niszk Oded Goldreich, 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...
Deterministic Amplification of Space-Bounded Probabilistic Algorithms (1999)
Ziv Bar-yossef, Oded Goldreich, Avi Wigderson
This paper initiates the study of deterministic amplification of space-bounded probabilistic algorithms. The straightforward implementations of known amplification methods cannot be used for such...
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of NISZK (1999)
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...
Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
We show that given oracle access to a subroutine which returns approximate closest vectors in a lattice, one may find in polynomial-time approximate shortest vectors in a lattice. The level of...
Improved Testing Algorithms for Monotonicity (1999)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f : \Sigma n 7! \Xi, where \Sigma and \Xi are finite ordered sets, the...
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK (1999)
We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pair of circuits, and YES instances (resp., NO instances) are such pairs in which the first (resp.,...
Computational Indistinguishability: A Sample Hierarchy (1999)
We consider the existence of pairs of probability ensembles which may be efficiently distinguished from each other given k samples but cannot be efficiently distinguished given k 0 ! k samples. It is...
Improved testing algorithms for monotonicity (1999)
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f: Σ n ↦ → Ξ, where Σ and Ξ are finite ordered sets, the test...
The current proof of the PCP Theorem (i.e., N P = PCP(log, O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the...
all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the...
Free bits, PCPs, and non-approximability -- towards tight results (1998)
Mihir Bellare, Oded Goldreich, Madhu Sudan
The first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for NP using logarithmic randomness and two amortized free...
The Foundations of Modern Cryptography (1998)
In our opinion, the Foundations of Cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. In this essay, we...
The Random Oracle Methodology, Revisited (1998)
Ran Canetti, Oded Goldreich, Shai Halevi
We take a formal look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes which result from implementing the random oracle by...
Efficient Approximation of Product Distributions (1998)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces that approximate the joint distribution of general random variables. Previous work on efficient constructions concentrate on...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Secure Multi-Party Computation (1998)
Contents 1 Introduction and Preliminaries 4 1.1 A Tentative Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.1.1 Overview of the Definitions : : : : : : : : : : : :...
Combinatorial Property Testing (a survey) (1998)
We consider the question of determining whether a given object has a predetermined property or is "far" from any object having the property. Specifically, objects are modeled by functions,...
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK (1998)
We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pairs of circuits, and yes instances (resp., no instances) are such pairs in which the first (resp.,...
Oded Goldreich, Amit Sahai, Salil Vadhan
We further extend the study, recently initiated by De-Santis et. al. (ICALP98) of non-interactive statistical zero-knowledge proofs. Our main focus is to compare the class NISZK of problems...
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge (1998)
Oded Goldreich, Amit Sahai, Salil Vadhan
We show how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof system which is statistical zero-knowledge with respect to...
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate rights to himself, i.e., to other public keys he owns, but may not safely delegate those rights to others, i.e., to their public keys. In...
Chinese Remaindering with Errors (1998)
Oded Goldreich, Dana Ron, Madhu Sudan
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1 ; : : : ; p k , provided m ! Q k i=1 p i . Thus the...
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge (1998)
Oded Goldreich, Amit Sahai, Salil Vadhan
We show how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof systemwhich is statistical zero-knowledgewith respect to...
Computational Indistinguishability: Algorithms vs. Circuits (1998)
Oded Goldreich, Rehovot Israel, Bernd Meyer
We present a simple proof to the existence of a probability ensemble with tiny support which cannot be distinguished from the uniform ensemble by any recursive computation. Since the support is tiny...
On the Circuit Complexity of Perfect Hashing (1998)
Oded Goldreich, Rehovot Israel, Avi Wigderson, Givat Ram
We consider the size of circuits which perfectly hash an arbitrary subset S ae f0; 1g n of cardinality 2 k into f0; 1g m . We observe that, in general, the size of such circuits is exponential in 2k...
On the Limits of Non-Approximability of Lattice Problems (1998)
Oded Goldreich, Rehovot Israel, Shafi Goldwasser
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of p n, of optimization problems in integer lattices; specifically, the closest...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f : f0; 1g n 7! f0; 1g at arguments of its choice, the test always accepts...
Property Testing and its Connection to Learning and Approximation (1998)
Oded Goldreich, Shafi Goldwasser, Dana Ron
In this paper, we consider the question of determining whether a function f has property P or is ffl-far from any function with property P. A property testing algorithm is given a sample of the value...
Self-Delegation with Controlled Propagation -- or -- What If You Lose Your Laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate rights to himself, i.e., to other public keys he owns, but may not safely delegate those rights to others, i.e., to their public keys. In...
A Sublinear Bipartiteness Tester for Bounded Degree Graphs (1998)
A Sublinear, Bipartiteness Tester, Oded Goldreich, Dana Ron
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length d, and the...
Uniform Generation of NP-witnesses Using an NP-oracle (1998)
Mihir Bellare, Oded Goldreich, Erez Petrank
A Uniform Generation procedure for NP is an algorithm which given any input in a fixed NP-language, outputs a uniformly distributed NP-witness for membership of the input in the language. We present...
Property Testing in Bounded Degree Graphs (1998)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Whereas they view graphs as represented by their adjacency matrix and measure distance between...
Chinese Remaindering with Errors (1998)
Oded Goldreich, Dana Ron, Madhu Sudan
The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p 1 ; : : : ; p k , provided m ! Q k i=1 p i . Thus the...
On the Limits of Non-Approximability of Lattice Problems (1998)
Oded Goldreich, Rehovot Israel, Shafi Goldwasser
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of p n, of optimization problems in integer lattices; specifically, the closest...
Computational Complexity and Knowledge Complexity (1998)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank, Siam J. Comput C
.<F3.9e+05> We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized...
Uniform Generation of NP-witnesses using an NP-oracle (1998)
Mihir Bellare, Oded Goldreich, Erez Petrank
A Uniform Generation procedure for NP is an algorithm which given any input in a fixed NP-language, outputs a uniformly distributed NP-witness for membership of the input in the language. We present...
Learning Polynomials With Queries: The Highly Noisy Case (1998)
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
Given a function f mapping n-variate inputs from a finite field F into F , we consider the task of reconstructing a list of all n-variate degree d polynomials which agree with f on a tiny but...
Self-delegation with controlled propagation — or — what if you lose your laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
Self-Delegation with Controlled Propagation- or- What If You Lose Your Laptop (1998)
Srael Ermany, Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
\Lambda y z Keywords:
Free bits, PCPs, and nonapproximability -- towards tight results (1998)
Mihir Bellare, Oded Goldreich, Madhu Sudan
This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) and the approximability of NP-optimization problems. The emphasis is on proving tight...
Self-Delegation with Controlled Propagation (1998)
Or What If, Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron
We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown £¥¤§¦©¨������������¦©¨������ function...
On the Foundations of Modern Cryptography (1997)
In our opinion, the Foundations of Cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. We survey some of...
A taxonomy of proof systems (1997)
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Public-key cryptosystems from lattice reduction problems (1997)
Oded Goldreich, Sha Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997)
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Shai Halevi
Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on...
Public-Key Cryptosystems from Lattice Reduction Problems (1997)
Oded Goldreich Shafi, Public-key Cryptosystems, Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
Public-Key Cryptosystems from Lattice Reduction Problems (1997)
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
On the Foundations of Modern Cryptography (1997)
the design of cryptographic systems has to be based on firm foundations; whereas ad-hoc approaches and heuristics are a very dangerous way to go. A heuristic may make sense when the designer has a...
The Foundations of Modern Cryptography (1997)
In our opinion, the Foundations of Cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. In this essay, we...
Efficient Approximation of General Product Distributions (1997)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces that approximate the joint distribution of general random variables. Previous work on efficient constructions concentrate on...
Three XOR-Lemmas --- An Exposition (1997)
Oded Goldreich Department, Oded Goldreich
We provide an exposition of three Lemmas which relate general properties of distributions with the exclusive-or of certain bit locations. The first XOR-Lemma, commonly attributed to U.V. Vazirani,...
Addendum to the Paper "Randomness in Interactive Proofs" (1997)
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
Contents: We reproduce a result regarding random walks on expander graphs which is implicit in [BGG90]. The presentation in [BGG90] makes an unnecessary step (i.e., modifying the random walk). The...
A Sample of Samplers: A Computational Perspective on Sampling (1997)
We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f : f0; 1g n 7! [0; 1], we need to estimate 2 \Gamman P x2f0;1g n f(x)...
Uniform Generation of NP-witnesses using an NP-oracle (1997)
Mihir Bellare, Oded Goldreich, Erez Petrank
A Uniform Generation procedure for NP is an algorithm which given any input in a fixed NP-language, outputs a uniformly distributed NP-witness for membership of the input in the language. We present...
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1997)
Oded Goldreich, Avi Wigderson, Givat Ram
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
A Combinatorial Consistency Lemma with application to proving the PCP Theorem (1997)
The current proof of the PCP Theorem (i.e., NP = PCP(log; O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the...
Computational Sample Complexity (1997)
Scott Decatur, Oded Goldreich, Dana Ron
In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information...
On the Theory of Average Case Complexity (1997)
Shai Ben-david, Benny Chor, Oded Goldreich, Michael Luby
This paper takes the next step in developing the theory of average case complexity initiated by Leonid A Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the...
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997)
Ajtai-dwork Cryptosystem, Oded Goldreich, Shafi Goldwasser, Shai Halevi
. Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on...
Property Testing in Bounded Degree Graphs (1997)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Whereas they view graphs as represented by their adjacency matrix and measure distance between...
Property Testing in Bounded Degree Graphs (1997)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case the graph...
The Random Oracle Hypothesis is False (1997)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, ...
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
A Sample of Samplers: A Computational Perspective on Sampling (1997)
We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f : f0; 1g n 7! [0; 1], we need to estimate 2 \Gamman P x2f0;1g n f(x)...
A Taxonomy of Proof Systems (1997)
Several alternative formulations of the concept of an efficient proof system are nowadays coexisting in our field. These systems include the classical formulation of NP , interactive proof systems...
Three XOR-Lemmas --- An Exposition (1997)
Oded Goldreich Department, Oded Goldreich
We provide an exposition of three Lemmas which relate general properties of distributions with the exclusive-or of certain bit locations. The first XOR-Lemma, commonly attributed to U.V. Vazirani,...
On the Complexity of Interactive Proofs with Bounded Communication (1997)
Oded Goldreich, Rehovot Israel, Johan Håstad
We investigate the computational complexity of languages which have interactive proof systems of bounded message complexity. In particular, denoting the length of the input by n, we show that ffl If...
Public-Key Cryptosystems from Lattice Reduction Problems (1997)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
How to Solve any Protocol Problem - An Efficiency Improvement (Extended Abstract) (1997)
) Oded Goldreich and Ronen Vainish Department of Computer Science Technion -- Israel Institute of Technology, Haifa, ISRAEL. ABSTRACT: Consider n parties having local inputs x 1 ; x 2 ; :::; x n...
A Taxonomy of Proof Systems (1997)
Several alternative formulations of the concept of an efficient proof system are nowadays coexisting in our field. These systems include the classical formulation of NP , interactive proof systems...
Quantifying Knowledge Complexity (1997)
One of the many contributions of the paper of Goldwasser, Micali and Rackoff is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) have...
Property Testing in Bounded Degree Graphs (1997)
We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Whereas they view graphs as represented by their adjacency matrix and measure distance between...
Another proof that BPP \subseteq PH (and more) (1997)
Oded Goldreich, Rehovot Israel, David Zuckerman
We provide another proof of the Sipser--Lautemann Theorem by which BPP ` MA (` PH). The current proof is based on strong results regarding the amplification of BPP , due to Zuckerman. Given these...
Three XOR-Lemmas --- An Exposition (1997)
We provide an exposition of three Lemmas which relate general properties of distributions with the exclusive-or of certain bit locations. The first XOR-Lemma, commonly attributed to U.V. Vazirani,...
Self-Delegation with Controlled Propagation (1997)
Or What If, Oded Goldreich, Birgit Pfitzmanny, Ronald L. Rivestz
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
Notes on Levin's Theory of Average-Case Complexity (1997)
Abstract In 1984, Leonid Levin has initiated a theory of average-case complexity. We provide an exposition of the basic definitions suggested by Levin, and discuss some of the considerations...
A taxonomy of proof systems (1997)
Oded Goldreich, Oded Goldreich
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on...
Software Protection and Simulation on Oblivious RAMs (1996)
Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky
Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...
Probabilistic Proof Systems -- A Survey (1996)
Oded Goldreich Department, Oded Goldreich
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems ---...
Probabilistic Proof Systems (A Survey) (1996)
Oded Goldreich Department, Oded Goldreich
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems ---...
Software Protection and Simulation on Oblivious RAMs (1996)
Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky
Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...
Probabilistic Proof Systems (A Survey) (1996)
Oded Goldreich Department, Oded Goldreich
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems ---...
Adaptively Secure Multi-party Computation (1996)
Ran Canetti, Uri Feige, Oded Goldreich, Moni Naor
A fundamental problem in designing secure multi-party protocols is how to deal with adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the...
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof (1996)
The Graph Clustering Problem is parameterized by a sequence of positive integers, m 1 ; :::; m t . The input is a sequence of P t i=1 m i graphs, and the question is whether the equivalence classes...
Collision-Free Hashing from Lattice Problems (1996)
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Shai Halevi
Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same...
Theory of Computing: A Scientific Perspective (1996)
We are gravely concerned with the contents, spirit and recommendations in the Aho et. al. Report on the Theory of Computing (TOC). This report "assesses the current goals and directions of the...
Collision-Free Hashing from Lattice Problems (1996)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same...
Software Protection and Simulation on Oblivious RAMs (1996)
Oded Goldreich, Rafail Ostrovsky
Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...
Collision-Free Hashing from Lattice Problems (1996)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same...
Software Protection and Simulation on Oblivious RAMs (1996)
Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky
Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...
Software Protection and Simulation on Oblivious RAMs (1996)
Oded Goldreich, Rafail Ostrovsky
Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...
Probabilistic Proof Systems (A Survey) (1996)
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems ---...
Private Information Retrieval (1996)
Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a significant risk to the privacy of the user, since a curious database operator...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Private information retrieval (1995)
Benny Chor, Oded Goldreich, Eyal Kushilevitz
Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a signicant risk to the privacy of the user, since a curious database operator...
Learning polynomials with queries: The highly noisy case (1995)
Oded Goldreich, Ronitt Rubinfeld
Given a function f mapping n-variate inputs from a nite eld F into F, we consider the task of reconstructing a list of all n-variate degree d polynomials that agree with f on a tiny but...
Private Information Retrieval (1995)
Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
: We describe schemes that enable a user to access k replicated copies of a database (k 2) and privately retrieve information stored in the database. This means that each individual database gets no...
Fault-tolerant Computation in the Full Information Model (1995)
Oded Goldreich, Shafi Goldwasser, Nathan Linial
We initiate an investigation of general fault-tolerant distributed computation in the fullinformation model. In the full information model no restrictions are made on the computational power of the...
Three XOR-Lemmas - An Exposition (1995)
We provide an exposition of three Lemmas which relate general properties of distributions with the exclusive-or of certain bit locations. The first XOR-Lemma, commonly attributed to U.V. Vazirani,...
Information Theory versus Complexity Theory: Another Test Case (1995)
Ivan Damgård, Oded Goldreich, Avi Wigderson
A few cases are known where the computational analogue of some basic information theoretical results is much harder to prove or even not known to hold. A notable example is Yao's XOR Lemma....
How to Construct Constant-Round Zero-Knowledge Proof Systems for NP (1995)
Constant-round zero-knowledge proof systems for every language in NP are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such proof systems...
Learning polynomials with queries: The highly noisy case (1995)
Oded Goldreich, Ronitt Rubinfeld
Given a function f mapping n-variate inputs from a finite field F into F , we consider the task of reconstructing a list of all n-variate degree d polynomials which agree with f on a tiny but...
Free Bits, PCPs and Non-Approximability - Towards Tight Results (3rd Version) (1995)
Mihir Bellare, Oded Goldreich, Madhu Sudan
This paper continues the investigation of the connection between proof systems and approximation. The emphasis is on proving tight non-approximability results via consideration of measures like the...
Incremental Cryptography and Application to Virus Protection (1995)
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
The goal of incremental cryptography is to design cryptographic algorithms with the property that having applied the algorithm to a document, it is possible to quickly update the result of the...
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs (1995)
Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson
This paper presents two transformations of public-coin/Arthur-Merlin proof systemswhich are zero-knowledge with respect to the honest verifier into (public-coin/ArthurMerlin) proof systems which are...
On Constructing 1-1 One-Way Functions (1995)
Oded Goldreich, Leonid A. Levin, Noam Nisan
We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of...
On Constructing 1-1 One-Way Functions (1995)
Oded Goldreich, Leonid A Levin, Noam Nisan
We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of...
Probabilistic Proof Systems (A Survey) (1995)
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems ---...
Private Information Retrieval (1995)
Benny Chor, Oded Goldreich, Eyal Kushilevitz
Publicly accessible databases are an indispensable resource for retrieving up to date information. But they also pose a significant risk to the privacy of the user, since a curious database operator...
Adaptively Secure Multi-party Computation (1995)
Ran Canetti, Uri Feige, Oded Goldreich, Moni Naor
A fundamental problem in the area of secure multi-party computation is how to deal with adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the...
Learning Polynomials With Queries: The Highly Noisy Case (1995)
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
Given a function f mapping n-variate inputs from a finite field F into F , we consider the task of reconstructing a list of all n-variate degree d polynomials which agree with f on a tiny but...
Incremental Cryptography and Application to Virus Protection (1995)
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
The goal of incremental cryptography is to design cryptographic algorithms with the property that having applied the algorithm to a document, it is possible to quickly update the result of the...
Quantifying Knowledge Complexity (1995)
One of the many contributions of the paper of Goldwasser, Micali and Rackoff is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) seems...
Honest verifier vs. dishonest verifier in public coin zeroknowledge proofs (1995)
Tatsuaki Okamoto ¢ This paper presents two transformations of public-coin/Arthur-Merlin proof systems which are zero-knowledge with respect to the honest verifier into (public-coin/Arthur-Merlin)...
Free Bits, PCPs and Non-Approximability - Towards Tight Results (3rd Version) (1995)
Mihir Bellare, Oded Goldreich, Madhu Sudan
This paper continues the investigation of the connection between proof systems and approximation. The emphasis is on proving tight non-approximability results via consideration of measures like the...
Hashing functions can simplify zero-knowledge protocol design (too (1994)
Ivan Damg Ard, Ivan Damgard, Oded Goldreich, Oded Goldreich, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Definitions and Properties of Zero-Knowledge Proof Systems (1994)
In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary...
Hashing functions can simplify zero-knowledge protocol design (too (1994)
Ivan Damgard, Oded Goldreich, Avi Wigderson
In Crypto93, Damgard showed that any constant-round protocol in which the verifier sends only independent, random bits and which is zero-knowledge against the honest verifier can be transformed into...
Computational complexity and knowledge complexity (1994)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
We study the computational complexity of languages which have interactive proofs of logarithmic knowledge-complexity. We show that all such languages can be recognized in BPP NP Prior to this work,...
Computational Complexity and Knowledge Complexity (1994)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in BPP NP . Prior to this work,...
Oded Goldreich Department, Oded Goldreich, Avi Wigderson
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
On-Line/Off-Line Digital Signatures (1994)
Shimon Even, Oded Goldreich, Silvio Micali
A new type of signature scheme is proposed. It consists of two phases. The first phase is performed off-line, before the message to be signed is even known. The second on-line phase is performed once...
Lower Bounds for Sampling Algorithms for Estimating the Average (1994)
Ran Canetti, Guy Even, Oded Goldreich
We show lower bounds on the number of sample points and on the number of coin tosses used by general sampling algorithms for estimating the average value of functions over a large domain. The bounds...
Quantitative Analysis of Dynamic Network Protocols (1994)
Oded Goldreich, Amir Herzberg, Adrian Segall
We present a quantitative approach to the analysis of dynamic network protocols. Dynamic networks, extensively studied in the last decade, are asynchronous communication networks in which links...
The Random Oracle Hypothesis is False (1994)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, ...
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
Incremental Cryptography: The Case of Hashing and Signing (1994)
Mihir Bellare, Oded Goldreich, Shafi Goldwasser, M. Bellare, O. Goldreich, S. Goldwasser
We initiate the investigation of a new kind of efficiency for cryptographic transformations. The idea is that having once applied the transformation to some document M , the time to update the result...
Computational Complexity and Knowledge Complexity (1994)
Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky, Erez Petrank
We study the computational complexity of languages which have interactive proofs of logarithmic knowledge-complexity. We show that all such languages can be recognized in BPP NP . Prior to this work,...
Probabilistic Proof Systems (A Survey) (1994)
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems --...
Computational Complexity and Knowledge Complexity (1994)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in BPP NP . Prior to this work,...
Computational Complexity and Knowledge Complexity (1994)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
. We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in BPP NP . Prior to this...
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1994)
Oded Goldreich, Avi Wigderson, Givat Ram
We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
The Random Oracle Hypothesis is False (1994)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, ...
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing (1994)
.We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),...
Hashing functions can simplify zero-knowledge protocol design (too (1994)
Oded Goldreich, Oded Goldreich, Avi Wigderson, Avi Wigderson
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Shimon Even, Oded Goldreich, Silvio Micali
Abstract. A new type of signature scheme is proposed. It consists of two phases. The first phase is performed off-line, before the message to be signed is even known. The second phase is performed...
Bounds on Tradeoffs between Randomness and Communication Complexity (1993)
Known results concerning the power of randomness are qualitative, in the sense that they only show that solutions exist or can be improved if randomness is allowed. We initiate a quantitative...
Randomness in Interactive Proofs (1993)
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
This paper initiates a study of the quantitative aspects of randomness in interactive proofs. Our main result, which applies to the equivalent form of IP known as Arthur-Merlin (AM) games, is a...
Randomness in Interactive Proofs (1993)
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
This paper initiates a study of the quantitative aspects of randomness in interactive proofs. Our main result, which applies to the equivalent form of IP known as Arthur-Merlin (AM) games, is a...
Simple Constructions of Almost k-wise Independent Random Variables (1992)
Noga Alon, Oded Goldreich, René Peralta
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
On Defining Proofs of Knowledge (1992)
oded$s. t echnion. ac. il. Abstract. The notion of a "proof of knowledge, " suggested by Gold-wasset, Micali and Rackoff, has been used in many works as a tool for the construction...
Approximations of General Independent Distributions (1992)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovi'c
We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on...
Towards a Computational Theory of Statistical Tests (1992)
We initiate a computational theory of statistical tests. Loosely speaking, we say that an algorithm is a statistical test if it rejects a "negligible" fraction of strings. We say that a...
Proving Computational Ability (1992)
We extend the notion of a proof of knowledge to a proof of the ability to perform some computational task. Department of Computer Science & Engineering, Mail Code 0114, University of California...
Proving Computational Ability (1992)
We investigate extending the notion of a proof of knowledge to a proof of the ability to perform some computational task. We provide some definitions and protocols for this purpose. Department of...
On Defining Proofs of Knowledge (1992)
The notion of a "proof of knowledge," suggested by Goldwasser, Micali and Rackoff, has been used in many works as a tool for the construction of cryptographic protocols and other schemes....
Simple Constructions of Almost k-wise Independent Random Variables (1992)
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
Quantifying Knowledge Complexity (1991)
One of the many contributions of the paper of Goldwasser, Micali and Rackoff is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) have...
A Uniform-Complexity Treatment of Encryption and Zero-Knowledge (1991)
We provide a treatment of encryption and zero-knowledge in terms of uniform complexity measures. This treatment is appropriate for cryptographic settings modeled by probabilistic polynomial-time...
Reuven Bar-yehuda, Oded Goldreich, Alon Itai
This paper presents an efficient randomized emulation of single-hop radio network with collision detection on multi-hop radio network without collision detection. Each step of n the single-hop...
A note on computational indistinguishability (1990)
We consider the existence of pairs of probability ensembles which may be eciently distinguished given k samples but cannot be eciently distinguished given k 0 samples. It is well known that in any...
A Tradeoff Between Information and Communication in Broadcast Protocols (1990)
Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish
This paper concerns the message complexity of broadcast in arbitrary point-topoint communication networks. Broadcast is a task initiated by a single processor that wishes to convey a message to all...
A Note On Computational Indistinguishability (1990)
We show that following two conditions are equivalent: 1) The existence of pseudorandom generators. 2) The existence of a pair of efficiently constructible distributions which are computationally...
On the Composition of Zero-Knowledge Proof Systems (1990)
: The wide applicability of zero-knowledge interactive proofs comes from the possibility of using these proofs as subroutines in cryptographic protocols. A basic question concerning this use is...
Security Preserving Amplification of Hardness (1990)
Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, David Zuckerman
We consider the task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted...
All known fast randomized Byzantine Agreement (BA) protocols have (rare) infinite runs. We present a method of combining randomized BA protocols of a certain class with any deterministic BA protocol...
Security Preserving Amplification of Hardness (1990)
Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, David Zuckerman
We consider the task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted...
The random oracle hypothesis is false (1990)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Desh Ranjan, Pankaj Rohatgi
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
A Note on Computational Indistinguishability (1990)
Abstract We consider the existence of pairs of probability ensembles which may be efficiently distinguished given k samples but cannot be efficiently distinguished given k 0! k samples. It is well...
On The Power Of Two-Points Based Sampling (1989)
The purpose of this note is to present a new sampling technique and to demonstrate some of its properties. The new technique consists of picking two elements at random, and deterministically...
On Completeness and Soundness in Interactive Proof Systems (1989)
Martin Furer, Oded Goldreich, Yishay Mansour
An interactive proof system with Perfect Completeness (resp. Perfect Soundness) for a language L is an interactive proof (for L) in which for every x 2 L (resp. x 62 L) the verifier always accepts...
On The Power Of Two-Points Based Sampling (1989)
The purpose of this note is to present a new sampling technique and to demonstrate some of its properties. The new technique consists of picking two elements at random, and deterministically...
A hard-core predicate for all one-way functions (1989)
Oded Goldreich, Leonid A. Levint
Abstract rity of f. In fact, for inputs (to f*) of practical size, the pieces effected by f are so small A central tool in constructing pseudorandom that f can be inverted (and the “hard-core”...
Randomness, interactive proofs, and zero-knowledge -- a survey (1988)
Recent approaches to the notions of randomness and proofs are surveyed. The new notions differ from the traditional ones in being subjective to the capabilities of the observer rather than reflecting...
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (1988)
, Introduction and References only) Benny Chor Oded Goldreich MIT \Gamma Laboratory for Computer Science Cambridge, Massachusetts 02139 ABSTRACT \Gamma A new model for weak random physical sources is...
Oded Goldreich, Ilvio Micali, Am Wigderson
Under the assumption that encryption functions exist, we show that all lan_uages in NP possess zero-knowledge proofs. That is, it is possible to demonstrate that a CNF formula is satisfiable without...
Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme (1987)
Reproduced From Preprint, Oded Goldreich
The focus of this note is the Goldwasser-Micali-Rivest Signature Scheme (presented in the 25th POCS , 1984). The GMR scheme has the salient property that, unless factoring is easy, it is infeasible...
How to Solve any Protocol Problem (1987)
Goldreich Silvio, Oded Goldreich, Silvio Micali, Avi Wigderson
: This extended abstract present a general theorem in the field of fault tolerant distributed computing. Following is a simplified description of a special case of this theorem. Loosely speaking, a...
On the Security of Multi-Party Ping-Pong Protocols (1985)
This paper is concerned with the model for security of cryptographic protocols suggested by Dolev and Yao. The Dolev and Yao model deals with a restricted class of protocols, known as Two-Party...
The Bit Extraction Problem or t-Resilient Functions (1985)
Benny Chor, Oded Goldreich, Johan Haståd, Joel Freidmann, Steven Rudich, Roman Smolensky
\Gamma We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f : f0; 1g n 7! f0; 1g m be a function. An adversary, knowing the function f , sets t of the n...
Property Testing and its connection to Learning and Approximation
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Dana Ron
We study the question of determining whether an unknown function has a particular property or is ffl-far from any function with that property. A property testing algorithm is given a sample of the...
Property Testing and Its Connection to Learning and Approximation
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Dana Ron
In this paper, we consider the question of determining whether a function f has property P or is ffl-far from any function with property P. A property testing algorithm is given a sample of the value...
On Defining Proofs of Knowledge
The notion of a "proof of knowledge," suggested by Goldwasser, Micali and Rackoff, has been used in many works as a tool for the construction of cryptographic protocols and other schemes....
Property Testing and its Connection to Learning and Approximation
Oded Goldreich, Shafi Goldwasser, Dana Ron
We study the question of determining whether an unknown function has a particular property or is ffl-far from any function with that property. A property testing algorithm is given a sample of the...