Foundations of Cryptography: Course Projects
Deadline: Dec. 30, 2016
Project: Secure Two-Party Computation (40 points)
Problem: Secure two-party computation protocols allow two parties, Alice and Bob, to jointly com- pute a function f(x,y) of their inputs x and y such that at the end of the protocol execution:
(a) both party learn the output f(x,y); and
(b) each party learns no more information about the other party’s input than what can be deduced
from its own input and the output, that is,
– Alice learns no more information about y than what can be deduced from its own input x
and the output f(x,y), and
– Bob learns no more information about x than what can be deduced from its own input y
and the output f(x,y).
In an honest-but-curious model of secure two-party computation, the parties Alice and Bob always follow the instructions of the protocol. In lecture 20, we presented a construction of secure two-party computation in the honest-but-curious model, based on oblivious transfer and garbled circuits.
Let x = x1x2 ···xn,y = y1y2 ···yn ∈ {0,1}n be two n-bit strings (numbers). Let f(x,y) be a
function defined as below:
1, x≥y; f(x,y)= 0, x