Rivest, Rabi, and Sherman proposed protocols for secret-key agreement and digital signatures. The secret-key agreement protocol given in Figure 7.11 is due to Rivest and Sherman. Rabi and Sherman modified this protocol to a digital signature protocol, see Exercise 7.4-1.
The Rivest-Sherman protocol is based on a total, strongly noninvertible, associative one-way functioní. Informally put, a one-way function is a function that is easy to compute but hard to invert. One-way functions are central cryptographic primitives and many cryptographic protocols use them as their key building blocks. To capture the notion of noninvertibility, a variety of models and, depending on the model used, various candidates for one-way functions have been proposed. In most cryptographic applications, noninvertibility is defined in the average-case complexity model. Unfortunately, it is not known whether such one-way functions exist; the security of the corresponding protocols is merely based on the assumption of their existence. Even in the less challenging worst-case model, in which so-called “complexity-theoretic” one-way functions are usually defined, the question of whether any type of one-way function exists remains an open issue after many years of research.
A total (i.e., everywhere defined) function mapping from to is associative if and only if holds for all , where we use the infix notation instead of the prefix notation . This property implies that the above protocol works:
so Alice and Bob indeed compute the same secret key.
The notion of strong noninvertibility is not to be defined formally here. Informally put, is said to be strongly noninvertible if is not only a one-way function, but even if in addition to the function value one of the corresponding arguments is given, it is not possible to compute the other argument efficiently. This property implies that the attacker Erich, knowing and and , is not able to compute the secret numbers and , from which he could easily determine the secret key .
7.4-1 Modify the Rivest-Sherman protocol for secret-key agreement from Figure 7.11 to a protocol for digital signatures.
7.4-2 a. Try to give a formal definition of the notion of “strong noninvertibility” that is defined only informally above. Use the worst-case complexity model.
b. Suppose is a partial function from to , i.e., may be undefined for some pairs in . Give a formal definition of “associativity” for partial functions. What is wrong with the following (flawed) attempt of a definition: “A partial function is said to be associative if and only if holds for all for which each of the four pairs , , , and is in the domain of .”