# Course:Fall 2011 Exercises 2

1. [25 pts] Preimage collision resistance and second-preimage collision resistance are incomparable. In this problem we consider hash functions on a finite domain (from {0,1}n(k) to {0,1}k).
1. Suppose $\mathcal{H}$ is preimage collision resistant. Modify $\mathcal{H}$ to $\mathcal{H}'$ (possibly with a different domain), so that the latter remains preimage collision resistant, but is not second-preimage collision resistant. (Prove these properties of $\mathcal{H}'$.)
2. Given a CRHF $\mathcal{H}$ which compresses by two bits (say from n bits to n − 2 bits), construct a CRHF $\mathcal{H}'$ that compresses by one bit (say from n + 1 bits to n bits), such that the function f(h',x) = (h',h'(x)) (where $h'\in\mathcal{H}'$) is not a OWF. (In both $\mathcal{H}$ and $\mathcal{H}'$, collision-resistance holds when the hash function is drawn uniformly at random from the family.)
3. [Extra] (Sufficiently Shrinking) CRHF implies OWF. Below we say that "x has a collision under f" if there exists an $x' \ne x$ such that f(x) = f(x').
1. Let $\mathcal{H}$ be a CRHF and suppose that for every $h\in\mathcal{H}$ and every x, x has a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
2. Now suppose that for each $h\in\mathcal{H}$, all but a negligible fraction of x's have a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
3. Show that if $\mathcal{H}$ is a CRHF from n bits to n / 2 bits, then the function f(h,x) = (h,h(x)) is a OWF.
2. [25 pts] 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.
1. Suppose ${\mathcal R}$ is an arbitrary randomized 2-party functionality which takes x and y from Alice and Bob respectively, and samples a uniform random string r (of a fixed length) and gives RA(x,y,r) and RB(x,y,r) respectively to Alice and Bob. Describe a deterministic 2-party SFE functionality ${\mathcal F}$ (which takes x and y from Alice and Bob respectively, and gives fA(x,y) and fB(x,y) to them respectively; fA,fB can depend on RA,RB), and a protocol $\pi^{{\mathcal F}}$ (i.e., a protocol in which Alice and Bob can access a trusted party implementing ${\mathcal F}$), such that $\pi^{{\mathcal F}}$ securely realizes ${\mathcal R}$. In your protocol $\pi^{{\mathcal F}}$, Alice and Bob should access ${\mathcal F}$ exactly once. Security must hold against both passive and active adversaries.
2. Suppose ${\mathcal F}$ is an arbitrary 2-party SFE functionality which takes x and y from Alice and Bob respectively, and gives fA(x,y) and fB(x,y) to them respectively. Describe another 2-party SFE functionality ${\mathcal G}$ which provides output only to Bob (i.e., Alice gets a dummy output $g_A(x,y)=\bot$), and a protocol $\rho^{\mathcal G}$ (i.e., a protocol in which Alice and Bob can access a trusted party implementing ${\mathcal G}$), such that $\rho^{\mathcal G}$ securely realizes ${\mathcal F}$. In your protocol $\rho^{\mathcal G}$, Alice and Bob should access ${\mathcal G}$ exactly once. Security needs to hold only against passive adversaries.
3. [25 pts] OT from Correlated Random Variables. Define Oblivious Transfer (OT) functionality over a field ${\mathbb F}$ (or, over a ring) as an SFE in which Alice inputs $(x_0,x_1) \in {\mathbb F}^2$ and Bob inputs $b\in\{0,1\}$; then Alice gets $\bot$ as output, but Bob gets xb.
1. Consider an inputless, randomized functionality RandOT, which outputs a random pair $(z_0,z_1)\in{\mathbb F}^2$ to Alice and (c,zc) to Bob, where $c\in\{0,1\}$ is a random bit. Give a protocol πRandOT that securely realizes OT, by accessing RandOT exactly once at the beginning of the protocol.
2. Consider another inputless, randomized SFE functionality RandShare, which outputs $(s_A,p_A)\in{\mathbb F}^2$ to Alice and $(s_B,p_B)\in{\mathbb F}^2$ to Bob, where (sA,sB,pA,pB) are uniformly random conditioned on the relation sA + sB = pApB. Give a protocol ρRandShare that securely realizes OT, by accessing RandShare exactly once at the beginning of the protocol.
4. [25 pts] In secure multi-party computation protocols designed for honest-majority, a commonly used tool is a secret-sharing scheme like Shamir's secret-sharing. Let $t\le(n-1)/2$. Consider an (n,t + 1) (i.e., t + 1 out of n) Shamir secret-sharing scheme over some field. Recall that the shares of a value are obtained by evaluating a random degree t polynomial at n points in the field, such that at (say) 0, the polynomial evaluates to the value being shared. Suppose n parties hold the shares of two values x and y under such a scheme. Let the shares be xi and yi for $i=1,\ldots,n$.
1. Addition. Show how the parties can obtain shares zi for z = x + y (shared using the same secret-sharing scheme), without learning anything more.
2. Multiplication (changing the threshold). Show how the parties can obtain shares Wi for w = xy, but shared using an (n,2t + 1) Shamir secret-sharing scheme, without learning anything more. [Hint: Given two polynomials f and g, what can you say about the polynomial h defined as h(i) = f(i)g(i)?]
3. Degree reduction. Suppose the parties are given shares ri and Ri of a value r using the (n,t + 1) and (n,2t + 1) secret-sharing schemes above. Show how they can convert their shares Wi of a value w under the latter scheme to shares wi under the former scheme, such that any subset of t players learns nothing more about w (they might already have partial information about w), where r is uniformly randomly chosen. You can assume that all the parties follow the protocol honestly. [Hint: Use r to blind w before reconstructing it, and then re-share it using the lower degree scheme.]
5. [Extra] The Needham-Schroeder Public Key protocol uses a trusted server, S, to help two parties exchange secret keys with each other. A priori, there are no secrecy or authentication guarantees on the communication network, and the parties know only each other's identities and a public key of the server S. The server, S, knows public keys of all the users. The goal of the protocol is that at the end A and B should agree on random nonces NA and NB (chosen by A and B respectively). The protocol is described at the end.
1. There is a (famous) man-in-the-middle attack on this protocol, whereby a party in the system can set up a shared key with B, while she thinks she has shared that key with A. Describe such an attack (without looking it up!). [Hint: The adversary can run a concurrent session with A.]
2. Suggest a (small) fix for the attack.
3. If you were designing this protocol today, using public-key encryption and signatures, how would you do it?

Needham-Schroeder (Public Key) Protocol: The protocol is described in terms of a public key "encryption" algorithm E. It is a deterministic encryption scheme with the property that ${\mathrm E}_{PK}({\mathrm E}_{SK}^{-1}(M)) = M$. If M is sufficiently random, ${\mathrm E}_{SK}^{-1}(M)$ is assumed to behave like a signature on M (though it does not give existential unforgeability). PA,PB are Alice and Bob's public keys and SA,SB are their secret keys, respectively. Likewise, the server's public and secret keys are PS,SS.

* $A \rightarrow S: A,B$ (A sends the identities to S)
* $S \rightarrow A: {\mathrm E}^{-1}_{SS}( K_{PB}, B )$ (S sends B's public key to A)
* $A \rightarrow B: {\mathrm E}_{PB}(N_A, A)$  (where NA is a fresh nonce, picked by A)
* $B \rightarrow S: B,A$ (B sends the identities to S)
* $S \rightarrow B: {\mathrm E}^{-1}_{SS}( K_{PA}, A)$ (S sends A's public key to B)
* $B \rightarrow A: {\mathrm E}_{PA}(N_B, N_A)$ (where NB is a fresh nonce picked by B)
* $A \rightarrow B: {\mathrm E}_{PB}(N_B)$ (A and B agree on NA,NB at this point)