Course:Fall 2011 Exercises 2
From CRYPTUTOR
- [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}).
- Suppose is preimage collision resistant. Modify to (possibly with a different domain), so that the latter remains preimage collision resistant, but is not second-preimage collision resistant. (Prove these properties of .)
- Given a CRHF which compresses by two bits (say from n bits to n − 2 bits), construct a CRHF that compresses by one bit (say from n + 1 bits to n bits), such that the function f(h',x) = (h',h'(x)) (where ) is not a OWF. (In both and , collision-resistance holds when the hash function is drawn uniformly at random from the family.)
- [Extra] (Sufficiently Shrinking) CRHF implies OWF. Below we say that "x has a collision under f" if there exists an such that f(x) = f(x').
- Let be a CRHF and suppose that for every and every x, x has a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
- Now suppose that for each , 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.
- Show that if is a CRHF from n bits to n / 2 bits, then the function f(h,x) = (h,h(x)) is a OWF.
- [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.
- Suppose 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 R_{A}(x,y,r) and R_{B}(x,y,r) respectively to Alice and Bob. Describe a deterministic 2-party SFE functionality (which takes x and y from Alice and Bob respectively, and gives f_{A}(x,y) and f_{B}(x,y) to them respectively; f_{A},f_{B} can depend on R_{A},R_{B}), and a protocol (i.e., a protocol in which Alice and Bob can access a trusted party implementing ), such that securely realizes . In your protocol , Alice and Bob should access exactly once. Security must hold against both passive and active adversaries.
- Suppose is an arbitrary 2-party SFE functionality which takes x and y from Alice and Bob respectively, and gives f_{A}(x,y) and f_{B}(x,y) to them respectively. Describe another 2-party SFE functionality which provides output only to Bob (i.e., Alice gets a dummy output ), and a protocol (i.e., a protocol in which Alice and Bob can access a trusted party implementing ), such that securely realizes . In your protocol , Alice and Bob should access exactly once. Security needs to hold only against passive adversaries.
- [25 pts] OT from Correlated Random Variables. Define Oblivious Transfer (OT) functionality over a field (or, over a ring) as an SFE in which Alice inputs and Bob inputs ; then Alice gets as output, but Bob gets x_{b}.
- Consider an inputless, randomized functionality RandOT, which outputs a random pair to Alice and (c,z_{c}) to Bob, where is a random bit. Give a protocol π^{RandOT} that securely realizes OT, by accessing RandOT exactly once at the beginning of the protocol.
- Consider another inputless, randomized SFE functionality RandShare, which outputs to Alice and to Bob, where (s_{A},s_{B},p_{A},p_{B}) are uniformly random conditioned on the relation s_{A} + s_{B} = p_{A}p_{B}. Give a protocol ρ^{RandShare} that securely realizes OT, by accessing RandShare exactly once at the beginning of the protocol.
- [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 . 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 x_{i} and y_{i} for .
- Addition. Show how the parties can obtain shares z_{i} for z = x + y (shared using the same secret-sharing scheme), without learning anything more.
- Multiplication (changing the threshold). Show how the parties can obtain shares W_{i} 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)?]
- Degree reduction. Suppose the parties are given shares r_{i} and R_{i} of a value r using the (n,t + 1) and (n,2t + 1) secret-sharing schemes above. Show how they can convert their shares W_{i} of a value w under the latter scheme to shares w_{i} 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.]
- [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 N_{A} and N_{B} (chosen by A and B respectively). The protocol is described at the end.
- 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.]
- Suggest a (small) fix for the attack.
- 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 . If M is sufficiently random, 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 sends the identities to S) * (S sends B's public key to A) * (where N_{A} is a fresh nonce, picked by A) * (B sends the identities to S) * (S sends A's public key to B) * (where N_{B} is a fresh nonce picked by B) * (A and B agree on N_{A},N_{B} at this point)