# 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 $$|g(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.