2
$\begingroup$

Suppose we have a random access machine with $(n+1)2^n$ random bits on its tape. This assumption is weaker than assuming the existence of a random oracle, but using this assumption we can construct a PRG and hence a OWF: take a random seed $s \in \{0, 1\}^n$, and output $n+1$ bits, where the $i$th bit outputted ($i=1,...,n+1$) is the $(i-1)2^n + 2^s$th position on the tape. This is trivially a PRG.

Notably, it would be conceivable that in the distant future there could exist some kind of device that behaves like a random access machine with a very large number of random bits on its tape, and if such a device existed, then even if $P=NP$ we would still have OWFs.

I have not read about this model or assumption anywhere; does anyone have any resources they could direct me to that discuss this?

$\endgroup$

1 Answer 1

1
$\begingroup$

This is trivially a PRG.

This isn't true. A PRG needs more than to be hard to predict, it needs to have a compact description. In particular, PRGs need to be efficient to evaluate. While this is true locally on your RAM machine, it isn't true in a way that is useful for cryptography.

For your hypothetical

Notably, it would be conceivable that in the distant future there could exist some kind of device that behaves like a random access machine with a very large number of random bits on its tape, and if such a device existed, then even if $P=NP$ we would still have OWFs.

note that if you have two such machines, there is no reason their randomness be correlated at all, so you can't use it as the basis of construction of secret-key encryption. You could have that machine encrypt something, then decrypt it later, but its not clear how useful this is.

Of course, if their randomness were correlated, you could do some things. There are various models similar to this, for example

  • the assumption of noisy (quantum) channels, in things like quantum key distribution
  • the assumption of the "wiretap channel" in coding theory.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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