One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties
<|reference_start|>One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties: 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.<|reference_end|>
@article{beygelzimer1999one-way,
    title={One-Way Functions in Worst-Case Cryptography: Algebraic and Security
  Properties},
    author={A. Beygelzimer, L. A. Hemaspaandra, C. M. Homan and J. Rothe},
    journal={arXiv preprint arXiv:cs/9911007},
    year={1999},
    number={University of Rochester Technical Report UR-CS TR 722},
    archivePrefix={arXiv},
    eprint={cs/9911007},
    primaryClass={cs.CC cs.CR}
}