There are often situations where two remote users each have data, and wish to (i) verify the equality of their data, and (ii) whenever a discrepancy is found afterwards, determine which of the two modified his data. The most common example is where they want to authenticate messages they exchange. Another possible example is where they have a huge database and its mirror in remote places, and whenever a discrepancy is found between their data, they can determine which of the two users is to blame.Of course, if one is allowed to use computational assumptions, this function can be realized readily, e.g., by using digital signatures. However, if one needs information-theoretic security, there is no known method that realizes this function efficiently, i.e., with secret key, communication, and trusted third parties all being sufficiently small.In order to realize this function efficiently with information-theoretic security, we here define the "equality-testing protocol with dispute resolution" as a new framework. The most significant difference between our protocol and the previous methods with similar functions is that we allow the intervention of a trusted third party when checking the equality of the data. In this new framework, we also present an explicit protocol that is information-theoretically secure and efficient.
There are often situations where two remote users each have data, and wish to (i) verify the equality of their data, and (ii) whenever a discrepancy is found afterwards, determine which of the two modified his data. The most common example is where they want to authenticate messages they exchange. Another possible example is where they have a huge database and its mirror in remote places, and whenever a discrepancy is found between their data, they can determine which of the two users is to blame.Of course, if one is allowed to use computational assumptions, this function can be realized readily, e.g., by using digital signatures. However, if one needs information-theoretic security, there is no known method that realizes this function efficiently, i.e., with secret key, communication, and trusted third parties all being sufficiently small.In order to realize this function efficiently with information-theoretic security, we here define the "equality-testing protocol with dispute resolution" as a new framework. The most significant difference between our protocol and the previous methods with similar functions is that we allow the intervention of a trusted third party when checking the equality of the data. In this new framework, we also present an explicit protocol that is information-theoretically secure and efficient.
Secure multiparty computation was firstly introduced by Yao in 1982. Two-party equality testing is a special case of secure multiparty computation. It enables two entities to compare the equality of their secret data without revealing the data to the other party. This kind of protocols has been wildly investigated in the literature. However, in most of the existing protocols, the testing result is known by only one entity (informer). The other entity is informed about the testing result by the informer so she must fully trust the informer about the result she received. In this paper, we propose a new two-party equality testing protocol. In our protocol, although the final result is still informed by the informer, we allow the entity being informed to verify the correctness of the final result. In this way, the two entities can make sure whether the secret information they preserved are equivalent or not without revealing it. We will also give the security analysis and show that this protocol does not leak any information about the secret value.
Let us consider a situation where two information brokers, whose currency is, of course, information, need to reciprocally exchange information. The two brokers, being somewhat distrustful, would like a third, mutually trusted entity to be involved in the exchange process so as to guarantee the successful completion of the transaction and also verify that it indeed took place. Can this be completed in such a way that both brokers receive their information simultaneously and securely, without the trusted intermediary knowing the exchanged information? This work presents and rigorously analyzes a new quantum entanglement-based protocol that provides a solution to the above problem. The proposed protocol is aptly named the entanglement-based reciprocal simultaneous information exchange protocol. Its security is ultimately based on the assumption of the existence of a third, trusted party. Although the reciprocal information flow is between our two information brokers, the third entity plays a crucial role in mediating this process by being a guarantor and a verifier. The phenomenon of quantum entanglement is the cornerstone of this protocol, as it makes its implementation possible even when all entities are spatially separated and ensures that, upon completion, the trusted third party remains oblivious to the actual information that was exchanged.
At present, research on secure multi-party computation is of great interest in modern cryptography. It should be acknowledged that if any function can be computed securely, then it results in a very powerful tool. In fact, all natural protocols are, or can be rephrased to be, special cases of the multi-party computation problems. Design and analysis of the special multi-party computation protocols is meaningful and has attracted much interest in this field. Based on the combination of a public-key cryptosystem of the homomorphic encryption and on the theoretic construction relying on the F-hiding assumption, a protocol for comparing information of equality is proposed. The protocol needs only a single round of interaction and ensures fairness, efficiency and security. The protocol is fair, which means that one party knows the sound result of the comparison if and only if the other one knows the result. The protocol is efficient with the help of an oblivious third party for calculating. However, the third party cannot learn any information about the participant抯 private inputs and even about the comparison result, and cannot collude with any participant. The protocol is secure for the two participants, that is, any information about their secret input will not leak except the final computation result. A precise proof of security of the protocol is presented. Applications of this protocol may include private bidding and auctions, secret ballot elections, commercial business, identification in a number of scenarios and so on. It is believed that the protocol may be of practical significance for electronic transaction.
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.
It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.