### Fall 2001, CSE 597E: Quiz 6 - 16 Nov 2001

Please write your Name and Student ID at the top of the page.

1. [2 points] What does it mean that an encryption scheme is "semantically secure"? (Only one answer, please)

1. It is impossible to decrypt a message
2. The only information that we can efficiently compute from a cyphertext is the length of the plaintext
3. The only information that we can efficiently compute is the lenght of the cyphertext
4. It is unfeasible to decrypt a cyphertext unless we know the lenght of the plaintext

2. [3 points] Please describe briefly how the public key encryption can be used for authentication

The party P encrypts a message with his private key. Every other party Q who receives the message can decrypt it by using P's public key, and Q can be sure that it was sent by P (authentication). In other words, P's private key is used as a signature by P.

Note: Authentication is one of the possible uses of public key encription. The other standard way to use the public key is based on the idea that the sender encripts the message with the receiver's public key, and the receive's decripts it with his own private key. In this way we achieve secrecy, but not authentication of origin (at least, not unless we do something else)

3. [2 points] What is the general problem of secure multi-party computation? (only one answer, please)

1. To compute a function f(x1,x2,...,xn), where for each i the input xi is provided by the party Pi, in such a way that xi is kept secret to any other Pj.
2. To compute a function f(x1,x2,...,xn) in such a way that each xi is kept secret to all parties
3. To exchange a secret f(x1,x2,...,xn) between all parties P1,P2,...,Pn in such a way that no adversary can intercept it
4. To generate a public key known to all and only the intended parties P1,P2,...,Pn by using a function of the form f(x1,x2,...,xn).

4. [1 point] In which case the problem of secure multi-party computation is trivial? (only one answer, please)

1. If there is a trusted third party which can calculate x1,x2,...,xn
2. If there is a trusted third party which can generate a private key for any pair of parties (Pi,Pj)
3. If the function f(x1,x2,...,x3) is feasible
4. If there is a trusted third party which can get x1,x2,...,xn from P1,P2,...,Pn and then calculate f(x1,x2,...,x3).

5. [2 points] What is a semi-honest party (only one answer, please)

1. A party which cheats only once in a while
2. A party which keeps trace of all its intermediate computations
3. A party which will not cheat unless he knows that someone else is cheating
4. A party which tries to find out information about the other parties, but without malicious intentions