Secure Multiparty Computation of Approximations (Extended Abstract) (2009)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
1 Introduction There are an increasing number and variety of real-world applications that collect a massive amount of data and wish to make use of it. For example, massive data sets arise in physical...
Cryptography in NC0 (Extended Abstract) (2008)
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of computing...
computational complexity COMMUNICATION VS. COMPUTATION (2008)
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, S. Venkatesh
Abstract. We initiate a study of tradeoffs between communication and computation in well-known communication models and in other related models. The fundamental question we investigate is the...
Secure Multiparty Computation of Approximations (Extended Abstract) (2008)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
1 Introduction There are an increasing number and variety of real-world applications that collect a massive amount of data and wish to make use of it. For example, massive data sets arise in physical...
Secure Arithmetic Computation with No Honest Majority (2008)
Ishai, Yuval, Prabhakaran, Manoj, Sahai, Amit
We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of two-party...
, and Erez Petrank 1 1 Technion
Cryptography with Constant Input Locality ⋆ (extended abstract) (2008)
Abstract. We study the following natural question: Which cryptographic primitives (if any) can be realized by functions with constant input locality, namely functions in which every bit of the input...
On Pseudorandom Generators with 0 ⋆ Linear Stretch in NC (2008)
Abstract. We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC 0, namely ones in which each bit of the output depends on just a constant number of input bits....
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...
Compressing Cryptographic Resources (Extended Abstract) (2008)
Abstract. A private-key cryptosystem may be viewed as a means by which a trusted dealer privately conveys a large, shared pseudo-random object to a pair of players, using little communication....
Amos Beimel, Yuval Ishai, Eyal Kushilevitz
Abstract A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a databasewhile hiding the identity of the item being retrieved; specifically, in a t-private,...
Cryptography in NC 0 (EXTENDED ABSTRACT)\Lambda (2008)
Abstract We study the parallel time-complexity of basic crypto-graphic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we studythe possibility of...
How Many Oblivious Transfers are Needed for Secure Multiparty Computation? ∗ (2008)
Danny Harnik, Yuval Ishai, Eyal Kushilevitz, Davis Foundation
Oblivious transfer (OT) is an essential building block for secure multiparty computation when there is no honest majority. In this setting, current protocols for n ≥ 3 parties require each pair of...
Zero-Knowledge from Secure Multiparty Computation ∗ ABSTRACT (2008)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
We present a general construction of a zero-knowledge proof for an NP relation R(x, w) which only makes a black-box use of a secure protocol for a related multi-party functionality f. The latter...
A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The...
Michael J. Freedman, Yuval Ishai, Benny Pinkas, Omer Reingold
xi as the keyword and pi as the payload (database record). A query froma client is a searchword
Breaking the O(n^(1/(2k-1))) Barrier for Information-Theoretic Private Information Retrieval (2008)
Barrier For, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-francois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic,...
Compressing Cryptographic Resources (Extended Abstract) (2007)
. A private-key cryptosystem may be viewed as a means by which a trusted dealer privately conveys large, identical pseudo-random objects to a pair of players, using little communication....
Yuval Ishai, Joe Kilian, Kobbi Nissim
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...
Ronald Cramer, Serge Fehr, Yuval Ishai, Eyal Kushilevitz
Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in...
Abstract. Substantial eorts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the...
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide e#cient solutions when no e#cient exact computation is known. In particular, approximations are often useful in a distributed setting where...
Giovanni Di-crescenzo, Yuval Ishai, Rafail Ostrovsky
A private information retrieval scheme allows a user to retrieve a data item of his choice from a remote database (or several copies of a database) while hiding from the database owner which...
Compressing Cryptographic Resources (extended abstract) (2007)
Abstract. A private-key cryptosystem may be viewed as a means by which a trusted dealer privately conveys a large, shared pseudo-random object to a pair of players, using little communication....
Breaking the O(n 1=(2k\Gamma1) (2007)
Barrier For, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-francois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic,...
Yuval Ishai, Amit Sahai, David Wagner
Abstract. Can you guarantee secrecy even if an adversary can eavesdrop on your brain? We consider the problem of protecting privacy in circuits, when faced with an adversary that can access a bounded...
On Privacy and Partition Arguments 1 (2007)
A function f(x1; x2; : : : ; xn) is said to be t-private if there exists a (randomized) communication protocol for computing f, such that no coalition of at most t participants can infer any...
Ran Canetti, Yuval Ishai, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright
Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client interacts with one...
Amos Beimel, Yuval Ishai, Tal Malkin
Abstract. Private information retrieval (PIR) enables a user to retrieve a specific data item from a database, replicated among one or more servers, while hiding from each server the identity of the...
On the Power of Nonlinear Secret-Sharing (PRELIMINARY VERSION) (2007)
A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The...
Ran Canetti, Yuval Ishai, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright
Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client interacts with one...
NeuroCOLT Coordinating Partner (2007)
Martin Anthony, Peter Bartlett, Yuval Ishai, John Shawe-taylor
-./01 23456
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz
The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Verifiable...
On the Power of Nonlinear Secret-Sharing (PRELIMINARY VERSION) (2007)
A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The...
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide e#cient solutions when no e#cient exact computation is known. In particular, approximations are often useful in a distributed setting where...
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting...
Barrier For, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-francois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic,...
The Round Complexity of Verifiable Secret Sharing (2007)
And Secure Multicast, Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz
The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Veri able...
Private Circuits: Securing Hardware (2007)
Against Probing Attacks, Yuval Ishai, Amit Sahai, David Wagner
Can you guarantee secrecy even if an adversary can eavesdrop on your brain? We consider the problem of protecting privacy in circuits, when faced with an adversary that can access a bounded number of...
Ronald Cramer, Serge Fehr, Yuval Ishai, Eyal Kushilevitz
Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in...
Private Computation Using a PEZ Dispenser (2007)
Jozsef Balogh, Janos A. Csirik, Yuval Ishai, Eyal Kushilevitz
We show how a (big) PEZ dispenser can be used by two or more players to compute a function of their inputs while hiding the values of the inputs from each other. In contrast to traditional approaches...
On Pseudorandom Generators with 0 ∗ Linear Stretch in NC (2007)
We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC 0, namely ones in which each bit of the output depends on just a constant number of input bits. Previous...
Private multiparty sampling and approximation of vector combinations (2007)
Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright
Abstract. We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to...
Cryptography with Constant Input Locality ∗ (2007)
We study the following natural question: Which cryptographic primitives (if any) can be realized by functions with constant input locality, namely functions in which every bit of the input influences...
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...
We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of implementing...
Cryptography from Anonymity (2006)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
There is a vast body of work on implementing anonymous communication. In this paper we study the possibility of using anonymous communication as a building block, and show that one can leverage on...
Private Circuits II: Keeping Secrets In Tamperable Circuits (2006)
Yuval Ishai, Manoj Prabhakaran, Amit Sahai, David Wagner
Motivated by the problem of protecting cryptographic hardware, we continue the investigation of private circuits initiated in [16]. In this work, our aim is to construct circuits that should protect...
Cryptography from Anonymity \Lambda (2006)
Abstract There is a vast body of work on implementing anonymous communication. In this paper, we studythe possibility of using anonymous communication as a building block, and show that one can...
Cryptography from Anonymity (2006)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on...
We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of implementing...
Cryptography from Anonymity (2006)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on...
On pseudorandom generators with linear stretch in NC0 (2006)
Abstract We consider the question of constructing cryptographic pseudorandomgenerators (PRGs) in NC 0, namely ones in which each bit of the output depends on just a constant number of input bits....
Computationally private randomizing polynomials and their applications (2005)
Randomizing polynomials allow to represent a function f(x) by a low-degree randomized mapping ˆf(x, r) whose output distribution on an input x is a randomized encoding of f(x). It is known that any...
Sufficient Conditions for Collision-Resistant Hashing (2005)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Abstract. We present several new constructions of collision-resistant hash-functions (CRHFs) from general assumptions. We start with a simple construction of CRHF from any homomorphic encryption....
Secure computation of constant-depth circuits with applications to database search problems (2005)
Abstract. Motivated by database search problems such as partial match or nearest neighbor, we present secure multiparty computation protocols for constant-depth circuits. Specifically, for a...
Keyword Search and Oblivious Pseudorandom Functions (2005)
Michael J. Freedman, Yuval Ishai, Benny Pinkas, Omer Reingold
We study the problem of privacy-preserving access to a database.
Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator (2005)
We present a constant-round protocol for general secure multiparty computation which makes a black-box use of a pseudorandom generator. In particular, the protocol does not require expensive...
Computationally private randomizing polynomials and their applications (2005)
Randomizing polynomials allow to represent a function f(x) by a low-degree randomized mapping ˆ f(x, r) whose output distribution on an input x is a randomized encoding of f(x). It is known that any...
Secure computation of constant-depth circuits with applications to database search problems (2005)
Abstract. Motivated by database search problems such as partial match or nearest neighbor, we present secure multiparty computation protocols for constant-depth circuits. Specifically, for a...
Constant-round multiparty computation using a black-box pseudorandom generator (2005)
We present a constant-round protocol for general secure multiparty computation which makes a black-box use of a pseudorandom generator. In particular, the protocol does not require expensive...
Sufficient Conditions for Collision-Resistant Hashing (2005)
Abstract. We present several new constructions of collision-resistant hash-functions (CRHFs) from general assumptions. We start with a simple construction of CRHF from any homomorphic encryption....
Kushilevitz,“General constructions for information-theoretic private information retrieval (2005)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved; specifically, in a t-private, k-server PIR...
Computationally private randomizing polynomials and their applications (2005)
Randomizing polynomials allow to represent a function f(x) by a low-degree randomized mapping ˆf(x,r) whose output distribution on an input x is a randomized encoding of f(x). It is known that any...
Kushilevitz,“General constructions for information-theoretic private information retrieval (2005)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz
Abstract A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved; specifically, in a t-private...
Communication vs. computation (2004)
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, S. Venkatesh
We initiate a study of tradeoffs between communication and computation in well-known communication models and in other related models. The fundamental question we investigate is the following: Is...
On the hardness of information-theoretic multiparty computation (2004)
Abstract. We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity...
Batch Codes and Their Applications (2004)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket....
On the Hardness of Information-Theoretic Multiparty Computation (2004)
We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity of the...
Batch codes and their applications (2004)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, From Teradata
A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket....
On the hardness of information-theoretic multiparty computation (2004)
Abstract We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity of...
Communication vs. computation (2004)
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, S. Venkatesh
We initiate a study of tradeoffs between communication and computation in well-known communication models and in other related models. The fundamental question we investigate is the following: Is...
Communication vs. computation (2004)
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, S. Venkatesh
We initiate a study of tradeoffs between communication and computation in well-known communication models and in other related models. The fundamental question we investigate is the following: Is...
Batch Codes and Their Applications (2004)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket....
Communication vs. computation (2004)
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, S. Venkatesh
Abstract. We initiate a study of tradeoffs between communication and computation in well-known communication models and in other related models. The fundamental question we investigate is the...
Efficient Multi-Party Computation over Rings (2003)
Ronald Cramer, Serge Fehr, Yuval Ishai, Eyal Kushilevitz
Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in...
Private Circuits: Securing Hardware against Probing Attacks (2003)
Yuval Ishai, Amit Sahai, David Wagner
Abstract. Can you guarantee secrecy even if an adversary can eavesdrop on your brain? We consider the problem of protecting privacy in circuits, when faced with an adversary that can access a bounded...
General Constructions for Information-Theoretic Private Information Retrieval (2003)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved; specifically, in a t-private, k-server PIR...
Efficient Multi-Party Computation over Rings (2003)
Ronald Cramer, Serge Fehr, Yuval Ishai, Eyal Kushilevitz
Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in...
Private Circuits: Securing Hardware against Probing Attacks (2003)
Yuval Ishai, Amit Sahai, David Wagner
Abstract. Can you guarantee secrecy even if an adversary can eavesdrop on your brain? We consider the problem of protecting privacy in circuits, when faced with an adversary that can access a bounded...
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...
Private Circuits: Securing Hardware against Probing Attacks (2003)
Yuval Ishai, Amit Sahai, David Wagner
Abstract. Can you guarantee secrecy even if an adversary can eavesdrop on your brain? We consider the problem of protecting privacy in circuits, when faced with an adversary that can access a bounded...
On 2-Round Secure Multiparty Computation (2002)
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
Abstract. Substantial efforts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the...
Perfect constant-round secure computation via perfect randomizing polynomials (2002)
Abstract. Various information-theoretic constant-round secure multiparty protocols are known for classes such as NC 1 and polynomial-size branching programs [1, 13, 18, 3, 19, 10]. All these...
Breaking the O(n 1/(2k−1) ) Barrier for Information-Theoretic Private Information Retrieval (2002)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-françois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic,...
Breaking the O(n 1/(2k−1) ) Barrier for Information-Theoretic Private Information Retrieval (2002)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-françois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic...
Breaking the O(n 1/(2k−1) ) Barrier for Information-Theoretic Private Information Retrieval (2002)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-françois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic...
Breaking the O(n 1/(2k−1) ) Barrier for Information-Theoretic Private Information Retrieval (2002)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-françois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Speci£cally, in information-theoretic,...
Breaking the O(n^(1/(2k-1))) Barrier for Information-Theoretic Private Information Retrieval (2002)
Yuval Ishai, Eyal Kushilevitz, Jean-Francois Raymond
Private Information Retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic,...
On 2-Round Secure Multiparty Computation (2002)
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
Abstract. Substantial efforts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the...
Priced Oblivious Transfer: How to Sell Digital Goods (2001)
Bill Aiello, Yuval Ishai, Omer Reingold
Abstract. We consider the question of protecting the privacy of customers buying digital goods. More specifically, our goal is to allow a buyer to purchase digital goods from a vendor without letting...
Selective private function evaluation with applications to private statistics (2001)
Ran Canetti, Yuval Ishai, Ravi Kumar, Michael K. Reiters
Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client inter-acts with one...
On adaptive vs. non-adaptive security of multiparty protocols (2001)
Ran Canetti, Ivan Damgaard, Stefan Dziembowski, Yuval Ishai, Tal Malkin
protocols
Priced Oblivious Transfer: How to Sell Digital Goods (2001)
Bill Aiello, Yuval Ishai, Omer Reingold
Abstract We consider the question of protecting the privacy of customers buying digital goods. Morespecifically, our goal is to allow a buyer to purchase digital goods from a vendor without letting...
Secure multiparty computation of approximations (2001)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim
Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the...
Priced Oblivious Transfer: How to Sell Digital Goods (2001)
Bill Aiello, Yuval Ishai, Omer Reingold
Abstract. We consider the question of protecting the privacy of customers buying digital goods. More specifically, our goal is to allow a buyer to purchase digital goods from a vendor without letting...
Priced Oblivious Transfer: How to Sell Digital Goods (2001)
Bill Aiello, Yuval Ishai, Omer Reingold
Abstract. We consider the question of protecting the privacy of customers buying digital goods. More specifically, our goal is to allow a buyer to purchase digital goods from a vendor without letting...
Priced Oblivious Transfer: How to Sell Digital Goods (2001)
Bill Aiello, Yuval Ishai, Omer Reingold
We consider the question of protecting the privacy of customers buying digital goods. More specifically, our goal is to allow a buyer to purchase digital goods from a vendor without letting the...
On the power of nonlinear secret-sharing (2001)
A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The...
On adaptive vs. non-adaptive security of multiparty protocols (2001)
Ran Canetti, Ivan Damgaard, Stefan Dziembowski, Yuval Ishai, Tal Malkin
Security analysis of multiparty cryptographic protocols distinguishes between two types of adversarial settings: In the non-adaptive setting, the set of corrupted parties is chosen in advance, before...
Secure multiparty computation of approximations (2001)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes be used to obtain efficient solutions where no efficient exact computation is known. In particular, approximations are often useful in a distributed...
On adaptive vs. non-adaptive security of multiparty protocols (2001)
Ran Canetti, Ivan Damgaard, Stefan Dziembowski, Yuval Ishai, Tal Malkin
Security analysis of multiparty cryptographic protocols distinguishes between two types of adversarial settings: In the non-adaptive setting, the set of corrupted parties is chosen in advance, before...
Information-theoretic private information retrieval: A unified construction (2001)
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR protocol the...
Information-theoretic private information retrieval: A unified construction (2001)
Abstract. A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR...
Amos Beimel and Yuval Ishai Ben-Gurion University, Israel. beimel@cs.bgu.ac.il.
The Round-Complexity of Verifiable Secret-Sharing and Secure Multicast (2001)
Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Veriable...
Information-Theoretic Private Information Retrieval: A Unified Construction (2001)
Extended Abstract, Amos Beimel, Yuval Ishai
Amos Beimel and Yuval Ishai Ben-Gurion University, Israel. beimel@cs.bgu.ac.il.
Information-theoretic private information retrieval: A unified construction (2001)
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR protocol the...
Secure multiparty computation of approximations (2001)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim
Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the...
Information-theoretic private information retrieval: A unified construction (2001)
Abstract. A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR...
Reducing the servers' computation in private information retrieval: Pir with preprocessing (2000)
Amos Beimel, Yuval Ishai, Tal Malkin
Abstract. Private information retrieval (PIR) enables a user to retrieve a specific data item from a database, replicated among one or more servers, while hiding from each server the identity of the...
Motivated by questions about secure multi-party computation, we introduce and study a new natural representation of functions by polynomials, which we term randomizing polynomials. "Standard...
Reducing the servers' computation in private information retrieval: Pir with preprocessing (2000)
Amos Beimel, Yuval Ishai, Tal Malkin
Private information retrieval (PIR) enables a user to retrieve a data item from a database, replicated among one or more servers, while hiding the identity of the retrieved item. This problem was...
Universal Service-Providers for Database Private Information Retrieval \Lambda (1999)
Giovanni Di-crescenzoy, Yuval Ishai, Rafail Ostrovskyx
of this work was done while visiting Bellcore.
Improved upper bounds on information-theoretic private information retrieval (1999)
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit database x, replicated in k servers, while keeping the value of i private from each server. A t-private...
One-way functions are essential for single-server private information retrieval (1999)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
Private Information Retrieval (PIR) protocols allow a user to read information from a database without revealing to the server storing the database which information he has read. Kushilevitz and...
Improved upper bounds on information-theoretic private information retrieval (1999)
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit database x, replicated in k servers, while keeping the value of i private from each server. A t-private...
One-way Functions are Essential for Single-Server Private Information Retrieval (1999)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
Private Information Retrieval (PIR) protocols allow a user to read information from a database without revealing to the server storing the database which information he has read. Kushilevitz and...
One-way Functions are Essential for Single-Server Private Information Retrieval (1999)
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
Private Information Retrieval (PIR) protocols allow a user to read information from a database without revealing to the server storing the database which information he has read. Kushilevitz and...
Protecting Data Privacy in Private Information Retrieval Schemes (1999)
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit data string x, replicated in k 2 databases (in the information-theoretic setting) or in k 1 databases (in...
Protecting data privacy in private information retrieval schemes (1998)
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit data string x, replicated in k 2 databases (in the information-theoretic setting) or in k 1 databases (in...
Protecting data privacy in private information retrieval schemes (1998)
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of a data string x, replicated in k 2 databases, while keeping the value of i private. The main cost measure for such...
Protecting data privacy in private information retrieval schemes (1998)
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of a data string x, replicated in k 2 databases (in the information-theoretic setting) or k 1 databases (in the...
Non-interactive and non-malleable commitment (1998)
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky
A commitment protocol is a fundamental cryptographic primitive used as a basic building block throughout modern cryptography. In STOC 1991, Dolev Dwork and Naor showed that in many settings the...
Universal Service-Providers for Database Private Information Retrieval (1998)
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky
We consider the question of private information retrieval in the so-called "commoditybased " model. This model was recently proposed by Beaver for practically-oriented service-provider...
Protecting data privacy in private information retrieval schemes (1998)
Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin
These results also yield the first implementation of a distributed version of \Gamma n 1 \Delta-OT (1-out-of-n oblivious transfer) with information-theoretic security and sublinear communication...
on On Privacy and Partition Arguments 1 (1997)
A function and f (x1, x2,...,xn) is said to be t-private if there exists a (randomized) communication protocol for computing f, such that no coalition of at most t participants can infer any...
Private simultaneous messages protocols with applications (1997)
We study the Private Simultaneous Messages (PSM) model which is a variant of the model proposed in [15]. In the PSM model there are n players P 1; : : : ; Pn, each player P i holding a secret input x...
Private Simultaneous Messages Protocols with Applications (1997)
We study the Private Simultaneous Messages (PSM) model which is a variant of the model proposed in [16]. In the PSM model there are n players P 1 , ..., Pn , each player P i holding a secret input x...
Valid Generalisation from Approximate Interpolation (1996)
Martin Anthony, Peter Bartlett, Yuval Ishai, John Shawe-taylor
Let H and C be sets of functions from domain X to R. We say that H validly generalises C from approximate interpolation if and only if for each j ? 0 and ffl; ffi 2 (0; 1) there is m 0 (j; ffl; ffi)...
Valid generalisation from approximate interpolation (1994)
Martin Anthony, Peter Bartlett, Yuval Ishai, John Shawe-taylor
Let H and C be sets of functions from domain X to ℜ. We say that H validly generalises C from approximate interpolation if and only if for each η> 0 and ɛ, δ ∈ (0, 1) there is m0(η, ɛ,...
Valid generalisation from approximate interpolation (1994)
Martin Anthony, Peter Bartlett, Yuval Ishai, John Shawe-taylor
Let H and C be sets of functions from domain X to ℜ. We say that H validly generalises C from approximate interpolation if and only if for each η> 0 and ɛ, δ ∈ (0, 1) there is m0(η, ɛ,...
Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing
Amos Beimel, Yuval Ishai, Tal Malkin
Private information retrieval (PIR) enables a user to retrieve a specific data item from a database, replicated among one or more servers, while hiding from each server the identity of the retrieved...
Sufficient Conditions for Collision-Resistant Hashing
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
We present several new constructions of collision-resistant hash-functions (CRHFs) from general assumptions. We start with a simple construction of CRHF from any homomorphic encryption. Then, we...