Creating Strong Total Commutative Associative One-Way Functions from Any One-Way Function
Lane A. Hemaspaandra, J org Rothe · 1998
Rabi and Sherman (1997) presented novel digital signature and unauthenticated secret-key agreement protocols, developed by themselves and by Rivest and Sherman. These protocols use "strong," total, commutative (in the case of multi-party secret-key agreement), associative one-way functions as their key building blocks. Though Rabi and Sherman did prove that associative one-way functions exist if P eq NP, they left as an open question whether any natural complexity-theoretic assumption is sufficient to ensure the existence of "strong," total, commutative, associative one-way functions. In this paper, we prove that if P eq NP then "strong," total, commutative, associative one-way functions exist.