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...
New Algorithms for SIMD Alignment ⋆ (2008)
Liza Fireman, Erez Petrank, Ayal Zaks
Abstract. Optimizing programs for modern multiprocessor or vector platforms is a major important challenge for compilers today. In this work, we focus on one challenging aspect: the SIMD ALIGNMENT...
Using Prefetching to Improve Reference-Counting Garbage Collectors ⋆ (2008)
Abstract. Reference counting is a classical garbage collection method. Recently, a series of papers have extended the basic method to drastically reduce its notorious overhead and extend the basic...
ABSTRACT Black-Box Constructions for Secure Computation ∗ (extended abstract) (2008)
Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank
It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions...
ABSTRACT Mostly Concurrent Garbage Collection Revisited (2008)
Katherine Barabash, Yoav Ossia, Erez Petrank
The mostly concurrent garbage collection was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly...
Poly-logarithmic Rounds, Joe Kilian, Erez Petrank
2 k) rounds given at most k concurrent proofs. Finally, we show that a simple modification of our proof is a resettable zero-knowledge proof for NP, with!(log 2 k) rounds; previously known protocols...
Efficient and concurrent zeroknowledge from any public coin HVZK protocol (2008)
Daniele Micciancio, Erez Petrank
protocol
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank
Consider the set H of all linear (or ane) transformations between two vector spaces over a nite eld F. We study how good H is as a class of hash functions, namely we consider hashing a set S of size...
Hezi Azatchi, Yossi Levanoni, Erez Petrank
With concurrent and garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor garbage collector has become acute....
Ecient and Concurrent Zero-Knowledge from any public coin HVZK protocol (2007)
Daniele Micciancio, Erez Petrank
We show how to eciently transform any public coin honest verier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verier via...
The Hardness of Cache Conscious Data Placement (Extended Abstract) (2007)
The growing gap between the speed of memory access and cache access has made cache misses an in uential factor in program eciency. Much eort has been spent recently on reducing the number of cache...
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...
Probabilistically Checkable Proofs with Zero Knowledge (2007)
We construct PCPs with strong zero-knowledge properties. First, we construct polynomially bounded (in size) PCP's for NP which can be checked using poly-logarithmic queries, with polynomially...
KNOWLEDGE COMPLEXITY VERSUS COMPUTATIONAL COMPLEXITY AND THE HARDNESS OF APPROXIMATIONS (2007)
Erez Petrank, Ran Canetti, Benny Chor, Eli Dichterman, Guy Even, Shai Halevi, ...
This research was carried out in the faculty of Computer Science under the
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S...
Tzafrir Cohen, Joe Kilian, Erez Petrank
Abstract. The number of communication rounds is a classic complexity measure for protocols; reducing round complexity is a major goal in protocol design. However, when the communication time is...
Probabilistically Checkable Proofs with Zero Knowledge (2007)
We construct PCPs with strong zero-knowledge properties. First, we construct polynomially bounded (in size) PCP's for NP which can be checked using polylogarithmic queries, with polynomially low...
Alain Azagury, Elliot K. Kolodner, Erez Petrank, Zvi Yehudai
We consider the combination of card marking with remembered sets for generational garbage collection as suggested by Hosking and Hudson [3]. When more than two generations are used, a naive...
Black-Box Concurrent Zero-Knowledge Requires (2007)
Omega\gamma N Rounds, Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen
We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside BPP), whose security is proven via black-box simulation, must use at least ~...
Joe Kilian, Erez Petrank, Ransom Richardson
A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zeroknowledge is not...
Joe Kilian, Erez Petrank, Charles Rackoff
We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may...
Ecient and Concurrent Zero-Knowledge from any public coin HVZK protocol (2007)
Daniele Micciancio, Erez Petrank
We show how to eciently transform any public coin honest verier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verier via...
An efficient on-the-fly cycle collection (2007)
Paz, Harel, Bacon, David, Rajan, V. T., Kolodner, Elliot K., Petrank, Erez
A reference-counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference-counting collectors either use a backup tracing collector infrequently, or employ...
On Combining Privacy with Guaranteed Output Delivery in Secure Multiparty Computation (2006)
Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank
In the setting of multiparty computation, a set of parties wish to jointly compute a function of their inputs, while preserving security in the case that some subset of them are corrupted. The...
An Efficient Parallel Heap Compaction Algorithm (2004)
Diab Abuaiadh Yoav, Yoav Ossia, Erez Petrank, Uri Silbershtein
We propose a heap compaction algorithm appropriate for modern computing environments. Our algorithm is targeted at SMP platforms. It demonstrates high scalability when running in parallel but is also...
Mostly Concurrent Garbage Collection Revisited (2003)
Katherine Barabash, Yoav Ossia, Erez Petrank
The mostly concurrent garbage collection was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly...
Simulatable Commitments and Efficient Concurrent Zero-Knowledge (2003)
Daniele Micciancio, Erez Petrank
Abstract. We define and construct simulatable commitments. These are commitment schemes such that there is an efficient interactive proof system to show that a given string c is a legitimate...
Integrating generations with advanced reference counting garbage collectors (2003)
Abstract. We study an incorporation of generations into a modern reference counting collector. We start with the two on-the- y collectors suggested by Levanoni and Petrank: a reference counting...
Lower and Upper Bounds on Obtaining History Independence (2003)
History independent data structures, presented by Micciancio, are data structures that possess a strong security property: even if an intruder manages to get a copy of the data structure, the memory...
On-the-Fly Cycle Collection Revisited (2003)
Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, V. T. Rajan
A reference counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference counting collectors either use a backup tracing collector seldom, or employ a...
On-the-fly cycle collection revisited (2003)
Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, V. T. Rajan
A reference counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference counting collectors either use a backup tracing collector seldom, or employ a...
On-the-fly cycle collection revisited (2003)
Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, V. T. Rajan
A reference counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference counting collectors either use a backup tracing collector seldom, or employ a...
Integrating generations with advanced reference counting garbage collectors (2003)
1 Introduction Automatic memory management is well acknowledged as an important tool for fast development of large reliable software. It turns out that the garbage collection process has an important...
Mostly Concurrent Garbage Collection Revisited (2003)
Katherine Barabash, Yoav Ossia, Erez Petrank
ABSTRACT The mostly concurrent garbage collection was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly...
Extending oblivious transfers efficiently (2003)
Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank
Abstract. We consider the problem of extending oblivious transfers: Given a small number of oblivious transfers “for free, ” can one implement a large number of oblivious transfers? Beaver has...
Thread-local heaps for Java (2002)
Tamar Domani, Gal Goldshtein, Elliot K. Kolodner, Ethan Lewis, Erez Petrank, Dafna Sheinwald
We present a memory management scheme for Java based on thread-local heaps. Assuming most objects are created and used by a single thread, it is desirable to free the memory manager from redundant...
On Concurrent and Resettable Zero-Knowledge Proofs for NP (2001)
Kilian, Joe, Petrank, Erez, Richardson, Ransom
A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not...
Lower Bounds for Zero-knowledge on the Internet (2001)
Kilian, Joe, Petrank, Erez, Rackoff, Charles
We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may...
Responsive Round Complexity and Concurrent ZeroKnowledge (2001)
Tzafrir Cohen, Joe Kilian, Erez Petrank
Abstract. The number of communication rounds is a classic complexity measure for protocols; reducing round complexity is a major goal in protocol design. However, when the communication time is...
Responsive Round Complexity and Concurrent ZeroKnowledge (2001)
Tzafrir Cohen, Joe Kilian, Erez Petrank
Abstract. The number of communication rounds is a classic complexity measure for protocols; reducing round complexity is a major goal in protocol design. However, when the communication time is...
Black-Box Concurrent Zero-Knowledge Requires ~\Omega (log n) Rounds (2001)
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen
We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside BPP), whose security is proven via black-box simulation, must use at least ~...
Concurrent Zero-Knowledge Proofs for NP (2001)
Joe Kilian, Erez Petrank, Ransom Richardson
A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zeroknowledge is not...
CBC MAC for real-time data sources (2000)
The Cipher Block Chaining (CBC) Message Authentication Code (MAC) is an authentication method which is widely used in practice. It is well known that the naive use of CBC MAC for variable length...
A Generational On-the- Garbage Collector for Java (2000)
Tamar Domani, Elliot K. Kolodner, Erez Petrank
An on-the- y garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the- y...
Implementing an on-the-fly garbage collector for Java (2000)
Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Eliot E. Salant, Katherine Barabash, Itai Lahan, ...
Java uses garbage collection (GC) for the automatic reclamation of computer memory no longer required by a running application. GC implementations for Java Virtual Machines (JVM) are typically...
Implementing an on-the-fly garbage collector for Java (2000)
Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Eliot E. Salant, Katherine Barabash, Itai Lahan, ...
Java uses garbage collection (GC) for the automatic reclamation of computer memory no longer required by a running application. GC implementations for Java Virtual Machines (JVM) are typically...
A Generational On-the-fly Garbage Collector for Java (2000)
Tamar Domani, Elliot K. Kolodner, Erez Petrank
An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly...
Concurrent Zero-Knowledge in Poly-logarithmic Rounds (Extended Abstract) (2000)
A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such...
Concurrent zero-knowledge in poly-logarithmic rounds (2000)
A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such...
Concurrent Zero-Knowledge in (2000)
Poly-logarithmic Rounds, Erez Petrank
k) number of rounds. Thus, we narrow the huge gap between the known upper and lower bounds on the number of rounds required for a zero-knowledge proof that is robust for asynchronous composition. 1...
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...
An On-the- Reference Counting Garbage Collector for Java, proccedings (1999)
Reference counting is not naturally suitable for running on multiprocessors. The update of pointers and reference counts requires atomic and synchronized operations. We present a novel reference...
Martin Dietzfelbinger, Peter Bro Miltersen, G Abor Tardos, Noga Alon, Noga Alon, Erez Petrank, ...
et al.:
Computing from partial solutions (1999)
Shai Halevi, Richard J. Lipton, Erez Petrank
We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an ffl fraction of the bits in a satisfying assignment to a 3-CNF...
Parallel Copying Garbage Collection using Delayed Allocation (1999)
Elliot K. Kolodner, Erez Petrank
We present a new approach to parallel copying garbage collection on symmetric multiprocessor (SMP) machines appropriate for Java and other object-oriented languages. Parallel, in this setting, means...
A Scalable Reference Counting Garbage Collector (1999)
We study concurrent garbage collection via reference counting. While tracing variants of garbage collection have been well studied with respect to concurrency, the study of reference counting has...
Computing From Partial Solutions (1999)
Anna Al Shai, Shai Halevi, Richard J. Lipton, Erez Petrank
We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an ffl fraction of the bits in a satisfying assignment to a 3-CNF...
Parallel Copying Garbage Collection using Delayed Allocation (1999)
We present a new approach to parallel copying garbage collection on symmetric multiprocessor (SMP) machines appropriate for Java and other object-oriented languages. Parallel, in this setting, means...
We introduce the notion of escrowed identity, an application of key-escrow ideas to the problem of identification. In escrowed identity, one party A does not give his identity to another party B, but...
Lower Bounds for Zero Knowledge on the Internet (1998)
Joe Kilian, Erez Petrank, Charles Rackoff
We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may...
Alain Azagury, Elliot K. Kolodner, Erez Petrank
Replication-based incremental garbage collection [5, 4] is one of the more appealing concurrent garbage collection algorithms known today. It allows continuous operation of the application (the...
An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions (1998)
We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum, Feldman and Micali [BFM88]. Until recently there was a sizable polynomial gap between the most...
We introduce the concept of escrowed identity, an application of key-escrow ideas to the problem of authentication. In escrowed identity, one party A does not give his identity to another party B,...
We introduce the concept of escrowed identity, an application of key-escrow ideas to the problem of authentication. In escrowed identity, one party A does not give his identity to another party B,...
Lower Bounds for Zero Knowledge on the Internet (1998)
Joe Kilian, Erez Petrank, Charles Rackoff
We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may...
Combining Card Marking with Remembered Sets: How to Save Scanning Time (1998)
Alain Azagury, Elliot K. Kolodner, Erez Petrank, Zvi Yehudai
We consider the combination of card marking with remembered sets for generational garbage collection as suggested by Hosking and Hudson [3]. When more than two generations are used, a naive...
Alain Azagury, Elliot K. Kolodner, Erez Petrank
Replication-based incremental garbage collection [5, 4] is one of the more appealing concurrent garbage collection algorithms known today. It allows continuous operation of the application (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...
Computational Complexity and Knowledge Complexity (1998)
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
.<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...
Is Code Equivalence Easy to Decide (1997)
y We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the same codewords up to a fixed permutation on the codeword...
Is Code Equivalence Easy to Decide? (1997)
We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the same codewords up to a fixed permutation on the codeword...
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...
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...
Probabilistically Checkable Proofs with Zero Knowledge (1997)
Joe Kilian, Erez Petrank, Gábor Tardos
We construct PCPs with strong zero-knowledge properties. First, we construct polynomially bounded (in size) PCP's for NP which can be checked using poly-logarithmic queries, with polynomially...
CBC MAC for Real-Time Data Sources (1997)
Erez Petrank, P. O. Box, Charles Rackoff
The Cipher Block Chaining (CBC) Message Authentication Code (MAC) is an authentication method which is widely used in practice. It is well known that the naive use of CBC MAC for variable length...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S...
We introduce the notion of escrowed identity, an application of key-escrow ideas to the problem of identification. In escrowed identity, one party A does not give his identity to another party B, but...
On the knowledge complexity of NP (1996)
We show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class AM \ co AM. Thus, if the polynomial time hierarchy does not collapse,...
On the knowledge complexity of NP (1996)
We show that if a language has an interactive proof of logarithmic statistical knowledgecomplexity, then it belongs to the class AM " co\GammaAM. Thus, if the polynomial time hierarchy does...
Storing classified files (1995)
We initiate a study of a natural problem in secure systems, namely- storing classified files on-line. A system of classified files contains a set of files (or documents), a set of users, and an...
Knowledge Complexity versus Computational Complexity and the Hardness of Approximations (1995)
Erez Petrank, H. Woll R, Om Self-reducibility, R. Venkatesan, ...
this paper appeared in the Second IEEE Israel Symp. on Theory of Computation and Systems, June 1993, pp. 275-284.
Storing Classified Files (1995)
We initiate a study of a natural problem in secure systems, namely - storing classified files on-line. A system of classified files contains a set of files (or documents), a set of users, and an...
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...
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,...
The hardness of approximation: Gap location (1994)
Abstract. We refine the complexity analysis of approximation problems by relating it to a new parameter called gap location. Many of the results obtained so far for approximations yield satisfactory...
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, 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,...
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...
Making Zero-Knowledge Provers Efficient (1992)
We look at the question of how powerful a prover must be to give a zero-knowledge proof. We present the first unconditional bounds on the complexity of a statistical ZK prover. The result is that if...
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...
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...
Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, V. T. Rajan
A reference counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference counting collectors either use a backup tracing collector seldom, or employ a...
Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, V. T. Rajan
A reference counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference counting collectors either use a backup tracing collector seldom, or employ a...
Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank
Abstract. A reference counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference counting collectors either use a backup tracing collector infrequently,...
This document in subdirectoryRS/97/16/ Linear Hashing
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos, Noga Alon, ...
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 BRICS...