### Fall 2001, CSE 597E: Quiz 1 and solution - 19 Sept 2001

Please write your Name, Student ID, and Section at the top of the page.
1. [1 point] What is a one-way function? (only one answer, please)
1. A function which has no inverse
2. A function which looses information during the transformation
3. A function with low complexity, but whose inverse is intractable
4. A function which is computable, but whose inverse is not computable
5. A function which is surgective but not injective.

1. A trap for the attacker based on passing false information about the secret key
2. An information which allows to find out whether there has been an attempt of attack
3. A trap for the legal party based on corrupting the public key of the other party
4. An information which makes it easy to compute the inverse of a one-way function
5. A parameter which transforms an ordinary function into a one-way function

3. [5 points] For each of the following sentences about symmetric and asymmetric cryptography, say whether it is true or false.
1. In the asymmetric case each agent has a public key and a private key.   True
2. In the asymmetric case there is a trusted party who has one public key; all the ordinary agents have secret keys.   False
3. In the symmetric case the keys satisfy the symmetric property: {{M}k1}k2 = {{M}k2}k1.   False
4. In the asymmetric case the secret key SK and the public key PK satisfy the following inversion property: {{M}PK}SK = M.   True
5. In the symmetric case the protocols are symmetric, in the sense that for each action of an agent (during the protocol) there is a complementary reaction of his party.   False

1. A formalism to specify sequential programs (Calculus of Sequential Programs)
2. A formalism to specify systems of communicating processes (Communicating Sequential Processes)
3. A security protocol (Casper Security Protocol)
4. A formal tool to prove the correctness of cryptographic algorithms (Cryptography Soundness Prover)

5. [2 points] Describe briefly the meaning (behaviour) of the following specification of an intruder.
```   Intruder(X) = learn? m: messages -> Intruder(close(X U {m}))
[]
say! m: X /\ messages -> Intruder(X)
```
The symbols U and /\ here represent set union and set intersection.

Answer: At each step the intruder has two possibilities:

• read a message m and add it to its current knowledge (X), then infer all possible information from X U {m}. The closure under inference is represented by close(X U {m}) and it constitute the new knowledge of the intruder.
• send a message m which is a legal message and belong to its current knowledge

6. [Bonus question, points 5] Suppose that Angela and Bill live in two different islands and can communicate only by exchanging packages. Each of them also has various chains and locks and a key for each lock. A lock can be opened only by its own key, and there is only one copy of the key.

The mailman can deliver packages from Angela to Bob and viceversa, but is dishonest and can open and steal or replace the content of any package which is not chained and locked.

1. How can Angela send something to Bill, assuming that the mailman do not owns any chain/lock/key?

2. How can the mailman steal the content of the package sent by Angela, if he owns a chain with lock and key?