One-way functions in worst-case cryptography
Alina Beygelzimer, Lane A. Hemaspaandra, Christopher Michael Homan, Jörg Rothe · ACM SIGACT News · 1999
Introduction to Complexity Theory Column 26This issue's column overviews papers asking what additional algebraic and security properties one-way functions may have and whether requiring such properties is costly or a freebie.For example, it has recently been shown that if one-way functions exist then strong, total, commutative, associative one-way functions exist.Looking towards the future, in the next issues will be guest columns by Madhu Sudan on list-decoding algorithms and applications, and by Ulrich Hertrampf on algebraic acceptance mechanisms for polynomial-time machines.