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...
ABSTRACT Private Approximation of NP-hard Functions [Extended Abstract] (2009)
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
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...
Hard Instances of the Constrained Discrete Logarithm Problem (2008)
Ilya Mironov, Anton Mityagin, Kobbi Nissim
Abstract. The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent x belongs to a set known to the attacker. The complexity of generic algorithms for solving...
Certi cate Revocation and Certi cate Update (2008)
Moni Naor, Moni Naor, Kobbi Nissim, Kobbi Nissim
A new solution is suggested for the problem of certi cate revocation. This solution represents Certi cate Revocation Lists by an authenticated search data structure. The process of verifying whether...
How Auditors May Inadvertently Compromise Your Privacy (2008)
Introduction ¢ Let be a database containing sensitive information £ about individuals. For ¢ example, may consist of medical or census data. We consider the setting where statistical or aggregate...
What Can We Learn Privately? (2008)
Kasiviswanathan, Shiva Prasad, Lee, Homin K., Nissim, Kobbi, Raskhodnikova, Sofya, Smith, Adam
Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be...
Ilya Mironov, Anton Mityagin, Kobbi Nissim
The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent x belongs to a set known to the attacker. The complexity of generic algorithms for solving the...
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...
Ilya Mironov, Anton Mityagin, Kobbi Nissim
The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent x belongs to a set known to the attacker. The complexity of generic algorithms for solving the...
ABSTRACT Private Approximation of Search Problems ∗ (2008)
Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb
Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...
ABSTRACT Private Approximation of Search Problems ∗ (2008)
Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb
Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...
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...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
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...
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...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
A secure function evaluation protocol allows two parties to jointly compute a function f(x; y) of their inputs in a manner not leaking more information than necessary. A major result in this field...
On cutting a few vertices from a graph (2007)
Uriel Feige, Robert Krauthgamer, Kobbi Nissim
We consider the problem of finding in an undirected graph a minimum cut that separates exactly a given number k of vertices. For general k (i.e. k is part of the input and may depend on n) this...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
Certi cate Revocation and Certi cate Update (2007)
Moni Naor, Moni Naor, Kobbi Nissim, Kobbi Nissim
A new solution is suggested for the problem of certi cate revocation. This solution represents Certi cate Revocation Lists by an authenticated search data structure. The process of verifying whether...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
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...
K.: Private approximation of clustering and vertex (2007)
Amos Beimel, Renen Hallak, Kobbi Nissim
Abstract. Private approximation of search problems deals with finding approximate solutions to search problems while disclosing as little information as possible. The focus of this work is on private...
Smooth sensitivity and sampling in private data analysis (2007)
We introduce a new, generic framework for private data analysis. The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals...
Hard Instances of the Constrained Discrete Logarithm Problem (2006)
Mironov, Ilya, Mityagin, Anton, Nissim, Kobbi
The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the...
Calibrating noise to sensitivity in private data analysis (2006)
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, Adam Smith
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query...
Calibrating noise to sensitivity in private data analysis (2006)
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, Adam Smith
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query...
Communication Efficient Secure Linear Algebra (2006)
Kobbi Nissim Enav, Kobbi Nissim, Enav Weinreb
We present communication efficient secure protocols for a variety of linear algebra problems. Our main building block is a protocol for computing Gaussian elimination on encrypted data. As input for...
Dan Boneh, Eu-jin Goh, Kobbi Nissim
Let ψ be a 2-DNF formula on boolean variables x1,..., xn ∈ {0, 1}. We present a homomorphic public key encryption scheme that allows the public evaluation of ψ given an encryption of the...
Calibrating noise to sensitivity in private data analysis (2006)
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, Adam Smith
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query...
Private approximation of search problems (2006)
Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb
Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...
Private approximation of search problems (2006)
Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb
Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...
Communication efficient secure linear algebra (2006)
We present communication efficient secure protocols for a variety of linear algebra problems. Our main building block is a protocol for computing Gaussian elimination on encrypted data. As input for...
Communication efficient secure linear algebra (2006)
Abstract. We present communication efficient secure protocols for a variety of linear algebra problems. Our main building block is a protocol for computing Gaussian Elimination on encrypted data. As...
Krishnaram Kenthapadi, Nina Mishra, Kobbi Nissim
Given a data set consisting of private information about individuals, we consider the online query auditing problem: given a sequence of queries that have already been posed about the data, their...
Secure discsp protocols - from centralized towards distributed solutions (2005)
Abstract. We present new protocols for secure distributed constraint satisfaction problems (DisCSPs). The presented protocols are the first to enable an oblivious use of advanced search techniques...
Krishnaram Kenthapadi, Nina Mishra, Kobbi Nissim
Given a data set consisting of private information about individuals, we consider the online query auditing problem: given a sequence of queries that have already been posed about the data, their...
Practical privacy: The SuLQ framework (2005)
Avrim Blum, Cynthia Dwork, Frank Mcsherry, Kobbi Nissim
Abstract. We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a...
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...
Efficient private matching and set intersection (2004)
Michael J. Freedman, Kobbi Nissim, Benny Pinkas
Abstract. We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many...
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...
Privacy-preserving datamining on vertically partitioned databases (2004)
Abstract. In a recent paper Dinur and Nissim considered a statistical database in which a trusted database administrator monitors queries and introduces noise to the responses with the goal of...
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...
Revealing information while preserving privacy (2003)
We examine the tradeoff between privacy and usability of statistical databases. We model a statistical database by an n-bit string d1,.., dn, with a query being a subset q ⊆ [n] to be answered by...
Revealing information while preserving privacy (2003)
Abstract We examine the tradeoff between privacy and usability of statistical databases. We modela statistical database by an n-bit string d1,.., dn, with a query being a subset q ` [n] to beanswered...
Revealing information while preserving privacy (2003)
Abstract We examine the tradeoff between privacy and usability of statistical databases. Our mainresult is a polynomial reconstruction algorithm of data from noisy (perturbed) subset sums. Applying...
Revealing information while preserving privacy (2003)
We examine the tradeoff between privacy and usability of statistical databases. Our main result is a polynomial reconstruction algorithm of data from noisy (perturbed) subset sums. Applying this...
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...
Communication Complexity and Secure Function Evaluation (2001)
We suggest two new methodologies for the design of efficient secure protocols, that differ with respect to their underlying computational models. In one methodology we utilize the communication...
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...
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...
Communication preserving protocols for secure function evaluation (2001)
A secure function evaluation protocol allows two parties to jointly compute a function f(x; y) of their inputs in a manner not leaking more information than necessary. A major result in this field...
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...
Approximating the Minimum Bisection Size (extended Abstract) (2000)
Uriel Feige, Robert Krauthgamer, Kobbi Nissim
) Uriel Feige Robert Krauthgamer Kobbi Nissim Deptartment of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot 76100, Israel ffeige,robi,kobbig@wisdom.weizmann.ac.il...
On the Hardness of Approximating (2000)
Witnesses Uriel Feige, Uriel Feige, Michael Langberg, Kobbi Nissim
. The search version for NP-complete combinatorial optimization problems asks for finding a solution of optimal value. Such a solution is called a witness. We follow a recent paper by Kumar and...
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...
Firmato: A Novel Firewall Management Toolkit (1999)
Yair Bartal, Alain Mayer, Kobbi Nissim, Avishai Wool
In recent years firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc) and wide-spread deployment. In contrast, firewall and security...
Firmato: A novel firewall management toolkit (1999)
Yair Bartal, Alain Mayer, Kobbi Nissim, Avishai Wool
In recent years packet-filtering firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc.) and wide-spread deployment. In contrast,...
Certificate Revocation and Certificate Update (1998)
We present a solution for the problem of certificate revocation. This solution represents Certificate Revocation Lists by authenticated dictionaries that support (i) efficient verification whether a...
Certificate Revocation and Certificate Update (1998)
Moni Naor Kobbi, Moni Naor, Kobbi Nissim
A new solution is suggested for the problem of certificate revocation. This solution represents Certificate Revocation Lists by an authenticated search data structure. The process of verifying...
Certificate Revocation and Certificate Update (1998)
A new solution is suggested for the problem of certificate revocation. This solution represents Certificate Revocation Lists by an authenticated search data structure. The process of verifying...
On the Use of Interactive Proofs for Formal Program Verification (1997)
Automatic program verification is a computationally intense task. When a verifier declares a program correct, there still remains the question of whether the verifier itself made no errors in the...
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...
On the Security of Pay-Per-Click and Other Web Advertising Schemes
Vinod Anupam, Alain Mayer, Kobbi Nissim, Benny Pinkas, Michael K. Reiter
We present a hit inflation attack on pay-per-click Web advertising schemes. Our attack is virtually impossible for the program provider to detect conclusively, regardless of whether the provider is a...
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...