This paper is about the Oblivious Transfer in the distributed model recently proposed by M. Naor and B. Pinkas. In this setting a Sender has n secrets and a Receiver is interested in one of them. During a set up phase, the Sender gives information about the secrets to m servers. Afterwards, in a recovering phase, the receiver can compute the secret she wishes by interacting with k of them. More precisely, from the answers received she computes the secret in which she is interested but she gets no information on the others and, at the same time, any coalition of k 1 servers can neither compute any secret nor gure out which one the receiver has recovered.
This paper is about the Oblivious Transfer in the distributed model recently proposed by M. Naor and B. Pinkas. In this setting a Sender has n secrets and a Receiver is interested in one of them. During a set up phase, the Sender gives information about the secrets to m servers. Afterwards, in a recovering phase, the receiver can compute the secret she wishes by interacting with k of them. More precisely, from the answers received she computes the secret in which she is interested but she gets no information on the others and, at the same time, any coalition of k 1 servers can neither compute any secret nor gure out which one the receiver has recovered.
This paper is about unconditionally secure distributed protocols for oblivious transfer, as proposed by Naor and Pinkas and generalized by Blundo et al. In this setting a Sender has ζ secrets and a Receiver is interested in one of them. The Sender distributes the information about the secrets to n servers, and a Receiver must contact a threshold of the servers in order to compute the secret. We present a non-existence result and a lower bound for the existence of one-round, threshold, distributed oblivious transfer protocols, generalizing the results of Blundo et al. A threshold based construction implementing 1-out-of-ζ distributed oblivious transfer achieving this lower bound is described. A condition for existence of distributed oblivious transfer schemes based on general access structures is proven. We also present a general access structure protocol implementing 1-out-of-ζ distributed oblivious transfer.
In the various 1-out-of-n distributed oblivious transfer protocols (DOT) designed in an unconditionally secure environment, a receiver contacts k out of m servers to obtain one of the n secrets held by a sender. After a protocol has been executed, the sender has no information on the choice of the receiver and the receiver has no information on the secrets she did not obtain. Likewise, a coalition of k − 1 servers is unable to infer any information, neither on the sender’s secrets, nor on the receiver’s choice. These protocols are based on a semi-honest model: no mechanism prevents a group of malicious servers from disrupting the protocol such that the secret obtained by the receiver does not correspond to the chosen secret. Actually, to verify the information transmitted by the servers seems to require some properties difficult to reconcile: on one hand the receiver has to collect more information from the servers to discard the incorrect data generated by the malicious servers; on the other hand, if the receiver is allowed to gather more information from the servers, the sender’s security may be compromised. We study the first unconditionally secure DOT protocol in the presence of an active adversary who may corrupt up to k − 1 servers. In addition to the active adversary, we also assume that the sender may (passively) corrupt up to k − 1 servers to learn the choice of the receiver. Similarly, the receiver may (passively) corrupt up to k − 1 servers to learn more than the chosen secret. However, we assume that the sender, receiver, and active adversary do not collaborate with each other. Our DOT protocol allows the receiver to contact 4k − 3 servers to obtain one secret, while the required security is maintained.
The security of digital goods buyers and sellers is unbalanced. Of course, the property of sellers is protected; for example, when customers acquire digital books or films from Internet's merchants, they only receive the products they have paid for. Unfortunately, the buyers' privacy is rarely respected: purchases are often — without the buyers' knowledge — monitored, recorded, analysed, and sometimes sold to marketing companies. As a consequence, even if the customers do not intend to acquire additional products, their computer screens are later invaded with targeted advertisements. The main purpose of this thesis is to propose some methods to restore the balance and guarantee the buyers' privacy, while protecting the interests of the sellers. To this end, it is worth looking into the area of cryptography and more specifically, it is worth studying and designing some protocols called distributed oblivious transfer (DOT) protocols. A DOT protocol allows a party A to obtain one of the secret pieces of information (a secret for short) held by a party B so that the following two fundamental conditions are satisfied: • A chooses the secrets she wishes to obtain and does not obtain anything on the secrets she has not chosen, • B does not learn which secret was obtained by A. Furthermore, to improve the availability of the information, the protocol is distributed. That is, the party B transmits his secret information to m servers and the party A needs to contact at least k of these servers to obtain the chosen secret. The servers are not fully trusted, neither by A, nor by B. Therefore, from the information exchanged with A and B, no coalition of servers should be able to learn the secrets of B or the choice of A. The results of a preliminary literature review are surprising. In fact, the number of publications on DOT protocols is small (fewer than 20) compared to, for example, the number of publications on a similar concept, secret sharing (100s of publications). And yet, oblivious transfer is a fundamental component of more complex cryptographic protocols such as multi-party computation protocols, which allow a group of participants to securely calculate any function of their joint secret inputs. So, one could expect many variants, for example of the original DOT protocol introduced in 2002 by Naor and Pinkas [74], to fulfil the requirements of specific scenarios. The design of variants of DOT protocols in traditional cryptography has been the guiding thread of my research. My contribution mainly consists in (a) a critical analysis of the existing protocols, demonstrating their limitations, weaknesses, and in some cases, flaws; and (b) the design of the following protocols,well adapted to some specific situations: A Strongly Secure DOT Protocol. This DOT protocol addresses the most important weakness of unconditionally secure, one-round, polynomial interpolation-based DOT protocols: after the protocol has been executed, if the party A corrupts only one server, she can learn all the secrets of the party B. The protocol is secure even if A corrupts up to k - 1 servers. A Verifiable DOT Protocol. The party A should obtain the secret she has chosen, even when some servers are controlled by a malicious adversary whose objective is to sabotage the protocol. This is the case with this protocol, assuming that the adversary cannot control more than k - 1 servers. A Multiple Secrets DOT Protocol. When the party A wishes to obtain n > 1 secrets, the current protocols have to be executed n times. In this context, they are inefficient. The DOT protocol introduced here allows the party A, by contacting in the same session k - 1 + n servers, to collect n secrets. Adaptive DOT Protocols. The previous protocol allows the party A to request several secrets. However, the request of one secret may depend on the values of secrets already obtained. Two efficient protocols are presented in this scenario. The first one allows A to receive a limited number of secrets and therefore, is well adapted to a single receiver. For several receivers, a second protocol is proposed. This second protocol accepts an unlimited number of queries, but requires communications amongst the servers. A Threshold DOT protocol. Most existing DOT protocols rely on threshold secret sharing schemes. In a k-threshold protocol or scheme, security is guaranteed not only when k parties are contacted, but also when more than k parties are contacted. However, the existing DOT protocols based on k-threshold secret sharing schemes require an additional mechanism to control that exactly k servers are contacted, which is an under-utilisation of the underlying functionality. The proposed protocol is the first k-threshold DOT protocol which allows the party A to contact as many servers as she wishes to obtain the chosen secret, provided that at least k servers are contacted. This research is limited to unconditionally secure protocols, i.e., protocols whose security does not depend on mathematical (unproven) assumptions; within the limits of the given security models, the protocols are secure even against an adversary with unlimited computing power and time. In brief, the results presented in this thesis are a significant advance to the state of the art research on DOT protocols because on one hand, they point out the weaknesses of the DOT protocols most commonly accepted by the cryptographic community and on the other hand, they contribute to the cryptographic field through the design of new protocols, secure and efficient.
Naor and Pinkas (1999a) pointed out that 'this is of interest, given the possibility of implementing Oblivious Transfer using physical means, e.g., via a noisy channel or quantum cryptography. However, some of these reductions are not particularly efficient. .. '. Using tamper-proof smart cards, we propose some radically different approaches to the Oblivious Transfer problem. Despite the simplicity of our model, we achieve unconditional security and privacy for both the sender and receiver. In contrast to all known oblivious transfer protocols, which require extensive computations, the proposed schemes are very computationally efficient.
Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.
Two novel constructions of one out of n oblivious transfer protocols from bilinear maps between groups are proposed. The protocols satisfy the category of non-interactive, mean that any sender S can obliviously transfer some secret(s) to a receiver R, but R does not send any messages back to S. The choice of a receiver is unconditionally secure. A sender's secrecy is guaranteed if the receiver is semi-honest in a standard model since the decision bilinear Diffie-Hellman problem is hard and the sender's secrecy is achieved when the receiver is a malicious party in a random oracle model since the bilinear Diffie-Hellman problem assumption holds. When a sender is a cheating party, the receiver will detect him/her and halt the protocol. A precise proof of the security of the protocols is presented.