La. Hemaspaandra et J. Rothe, Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory, J COMPUT SY, 58(3), 1999, pp. 648-659
Rabi and Sherman presented novel digital signature and unauthenticated secr
et-key agreement protocols, developed by themselves and by Rivest and Sherm
an. These protocols use strong, total, commutative (in the case of multipar
ty secret-key agreement), associative one-way functions as their key buildi
ng blocks. Although Rabi and Sherman did prove that associative one-way fun
ctions exist if P not equal NP, they left as an open question whether any n
atural complexity-theoretic assumption is sufficient to ensure the existenc
e of strong, total, commutative, associative one-way functions. Tn this pap
er, we prove that if P not equal NP then strong, total, commutative, associ
ative one-way functions exist. (C) 1999 Academic Press.