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.
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.
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.
We study Distributed Oblivious Transfer(DOT) scheme in the adaptive version, which means the receiver should ask threshold number of servers to retrieve each secret, and the receiver could adaptively determine which secret would be retrieved and which servers to query. This protocol has both advantages of DOT and adaptive OT, thus inherently has good broad uses. Our first attempt to build such scheme follows the present DOT scheme and considers the semi-honest parties. The second protocol strengthens the security of the first one. It prevents potential malicious behaviors of servers, therefore it is a verifiable distributed oblivious transfer scheme with adaptive queries.
Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications such as secure multi-party computation, private information retrieval, private set intersection, contract signing, and privacy-preserving location-based services. The OT protocol has different variants such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. In the OT (one-out-of-2, one-out-of- n , and OT extension) protocol, the sender has a set of messages, whereas the receiver has a key. The receiver sends that key to the sender in a secure way; the sender cannot get any information about the received key. The sender encrypts every message by operating on every message using the received key and sends all the encrypted messages to the receiver. The receiver is able to extract only the required message using his key. However, in the k -out-of- n OT protocol, the receiver sends a set of k keys to the sender, and in replay, the sender sends all the encrypted messages. The receiver uses his keys and extracts the required messages, but it cannot gain any information about the messages that it has not requested. Generally, the OT protocol requires high communication and computation cost if we transfer millions of oblivious messages. The OT extension protocol provides a solution for this, where the receiver transfers a set of keys to the sender by executing a few numbers of OT protocols. Then, the sender encrypts all the messages using cheap symmetric key cryptography with the help of a received set of keys and transfers millions of oblivious messages to the receiver. In this work, we present different variants of OT protocols such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. Furthermore, we cover various aspects of theoretical security guarantees such as semi-honest and malicious adversaries, universally composable, used techniques, computation, and communication efficiency aspects. From the analysis, we found that the semi-honest adversary-based OT protocols required low communication and computation costs as compared to malicious adversary-based OT protocols.
In 1-out-of-qOblivious Transfer (OT) protocols, a sender Alice is able to send one ofq≥2messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners takeninstances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of thenoriginal OT instances are secure. We present new 1-out-of-qOT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given anFq-linear secret sharing scheme on a set ofnparticipants and adversary structureA, we can construct ann-server, 1-out-of-qOT combiner that is secure against an adversary corrupting either Alice and a set of servers inA, or Bob and a set of serversBwithBˉ∈/A. If the normalized total share size of the scheme is$\ell ,thentheresultingOTcombinerrequires\ell callstoOTprotocols,andthetotalamountofbitsexchangedduringtheprotocolis(q^{2}+q+1)\ell \log q.Wealsopresentaconstructionbasedon1−out−of−2OTcombinersthatusestheprotocolofCreˊpeau,BrassardandRobert(FOCS1986).Thisconstructionprovidessmallercommunicationcostsforcertainadversarystructures,suchasthresholdones:Foranyprimepowerq\geq n,therearen−server,1−out−of−qOTcombinersthatareperfectlysecureagainstactiveadversariescorruptingeitherAliceorBob,andaminorityoftheOTcandidates,exchangingO(qn\log q)$bits in total.