  We survey recent developments in the study of (worst-case) one-way functions
having strong algebraic and security properties. According to [RS93], this line
of research was initiated in 1984 by Rivest and Sherman who designed two-party
secret-key agreement protocols that use strongly noninvertible, total,
associative one-way functions as their key building blocks. If commutativity is
added as an ingredient, these protocols can be used by more than two parties,
as noted by Rabi and Sherman [RS93] who also developed digital signature
protocols that are based on such enhanced one-way functions.
  Until recently, it was an open question whether one-way functions having the
algebraic and security properties that these protocols require could be created
from any given one-way function. Recently, Hemaspaandra and Rothe [HR99]
resolved this open issue in the affirmative, by showing that one-way functions
exist if and only if strong, total, commutative, associative one-way functions
exist.
  We discuss this result, and the work of Rabi, Rivest, and Sherman, and recent
work of Homan [Hom99] that makes progress on related issues.
