In this thesis, we are interested in the theory of unconditional secure two-party computations of which Oblivious Transfer (OT) and Bit Commitment (BC) are the central primitives. On one hand, my works are inspired from Crépeau's et al.'s framework of building of OT protocol from noisy communication channels. The principle of this framework is to conceive, from noisy channels, an intermediate erasure model which is a variant of OT. We contributed to this framework by proposing a more general intermediate model, the Binary Symmetric Multi-Error-Rate Channel, which also can be built from noisy channels. With this intermediate model, we can build OT protocol from the noisy channels more effectively. In addition, we expose some case studies on emulating noisy models by a quantum nonorthogonal coding (QNOC) scheme which uses two non-orthogonal pure states for encoding two values of the classical bit. On the other hand, we revise the quantum model for general two-party protocols concerning classical and quantum computations and communications. We state that in the general model, a classical channel is inevitably macroscopic and its decoherence is so strong that quantum information is not accepted to be transfered on it. Thus, the quantum model for two-party protocols becomes three-party, including an environment of the channel. Indeed, with the faithful interpretation of general quantum two-party protocols in this three-party model, we reaffirm the no-go theorems of Mayers and Lo & Chau on the impossibilities of quantum OT, BC. In addion, we can go further to apply these negative results to protocols using some quantum trusted oracles, such as Coin-Flipping.
In this thesis, we are interested in the theory of unconditional secure two-party computations of which Oblivious Transfer (OT) and Bit Commitment (BC) are the central primitives. On one hand, my works are inspired from Crépeau's et al.'s framework of building of OT protocol from noisy communication channels. The principle of this framework is to conceive, from noisy channels, an intermediate erasure model which is a variant of OT. We contributed to this framework by proposing a more general intermediate model, the Binary Symmetric Multi-Error-Rate Channel, which also can be built from noisy channels. With this intermediate model, we can build OT protocol from the noisy channels more effectively. In addition, we expose some case studies on emulating noisy models by a quantum nonorthogonal coding (QNOC) scheme which uses two non-orthogonal pure states for encoding two values of the classical bit. On the other hand, we revise the quantum model for general two-party protocols concerning classical and quantum computations and communications. We state that in the general model, a classical channel is inevitably macroscopic and its decoherence is so strong that quantum information is not accepted to be transfered on it. Thus, the quantum model for two-party protocols becomes three-party, including an environment of the channel. Indeed, with the faithful interpretation of general quantum two-party protocols in this three-party model, we reaffirm the no-go theorems of Mayers and Lo & Chau on the impossibilities of quantum OT, BC. In addion, we can go further to apply these negative results to protocols using some quantum trusted oracles, such as Coin-Flipping.
Dans cette thèse, nous sommes intéressés à la construction inconditionnelle du calcul sécurisé à deux parties dont Oblivious Transfer (OT) et Bit Commitment (BC) sont les primitifs fondamentaux. D'une part, mes oeuvres sont inspirées du framework de Crépeau et al. pour la construction de OT à partir des canaux bruités. Le principe est de concevoir, à partir des canaux bruités, un modèle d'effacement intermédiaire qui est un variant de OT. Nous avons contribué à ce framework en proposant un modèle intermédiaire plus générique, le Binary Symmetric Multi-Error-Rate Channel, qui peut également être construit à partir des canaux bruités. Avec ce modèle intermédiaire, nous pouvons construire le protocole de OT de manière plus efficace. En outre, nous exposons quelques études de cas sur l'émulation des modèles bruités par un codage quantique nonorthogonal qui utilise deux états non-orthogonaux pour coder deux valeurs du bit classique. D'autre part, nous révisons le modèle quantique des protocoles quantiques à deux parties, couvrant les calculs et les communications classiques. Nous constatons que, dans le modèle général, un canal classique est inévitablement macroscopique et la decoherence est si forte que l'information quantique n'est pas acceptée d'être transférée sur ce canal. Ainsi, le modèle quantique des protocoles à deux parties consiste en trois parties, y compris l'environnement du canal. Avec cette fidèle interprétation, nous réaffirmons les théorèmes No-go de Mayers et Lo & Chau sur l'impossibilité de OT, BC quantiques. En addion, nous pouvons étendre ces résultats négatifs aux protocoles utilisant certains oracles quantiques, comme Coin-Flipping.
Oblivious transfer (OT) and bit commitment (BC) are two-party cryptographic protocols which play crucial roles in the construction of various cryptographic protocols. We propose three practical quantum cryptographic protocols in this paper. We first construct a practical quantum random oblivious transfer (R-OT) protocol based on the fact that non-orthogonal states cannot be reliably distinguished. Then, we construct a fault-tolerant one-out-of-two oblivious transfer ( O T 1 2 ) protocol based on the quantum R-OT protocol. Afterwards, we propose a quantum bit commitment (QBC) protocol which executes the fault-tolerant O T 1 2 several times. Mayers, Lo and Chau (MLC) no-go theorem proves that QBC protocol cannot be unconditionally secure. However, we find that computing the unitary transformation of no-go theorem attack needs so many resources that it is not realistically implementable. We give a definition of physical security for QBC protocols and prove that the practical QBC we proposed is physically secure and can be implemented in the real world.
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.
In this article, we are interested in the physical model of general quantum protocols implementing secure two-party computations in the light of Mayers' and Lo's & Chau's no-go theorems of bit commitment and oblivious transfer. In contrast to the commonly adobted quantum pure two-party model in the literature where classical communication is normally ignored, we propose an alternative interpretation for the purification of classical communication in two-party protocols by introducing a quantum third party for the classical channel. This interpretation leads to a global three-party model, involving Alice's and Bob's machines and the environment coupled to the macroscopic channel, using the decoherence scheme in quantum measurements. This model could give a more general view on the concealing/binding trade-off of quantum bit commitment protocols. Inspired from this three-party interpretation, we extend the no-go theorems for denying some classes of two-party protocols having access to some particular quantum trusted third-parties, known as quantum two-party oracles. The extension implies that a quantum protocol for implementing secure two-party computations musts have access to a trusted third-party which erases information and thus makes dissipation of heat to the environment.
Based on quantum uncertainty and quantum entanglement, an quantum allor-nothing oblivious transfer protocol is proposed. It is illustrated in detail that the protocol is unconditionally secure. The distinct merit of the present protocol lies in that it is not based on quantum bit commitment. The full utilization of the entanglement makes the protocol different from previous insecure ones, thus its security is not restricted by the no-go theorem of twoparty secure computations. Typeset using REVTEX 1 The research on the oblivious transfer (OT) problem may be traced back to more than twenty years ago [1,2]. Kilian [3] pointed out later that OT is very important in two-party and multi-party protocols. This is because in most symmetrical protocols, the participants always know each others ’ data. If some participants are dishonest or try to get extra information, the protocols become insecure. OT can create some secret between the participants and break this symmetry. Thus it can be used to implement multi-party protocols such as
A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process, or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multiparty computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signaling constraints into account. The best that can be hoped for, in general, are quantum protocols which are computationally secure against quantum attack. Here a method is described for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin-tossing protocol. No security proof is attempted, but reasons are sketched why these protocols might resist quantum computational attack.