A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs

Generic

2/4/24, 6:29 PM

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?

1 + 0

one-way-function

pseudo-random-generator

hardness-assumptions

Score:1

Crypto

Mark

2/8/24, 3:36 AM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.