3
$\begingroup$

(As for the question in the title: the answer must be no, but then I don't understand what is intended.)

The Wikipedia page on one way functions states:

Goldreich gives one construction of a universal one-way function, which is denoted by $f_{univ}$ here.

$f_{univ} (desc(M), x) := (desc(M), M(x))$, where $desc(M)$ is the description of Turing machine $M$, and $x$ is an input string. $M(x)$ is defined as the output of machine $M$ given $x$ as input if the running time is at most quadratic on the length of $x$, and otherwise, $M(x) := x$. This definition of $M(x)$ guarantees $f_{univ}$ can be efficiently computed within polynomial time.

The point of $f_{univ}$ is that whenever there exists one way functions that run in quadratic time, then $f_{univ}$ is a one-way function as well. (And the Goldreich reference proves that whenever one-way functions of any running time exist, they can be used to create one way functions that run in quadratic time, hence obtaining the result that the 'concrete' function $f_{univ}$ is a one way function if and only if one way functions exist at all.)

I am, however, not convinced that the last statement from the quote is obvious.

As I understand it, a computer wanting to compute $M(x)$ needs to do two things:

1) Decide whether or not the running time of machine $M$ given $x$ as input is "at most quadratic on the length of $x$"

2) Either return $x$ or let $M$ run on input $x$ and return the output

Now it is clear that step 2) takes at most quadratic time in the length of $x$ and hence certainly in the length of the total input of $f_{univ}$. What is not clear is that step 1) can be carried out in polynomial time.

To be clear: I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$. I can also think up an algorithm that test in polynomial time (even time $1000|x|^2$) whether or not $M$ runs for at most $1000|x|^2$ steps. Etc etc etc. However the term 'quadratic' gives us no information on how big or small the implied constant is.

It seems that whenever I make the definition of $f_{univ}$ concrete as in the example above (so output the output of $M$ on $x$ whenever it can be computed in less than $1000 |x|^2$ steps and otherwise output $x$), there might be a world imaginable where quadratic time one way functions exist but all of them take time longer than 1000 times their input length squared and $f_{univ}$ is not one way at all. The only way I can think of to avoid this is for the computer to somehow decide if $M$ halts on $x$ at all but that is known to be a hard problem.

What am I missing?

UPDATE: I see another way out of this: when the proof that any one-way function $f$ can be transformed into a one way function $g$ that runs in quadratic time does in fact give that $g$ runs in time $< cn^2$ for a very concrete $c$. However here it is crucially important that $c$ does not depend on the unkonwn function $f$. This is not clear from me from the Goldreich notes Wikipedia links to. (The proof is in section 2.4.2.) Any help clarifying this is appreciated!

$\endgroup$
4
$\begingroup$

You don't need to know whether it is quadratic on all $x$, only on the particular $x$ that is given as input. And it's easy to decide whether a machine runs in a given time bound on a fixed input $x$. Just simulate it for that many steps and check whether it stops before the time bound runs out.

Here, "at most quadratic" is a little sloppy. It should be read as meaning "at most $|x|^2$ steps", so that there is a concrete time bound to check against. But one should keep in mind that there is a tradeoff between writing that is perfectly rigorous, and writing that can easily be understood by non-specialists, and Wikipedia generally aims for the latter — see https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable and its specific guidance to "explain formulae in English".

$\endgroup$
  • $\begingroup$ Yes the first paragraph is what I had in mind when I wrote: 'I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$.' Your second paragraph makes a LOT of sense - in fact it is not so long ago that I myself would have interpreted at most quadratic as "at most $|x|^2$ step without worrying about any constants. Thanks for clarifying this! $\endgroup$ – Vincent Jan 23 '16 at 13:46
  • $\begingroup$ It seems then however that we are in the situation I described under 'UPDATE' (for $c = 1$) and that Goldreich also uses 'quadratic' in the unusual and stricter sense of 'at most $|x|^2$ steps'. I should stare a bit longer at his argument to verify that it does indeed work with this stronger notion of quadratic. $\endgroup$ – Vincent Jan 23 '16 at 13:47

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.