This paper examines secure two-party computation of functions, which depend only on the Hamming distance of the inputs of the two parties.We present efficient protocols for computing these functions.In particular, we present protocols which are secure in the sense of full simulatability against malicious adversaries.We then show applications of HDOT.These include protocols for checking similarity between documents without disclosing additional information about them (these protocols are based on algorithms of Broder et al. for computing document similarity based on the Jaccard measure).Another application is a variant of symmetric private information retrieval (SPIR), which can be used if the server's database contains N entries, at most N / logN of which have individual values, and the rest are set to some default value.The receiver does not learn whether it receives an individual value or the default value.This variant of PIR is unique since it can be based on the existence of OT alone.
This paper examines secure two-party computation of functions, which depend only on the Hamming distance of the inputs of the two parties.We present efficient protocols for computing these functions.In particular, we present protocols which are secure in the sense of full simulatability against malicious adversaries.We then show applications of HDOT.These include protocols for checking similarity between documents without disclosing additional information about them (these protocols are based on algorithms of Broder et al. for computing document similarity based on the Jaccard measure).Another application is a variant of symmetric private information retrieval (SPIR), which can be used if the server's database contains N entries, at most N / logN of which have individual values, and the rest are set to some default value.The receiver does not learn whether it receives an individual value or the default value.This variant of PIR is unique since it can be based on the existence of OT alone.
In the problem of Secure Multi-party Computation, the objective is to design a protocol that allows a group of parties to securely compute functions of their collective private data, while ensuring that no party reveals any more information about its private data other than what must be inherently revealed by the computation results (privacy) and that no parties can disrupt or influence the computation results beyond the effects of changing their input data (correctness and consistency). Information theoretic approaches toward this problem, that provide provable (unconditional) security guarantees even against adversarial parties that have unbounded computational power, have established that general computation is possible in a variety of scenarios. However, these general solutions are not always efficient or finely tuned to the requirements of specific problems and applications.
The focus of this thesis is on the development of information theoretic approaches for multi-party computation applications with the common theme of secure and efficient computation and inference over a distributed data network. Specific applications include: 1) private information retrieval, where the objective is to privately retrieve data without revealing what was selected; 2) secure statistical analysis, the problem of extracting statistics without revealing anything else about the underlying data; 3) secure sampling, which is the secure generation of new data with a given distribution; and 4) secure authentication, where the identity of a party needs to authenticated via inference on his/her credentials and stored registration data.
The contributions of this thesis toward addressing these applications include the following: The development of an Oblivious Transfer (OT) protocol, applicable to private information retrieval, that trades off a small amount of privacy while being several times more efficient than other OT protocols. The efficiency of general se- cure two-party computation via OT realized from noisy channels is also analyzed. A technique for approximate secure multi-party computation applicable to secure statistical analysis of large scale distributed databases is developed. By exploiting a dimensionality reduction and the structure of a broad class of functions based on the computed statistics, the feasibility of simultaneously achieving both arbitrarily high accuracy and arbitrarily high communication efficiency is demonstrated. The region of distributions that can be securely sampled in the two-party scenario is characterized. It is further established that for those distributions, it can be accomplished with a protocol that only sends one message. Inner and outer bounds on the region of distributions that can be securely sampled in the general multi-party scenario are also developed. A new three-party protocol, applicable to the problem of secure biometric authentication, that securely computes the Hamming distance even when one of the parties arbitrarily deviates from the protocol is proposed and analyzed. A two-factor secure biometric authentication system that is robust against the compromise of registered biometric data, allowing for revocability and resistance against cross-enrollment attacks is also proposed.
Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.
Bringer et al. proposed two cryptographic protocols for the computation of Hamming distance. Their first scheme uses oblivious transfer and provides security in the semi-honest model. The other scheme uses committed oblivious transfer and is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. In this paper, we show that their protocol is not actually fully secure against malicious adversaries. More precisely, our attack breaks the soundness property of their protocol where a malicious user can compute a Hamming distance, which is different from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass the authentication without knowledge of the honest user's input with at most O(n) complexity instead of O(2n), where n is the input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of our modified protocol is proven using the simulation-based paradigm. Furthermore, as for efficiency concerns, the modified protocol utilizes verifiable oblivious transfer, which does not require the commitments to outputs, which improves its efficiency significantly.
We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs xA and xB respectively, to compute a function f(xA,xB) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(xA,xB) only when it equals a certain value of interest (such as "Yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xA,xB) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the "honest but curious" model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.
Secure 2PC (Two-Party Computation) is a research problem that abstracts a wide class of realworld applications with privacy concerns.In this problem, two parties want to collaboratively compute an objective function over their private inputs while the inputs are too valuable or sensitive to share with each other.For example, competing insurance companies may be interested in finding out the statistics of their aggregated client database but reluctant to reveal their own databases; drivers on the road may want to query the nearest gas station but hesitate to disclose their GPS coordinates.In this thesis, we constructed a framework for secure 2PC.This framework consists of a two-party interactive protocol and a few cryptographic building blocks.More specifically, the former comes from applying the cut-and-choose technique to the Yao protocol with the support of the latter, which are formally defined to capture the security properties needed in order to tackle the known attacks.We first proved that the main protocol indeed securely computes any single-output objective function even in the presence of malicious adversaries.Next, to demonstrate the power of this framework, we explicitly instantiated the building blocks by using number-theoretic assumptions and the technique of auxiliary circuits.We also presented techniques that allow our framework to handle from any single-output to any two-output objective functions.Finally, we implemented the framework to demonstrate its performance empirically.In particular, this implementation benefits from the embarrassingly parallelizable nature of our framework.