Mehmet Sabir Kiraz (#704)
Mehmet Sabir Kiraz
Topic of his/her doctorate.
Secure and Fair Two-Party Computation
Secure Two-Party Computation, Garbled Circuits, Cryptographic protocols
Year of completion
Consider several parties that do not trust each other, yet they wish to correctly compute
some common function of their local inputs while keeping these inputs private. This
problem is known as “Secure Multi-Party Computation”, and was introduced by Andrew
Yao in 1982. Secure multi-party computations have some real world examples like electronic
auctions, electronic voting or Fingerprinting. In this thesis we consider the case where there
are only two parties involved. This is known as “Secure Two-Party Computation”.
If there is a trusted third party called Carol, then the problem is pretty straightforward.
The participating parties could hand their inputs in Carol who can compute the common
function correctly and could return the outputs to the corresponding parties. The goal is
to achieve (almost) the same result when there is no trusted third party.
Cryptographic protocols are designed in order to solve these kinds of problems. These
protocols are analyzed within an appropriate model in which the behavior of parties is
structured. The basic level is called the Semi-Honest Model where parties are assumed to
follow the protocol specification, but later can derive additional information based on the
messages which have been received so far. A more realistic model is the so-called Malicious
Model. The common approach is to First analyze a protocol in the semi-honest model and
then later extend it into the malicious model.
Any cryptographic protocol for secure two-party computation must satisfy the following
security requirements: correctness, privacy and fairness. It must guarantee the correctness
of the result while preserving the privacy of the parties’ inputs, even if one of the parties is
malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness.
This roughly means that whenever a party aborts the protocol prematurely, he or she should
not have any advantage over the other party in discovering the output.
The main question for researchers is to construct new protocols that achieve the above
mentioned goals for secure multi-party computation. Of course, such protocols must be
secure in a given model, as well as be as effcient as possible. In 1986, Yao presented
the First general protocol for secure two-party computation which was applicable only to
the semi-honest model. He uses a tool called “Garbled Circuit”. Yao’s protocol uses the
underlying primitives (“Pseudorandom Generator” and “Oblivious Transfer”) as blackboxes which lead to e?cient results. After Yao’s work many variants and improvements
have been proposed for the malicious model. In this thesis, we design several new protocols
for secure two-party computation based on Yao’s garbled circuit. Before we present the
details of our new designs, we first show several weaknesses, security flaws or problems with
the existing protocols in the literature. We first work in the semi-honest model and then
extend it into the malicious model by presenting new protocols. Finally we add fairness to
Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is
useful for implementing protocols for secure multi-party computation. We study several
variants of oblivious transfer in this thesis. We present a new protocol for the so-called “Committed OT”. This protocol is very effcient in the sense that it is quite good in
comparison to the most effcient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer
protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is
of independent interest.
We also deal with fairness in this thesis. For protocols based on garbled circuit, so far
only Benny Pinkas has presented a protocol in the literature for achieving fairness. We
show a subtle problem with this protocol where the privacy of the inputs of one party can
be compromised. We also describe this problem in detail which is in fact related to the
fairness, and finally propose a more effcient scheme that does achieve fairness.
m.kiraz (at) uekae.tubitak.gov.tr