# Length-preserving one-way functions

Unfortunately my background in computational complexity is still weak, but I am working on it.

As I understand, the question of existence of one-way functions is very important in the field.

Assume there are one way-functions, how it can be shown that there exist one-way functions which are length preserving?

Wlog let $g$ be a strong one way function, we will now construct a length preserving oneway function $f$.

Since $g$ is PPT computable by assumption, there is a polynomial $p$ s.t $|f(x)| \le p(|x|)$ for all $x$ Define

$$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ this function always has $|g'(x)| = p(|x|)$. and is trivially strongly one way.

We now have to force $|x| = |f(x)|$.

This we can do by taking $p(|x|)$ bits as input and taking only $|x|$ of it into account, i.e

$f(x||y) = g'(x)$ for $|y| = p(|x|) - |x| + 1$.

Strong one-wayness of $f$ follows from the strong one-wayness of $g'$.

Had $f$ not been strongly one way, we could query a PPT adversary of $f$ for $z = f(y)$ get $x = x_1 || \ldots || x_n$ back and try for each $m \in [n]$ whether $g'(x_1||\ldots||x_m) = z$ and eventually find a preimage of $z$ under $g'$ in polynomial time with non negligible probability. Conradiction.

See the original proof here.

• Please sketch the proof here. – Raphael Mar 20 '13 at 20:49
• OK. The sketch is there now. – Me. Mar 20 '13 at 21:17
• This proof looks a bit confused. What's $f$? It introduces $f$ without defining it. – D.W. Apr 19 '15 at 6:57