One-way functions are essential for complexity based cryptography

Abstract

It is shown that many of the standard cryptographic tasks are equivalent to the usual definition of a one-way function. In particular, it is shown that for some of the standard cryptographic tasks any secure protocol for the task can be converted into a one-way function in the usual sense, and thus the security of any proposed protocol for these tasks is implicitly based on a function being 'one-way.' Thus, the usual definition of a one-way function is robust; any one-way function with respect to another definition on which a secure cryptographic protocol can be based can be used to construct a one-way function in the usual sense. The authors focus on private-key encryption, identification/authentication, bit commitment, and coin flipping by telephone. However, the proof techniques presented here can be easily adopted to prove analogous results for other cryptographic tasks.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>