7
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.