Optimal Cryptographic Hardness of Learning Monotone Functions (2009)
Dana Dachman-soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee
Abstract. A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time...
Columbia Univ. New York, NY LP Decoding Corrects a Constant Fraction of Errors (2009)
Abstract — We show that for low-density paritycheck (LDPC) codes with sufficient expansion, the Linear Programming (LP) Decoder corrects a constant fraction of errors. I.
Secure Network Coding via Filtered Secret Sharing ∗ (2009)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We study the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. We...
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...
Jon Feldman, Cliff Stein, Tal Malkin, Rocco A. Servedio, Martin J. Wainwright
We show that for low-density parity-check (LDPC) codes with sufficient expansion, the
Oblivious Image Matching (2008)
Shai Avidan, Ariel Elbaz, Tal Malkin, Ryan Moriarty
Abstract. We present the problem of Oblivious Image Matching, where two parties want to determine whether they have images of the same object or scene, without revealing any additional information....
On the Capacity of Secure Network Coding (2008)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We consider the problem of using a multicast network code to transmit information securely in the presence of a "wire-tap " adversary who can eavesdrop on a bounded number of...
Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky
Abstract. A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We...
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...
Yael Gertner, Tal Malkin, Steven Myers
Abstract We address the question of whether or not semantically secure public-key encryption primitives implythe existence of chosen ciphertext attack (CCA) secure primitives. We show a black-box...
How Should We Solve Search Problems Privately? (2008)
Amos Beimel, Tal Malkin, Kobbi Nissim
Abstract. Secure multiparty computation allows a group of distrusting parties to jointly compute a (possibly randomized) function of their inputs. However, it is often the case that the parties...
Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky
Abstract. A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We...
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...
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...
Secure Multiparty Computation of Approximations (Extended Abstract) (2007)
Joan Feigenbaum, 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...
Efficient Distributed ( n 1) Oblivious Transfer (2007)
In this paper, we present a new application for \Gamma n 1
E cient Distributed ( n 1) Oblivious Transfer (2007)
In this paper, we present a new application for, n 1 oblivious transfer, which isaninteractive protocol between two parties Alice and Bob, where Alice has n secrets and Bob has a query i. At the end...
Yael Gertner, Shafi Goldwasser, Tal Malkin
Private information retrieval (PIR) schemes enable users to obtain information from databases while keeping their queries secret from the database managers. We propose a new model for PIR, utilizing...
Composition and Eciency Tradeos for Forward-Secure Digital Signatures (2007)
Tal Malkin, Daniele Micciancio, Sara Miner
Forward-secure digital signatures, initially proposed by Anderson in CCS 97 and formalized by Bellare and Miner in Crypto 99, are signature schemes which enjoy the additional guarantee that a...
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...
Oblivious Image Matching (2007)
Avidan, Shai, Elbaz, Ariel, Malkin, Tal, Moriarty, Ryan
We present the problem of Oblivious Image Matching, where two parties want to determine whether they have images of the same object or scene, without revealing any additional information. While image...
ProSiBIR: Proactive Signer-Base Intrusion Resilient Signatures (2007)
The notion of Signer-Base Intrusion-Resilient (SiBIR) signatures was introduced in [IR02] as a scheme that can withstand an arbitrary number of key-exposures, as long as both of its modules are not...
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...
Mercurial commitments with applications to zero-knowledge sets (2005)
Melissa Chase, Er Healy, Anna Lysyanskaya, Tal Malkin, Leonid Reyzin
Abstract. We introduce a new flavor of commitment schemes, which we call mercurial commitments. Informally, mercurial commitments are standard commitments that have been extended to allow for soft...
Rosario Gennaro, Anna Lysyanskaya, Tal Malkin, Silvio Micali
Abstract. Traditionally, secure cryptographic algorithms provide security against an adversary who has only black-box access to the secret information of honest parties. However, such models are not...
People What's Ahead ● Overview of IDS (2004)
Michael Locasto, Janak Parekh, Sal Stolfo, Angelos Keromytis, Tal Malkin, Vishal Misra, ...
● Distributed largescale threats – Money is the motivator (no longer a kid looking for notoriety) ● P2P collaboration is the key to responding –...
LP decoding corrects a constant fraction of errors (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cli Stein, Martin J. Wainwright
We show that for low-density parity-check (LDPC) codes with sucient expansion, the Linear Programming (LP) Decoder of Feldman, Karger and Wainwright (Allerton, 2003) can correct a constant fraction...
The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures (2004)
Tal Malkin, Satoshi Obana, Moti Yung
Abstract. For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of...
The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures (2004)
Tal Malkin, Satoshi Obana, Moti Yung
Abstract. For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of...
A quantitative approach to reductions in secure computation (2004)
Secure computation is one of the most fundamental cryptographic tasks. It is known that all functions can be computed securely in the information theoretic setting, given access to a black box for...
A quantitative approach to reductions in secure computation (2004)
Abstract Secure computation is one of the most fundamental cryptographic tasks. It is known that all functionscan be computed securely in the information theoretic setting, given access to a black...
LP decoding corrects a constant fraction of errors (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright
Abstract—We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a...
The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures (2004)
Tal Malkin, Satoshi Obana, Moti Yung
Abstract. For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of...
On the capacity of secure network coding (2004)
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein
We consider the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. Cai...
On the performance, feasibility, and use of forward-secure signatures (2003)
Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures...
On adaptive vs. non-adaptive security of multiparty protocols (2001)
Ran Canetti, Ivan Damgaard, Stefan Dziembowski, Yuval Ishai, Tal Malkin
protocols
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...
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...
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...
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...
Single Database Private Information Retrieval Implies Oblivious Transfer (2000)
Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky
A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We call a PIR...
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...
Single database private information retrieval implies oblivious transfer (2000)
Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky
Work done at the Massachusetts Institute of Technology. Abstract. A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry...
The all-or-nothing nature of two-party secure computation (1999)
Amos Beimel, Tal Malkin, Silvio Micali
A function f is computationally securely computable if two computationally-bounded parties, Alice, having a secret input x, and Bob, having a secret input y, can talk back and forth so that (even if...
The all-or-nothing nature of two-party secure computation (1999)
Amos Beimel, Tal Malkin, Silvio Micali
Abstract. A function f is computationally securely computable if two computationally-bounded parties Alice, having a secret input x, and Bob, having a secret input y, can talk back and forth so that...
Efficient Communication-Storage Tradeoffs for Multicast Encryption (1999)
Ran Canetti, Tal Malkin, Kobbi Nissim
Abstract. We consider re-keying protocols for secure multicasting in a dynamic multicast group with a center. There is a variety of different scenarios using multicast, presenting a wide range of...
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...
The All-or-Nothing Nature of Two-Party Secure Computation (1999)
Amos Beimel Tal, Tal Malkin, Silvio Micali
. A function f is computationally securely computable if two computationally-bounded parties Alice, having a secret input x, and Bob, having a secret input y, can talk back and forth so that (even if...
The All-or-Nothing Nature of Two-Party Secure Computation (1999)
Amos Beimel, Tal Malkin, Silvio Micali
. A function f is computationally securely computable if two computationally-bounded parties Alice, having a secret input x, and Bob, having a secret input y, can talk back and forth so that (even if...
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...
The All-or-Nothing Nature of Two-Party Secure Computation (1999)
Amos Beimel, Tal Malkin, Silvio Micali
A function f is computationally securely computable if two computationally-bounded parties Alice, having a secret input x, and Bob, having a secret input y, can talk back and forth so that (even if...
The All-or-Nothing Nature of Two-Party Secure Computation (1999)
Amos Beimel, Tal Malkin, Silvio Micali
A function f is computationally securely computable if two computationally-bounded parties Alice, having a secret input x, and Bob, having a secret input y, can talk back and forth so that (even if...
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...
A random server model for private information retrieval (1998)
Yael Gertner, Sha Goldwasser, Tal Malkin
Private information retrieval (PIR) schemes provide a user with information from a database while keeping his query secret from the database manager. We propose a new model for PIR, utilizing...
A random server model for private information retrieval (1998)
Yael Gertner, Shafi Goldwasser, Tal Malkin
Private information retrieval (PIR) schemes provide a user with information from a database while keeping his query secret from the database manager. We propose a new model for PIR, utilizing...
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...
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...
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...
Efficient Communication-Storage Tradeoffs for Multicast Encryption
Ran Canetti, Tal Malkin, Kobbi Nissim
. We consider re-keying protocols for secure multicasting in a dynamic multicast group with a center. There is a variety of different scenarios using multicast, presenting a wide range of efficiency...
Efficient Communication-Storage Tradeoffs for Multicast Encryption
Ran Canetti Tal, Tal Malkin, Kobbi Nissim
. We consider re-keying protocols for secure multicasting in a dynamic multicast group with a center. There is a variety of different scenarios using multicast, presenting a wide range of efficiency...