Course:Fall 2009 Exercises 3

2009-11-23T01:39:58Z

New page

'''Under preparation.'''

# '''Power of 2-party SFE with only one output.''' In this problem we shall see how deterministic secure function evaluation (SFE) functionalities in which only one party receives the outcome can be easily used to realize more general functionalities securely, against passive (honest-but-curious) adversaries.
## Suppose <math>{\mathcal R}</math> is an arbitrary ''randomized'' 2-party functionality which takes <math>x</math> and <math>y</math> from Alice and Bob respectively, and samples a uniform random string <math>r</math> (of a fixed length) and gives <math>R_A(x,y,r)</math> and <math>R_B(x,y,r)</math> respectively to Alice and Bob. Describe a ''deterministic'' 2-party SFE functionality <math>{\mathcal F}</math> (which takes <math>x</math> and <math>y</math> from Alice and Bob respectively, and gives <math>f_A(x,y)</math> and <math>f_B(x,y)</math> to them respectively; <math>f_A, f_B</math> can depend on <math>R_A, R_B</math>), and a protocol <math>\pi^{{\mathcal F}}</math> (i.e., a protocol in which Alice and Bob can access a trusted party implementing <math>{\mathcal F}</math>), such that <math>\pi^{{\mathcal F}}</math> securely realizes <math>{\mathcal R}</math>. In your protocol <math>\pi^{{\mathcal F}}</math>, Alice and Bob should access <math>{\mathcal F}</math> exactly once. Security must hold against both passive and active adversaries.
## Suppose <math>{\mathcal F}</math> is an arbitrary 2-party SFE functionality which takes <math>x</math> and <math>y</math> from Alice and Bob respectively, and gives <math>f_A(x,y)</math> and <math>f_B(x,y)</math> to them respectively. Describe another 2-party SFE functionality <math>{\mathcal G}</math> which provides output only to Bob (i.e., Alice gets a dummy output <math>g_A(x,y)=\bot</math>), and a protocol <math>\rho^{\mathcal G}</math> (i.e., a protocol in which Alice and Bob can access a trusted party implementing <math>{\mathcal G}</math>), such that <math>\rho^{\mathcal G}</math> securely realizes <math>{\mathcal F}</math>. In your protocol <math>\rho^{\mathcal G}</math>, Alice and Bob should access <math>{\mathcal G}</math> exactly once. Security needs to hold only against passive adversaries.
# '''OT from Correlated Random Variables.''' Define Oblivious Transfer (OT) functionality over a field <math>{\mathbb F}</math> (or, over a ring) as an SFE in which Alice inputs <math>(x_0,x_1) \in {\mathbb F}^2</math> and Bob inputs <math>b\in\{0,1\}</math>; then Alice gets <math>\bot</math> as output, but Bob gets <math>x_b</math>.
## Consider an inputless, randomized functionality RandOT, which outputs a random pair <math>(z_0,z_1)\in{\mathbb F}^2</math> to Alice and a random bit <math>c\in\{0,1\}</math> to Bob. Give a protocol <math>\pi^{\mathrm{RandOT}}</math> that securely realizes OT, by accessing RandOT exactly once at the beginning of the protocol.
## Consider another inputless, randomized SFE functionality RandShare, which outputs <math>(s_A,p_A)\in{\mathbb F}^2</math> to Alice and <math>(s_B,p_B)\in{\mathbb F}^2</math> to Bob, where <math>(s_A,s_B,p_A,p_B)</math> are uniformly random conditioned on the relation <math>s_A+s_B = p_A p_B</math>. Give a protocol <math>\rho^{\mathrm{RandShare}}</math> that securely realizes OT, by accessing RandShare exactly once at the beginning of the protocol.

CRYPTUTOR - Recent changes [en]

Course:Fall 2009 Exercises 3