## One-Way Function

Consider straight-line algorithms over a Finite Field with elements. Then the -straight line complexity of a function is defined as the length of the shortest straight-line algorithm which computes a function such that is satisfied for at least elements of . A function is straight-line one way'' of range if satisfies the properties:

1. There exists an infinite set of finite fields such that is defined in every and is One-to-One in every .

2. For every such that , tends to infinity as the cardinality of approaches infinity.

3. For every such that , the work function'' satisfies

It is not known if there is a one-way function with work factor .

References

Ziv, J. In Search of a One-Way Function'' §4.1 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 104-105, 1987.