Since oblivious transfer, a primitive of paramount importance in secure two- and multiparty computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionality are of great interest. In this context, various monotones-quantities that cannot be increased by any protocol-are introduced and then used to derive lower bounds on the possibility and efficiency of such reductions.
Since oblivious transfer, a primitive of paramount importance in secure two- and multiparty computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionality are of great interest. In this context, various monotones-quantities that cannot be increased by any protocol-are introduced and then used to derive lower bounds on the possibility and efficiency of such reductions.
Oblivious transfer is a primitive of paramount importance in cryptography or, more precisely, two- and multi-party computation due to its universality. Unfortunately, oblivious transfer cannot be achieved in an unconditionally secure way for both parties from scratch. Therefore, it is a natural question what information-theoretic primitives or computational assumptions oblivious transfer can be based on. The results in our thesis are threefold. First, we present a protocol that implements oblivious transfer from a weakened oblivious transfer called universal oblivious transfer, where one of the two players may get additional information. Our reduction is about twice as efficient as previous results. Weak oblivious transfer is an even weaker form of oblivious transfer, where both players may obtain additional information about the other player's input, and where the output can contain errors. We give a new, weaker definition of weak oblivious transfer, as well as new reductions with a more detailed analysis. Finally, we carry over our results to the computational setting and show how a weak oblivious transfer that is sometimes incorrect and only mildly secure against computationally bounded adversaries can be strengthened.
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.
Central cryptographic functionalities such as encryption, authentication, or secure two-party computation cannot be realized in an information-theoretically secure way from scratch. This serves as a motivation to study what (possibly weak) primitives they can be based on. We consider as such starting points general two-party input-output systems that do not allow for message transmission and show that they can be used for realizing unconditionally secure bit commitment as soon as they are nontrivial, i.e., cannot be securely realized from distributed randomness only.
Oblivious transfer is an important primitive in modern cryptography.Applications include secure multiparty computation, oblivious sampling, e-voting, and signatures.Information-theoretically secure perfect 1-out-of 2 oblivious transfer is impossible to achieve.Imperfect variants, where both participants' ability to cheat is still limited, are possible using quantum means while remaining classically impossible.Precisely what security parameters are attainable remains unknown.We introduce a theoretical framework for studying semirandom quantum oblivious transfer, which is shown to be equivalent to regular oblivious transfer in terms of cheating probabilities.We then use it to derive bounds on cheating.We also present a protocol with lower cheating probabilities than previous schemes, together with its optical realization.We show that a lower bound of 2 3 on the minimum achievable cheating probability can be directly derived for semirandom protocols using a different method and definition of cheating than used previously.The lower bound increases from 23 to approximately 0.749 if the states output by the protocol are pure and symmetric.The oblivious transfer scheme we present uses unambiguous state elimination measurements and can be implemented with the same technological requirements as standard quantum cryptography.In particular, it does not require honest participants to prepare or measure entangled states.The cheating probabilities are 3 4 and approximately 0.729 for sender and receiver, respectively, which is lower than in existing protocols.Using a photonic testbed, we have implemented the protocol with honest parties, as well as optimal cheating strategies.Because of the asymmetry of the receiver's and sender's cheating probabilities, the protocol can be combined with a "trivial" protocol to achieve an overall protocol with lower average cheating probabilities of approximately 0.74 for both sender and receiver.This demonstrates that, interestingly, protocols where the final output states are pure and symmetric are not optimal in terms of average cheating probability.
We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation in the standard model with n = 2t+1 parties of which t are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn or not learn the output. Specifically, we show that there is a function H^* such that for any protocol that evaluates y_i = b_i ⋅ f(x₁,...,x_n) with perfect passive security (where b_i is a private boolean input), the total communication must be at least 1/2 ∑_{i = 1}ⁿ H_f^*(x_i) bits of information. The second lower bound applies to the perfect maliciously secure setting with n = 3t+1 parties. We show that for any n and all large enough S, there exists a reactive functionality F_S taking an S-bit string as input (and with short output) such that any protocol implementing F_S with perfect malicious security must communicate Ω(nS) bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any n and all large enough g ∈ ℕ there exists a reactive functionality F_C doing computation specified by a Boolean circuit C with g gates, where any perfectly secure protocol implementing F_C must communicate Ω(n g) bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lg n off for Boolean circuits). Both results also extend to the case where the threshold t is suboptimal. Namely if n = kt+s the bound is weakened by a factor O(s), which corresponds to known optimizations via packed secret-sharing.