Associative one-way functions: a new paradigm for secret-key agreement and digital signatures
Muhammad Rabi, Alan T. Sherman · 1993
We propose associative one-way functions as a new cryptographic paradigm for exchanging secret keys and for signing digital documents. First, we precisely define these functions and establish some of their basic properties. Next, generalizing a theorem of Selman, we constructively prove that they exist if and only if P 6= NP . In addition, we exhibit an implementation based on integer multiplication. We present a novel protocol that enables two parties to agree on a secret key, and we discuss the security of this protocol. Finally, we generalize our protocol to enable two or more parties to agree on a secret key, and we present a similar protocol for signing documents. Given any honest binary function ffi : S \\Theta S ! S on the message space S = f0; 1g , we say that ffi is associative one-way if: 1) for all x; y; z 2 S, x ffi (y ffi z) = (x ffi y) ffi z; and 2) ffi is polynomial-time computable, but inverting ffi is not. We say that ffi is strong if inverting x ffi y remains har...