One-Way Function

Consider straight-line algorithms over a Finite Field with $q$ elements. Then the $\epsilon$-straight line complexity $C_\epsilon(\phi)$ of a function $\phi$ is defined as the length of the shortest straight-line algorithm which computes a function $f$ such that $f(x)=x$ is satisfied for at least $(1-\epsilon)q$ elements of $F$. A function $\phi$ is straight-line ``one way'' of range $0\leq\delta\leq 1$ if $\phi$ satisfies the properties:

1. There exists an infinite set $S$ of finite fields such that $\phi$ is defined in every $F\in S$ and $\epsilon$ is One-to-One in every $F\in S$.

2. For every $\epsilon$ such that $0\leq\epsilon\leq\delta$, $C_\epsilon(\phi^{-1})$ tends to infinity as the cardinality $q$ of $F$ approaches infinity.

3. For every $\epsilon$ such that $0\leq\epsilon\leq\delta$, the ``work function'' $\eta$ satisfies

$$\eta\equiv \liminf_{q\to\infty} \eta \equiv \liminf_{q\to\i... ...on(\phi^{-1})-\ln C \epsilon(\phi)\over\ln C\epsilon(\phi)}>1.$$

It is not known if there is a one-way function with work factor $\eta>(\ln q)^3$.

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.