Is there a definition of the pseudo-random sequences like PRG or PRF in cryptography?

Question

I have learned the definition of PRGs and PRFs. As I know the meaning of pseudoreandomness. I think that the pseudo-random sequence and the truly random sequence are indistinguishable.

I did not find a definition of the pseudo-random sequences. And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence). Follows are my approaches which may be helpful.

Let a sequence $\alpha = (a_{1}, a_{2}, \ldots, a_{n}, \ldots)$ is a sequence over a finite set $\Sigma$ ($|\Sigma| > 1$), where $a_{i} \in \Sigma$. It is truly random if $a_{i}$ is chosen uniformly in $\Sigma$.

Let $\beta= (b_{1}, b_{2}, \ldots, b_{n}, \ldots)$ be a sequence over $\Sigma$. It is pseudo-random sequence if for every PPT algorithm $A$, there is a negligible function $\varepsilon$ such that

$$\left\vert \Pr \left[ A(b_{1} \Vert b_{2} \Vert \cdots \Vert b_{n}) = 1 \right] - \Pr\left[ A(a_{1} \Vert a_{2} \Vert \cdots \Vert a_{n}) = 1 \right] \right\vert \leq \varepsilon(n)$$

Or can we consider that it is unpredictable? Let $\beta= (b_{1}, b_{2}, \ldots, b_{n}, \ldots)$ be a sequence over $\Sigma$. It is pseudo-random sequence if for every PPT algorithm $A$, there is a negligible function $\varepsilon$ such that

$$\left\vert \Pr \left[ A(b_{1} \Vert b_{2} \Vert \cdots \Vert b_{n}) = b_{n+1} \right] - \frac{1}{|\Sigma|} \right\vert \leq \varepsilon(n)$$

Answer 1

I think that the pseudo-random sequence and the truly random sequence are indistinguishable.

And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence).

Congratulations, you have a very good intuition! You're almost there.

A key to understanding the definition of a pseudorandom sequence is that there is no such thing as a pseudorandom sequence. If you have a specific sequence, then there's no randomness involved! Instead, the useful concept is that of a pseudorandom sequence family, more usually called pseudorandom function family (but abbreviated PRF). In a nutshell, a pseudorandom sequence family is a family of sequences such that given some data that may or may not be part of a sequence in that family, and bounded computational power, there is no way to know whether the data is from a sequence in the family or was generated uniformly at random. In other words, a pseudorandom sequence is indistinguishable from a random sequence.

Note that “uniformly at random” here is a mathematical definition: a uniformly random bit sequence is one where the value of each bit is independent (in the sense of probability theory) from the value of other bits as well as from all other events in the world. This definition does not consider whether it is possible to perform this generation in the physical world.

The definition of pseudorandomness only considers the output of the process, not how this output is produced. Otherwise it would be a circular definition: a pseudorandom generator is one that produces pseudorandom output — “pseudorandom output” has to have some definition other than where the output come from. The definition is about what you can deduce from observing the output. A pseudorandom generator is an algorithm that transforms a seed into the element of a pseudorandom sequence family that is indexed by the seed value.

To put this indistinguishability in more mathematical terms, consider an observable property $A$ of the output. For example, “bit $3$ is 1 and bits $4$, $5$ and $6$ are not all equal”. This observable property has a certain probability $\Pr_U(A)$ of being true for the uniform random distribution ($\frac{1}{2} \cdot \frac{6}{8}$ for the example above). If you pick a random element of the pseudorandom sequence family $F$, the probability of this observable property $\Pr_F(A)$ must be close enough to the probability for the uniform random distribution: $\Pr_F(A) \approx Pr_U(A)$.

To make this definition fully precise, we still need to say what observable properties are permitted and what “close enough” means. We aren't interested in adversaries with infinite computational power, which is why we restrict $A$ to polynomial computations. And “close enough” is defined as bounded by a negligible function. That's how the equation in your question comes about. The piece that you were missing is that you don't first select specific sequences $\alpha$ and $\beta$. Rather, $\alpha$ and $\beta$ are a probability distribution over sequences: $\alpha$ is a choice of element of the function famility, and $\beta$ is a uniform choice over all possible functions.

Answer 2

I do not know of a formal definition for pseudo random sequences. What we tend to do is just prove that a pseudo random data is computationally indistinguishable from a truly random data. If we designed a predictor that would predict the next bit of a data sequence, the predictor would be unable to distinguish between data generated by the pseudorandom function and a truly random function. PRPs and PRFs have other guarantees and conditions, but I am going to ignore this for now. Formally, "computational indistinguishability" is described as

$$|Pr_{x \leftarrow P1} \left[D(x)=1\right]-Pr_{x \leftarrow P2} \left[D(x)=1\right] | < negligible.$$

If our pseudorandom function is $P1$, and our random function is $P2$ over the set $U=\{0,1\}^n$, we have computational indistinguishability when the probability of the next bit of $P1$ and $P2$ are close enough for some test $D$ to have a negligible difference.

More formally, you are trying to prove that there exists a negligible function $\varepsilon $ for every $n \in N$, that proves that PPT decider $D$ cannot tell apart a sample from ensembles of $P1$ and $P2$ in $N$. If I were to actually do a formal proof, I'd write is as:

$$|Pr\left[x \leftarrow P1:D(x)=1\right]-Pr\left[x \leftarrow P2: D(x)=1\right] | \le \varepsilon(n),$$ which seems to be closer to the format that you are using. A psuedo random sequence will have to satisfy the comparison against a random sequence to be valid.

Answer 3

I think the pseudo-randomness of a sequence is determined only by the way it was generated - using a PRG or not. It is not a property of the numbers in the sequence, so I don't think we can express it mathematically.

Answer 4

Thanks for all the answers. I realize that I had a big mistake. I did not figure out the distribution of the pseudo-random sequences.

I try to use PRGs or PRFs to define the pseudo-random sequences. If there is a formal one, please tell me.

Of course, the pseudo-random sequence and the truly random sequence are indistinguishable. And the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence). I also consider that what the "sequence" is. Is it a kind of "numbers" or "functions"?

As a book "Lecture Notes on Cryptography" written by Shafi Goldwasser and Mihir Bellare says,

The one-time pad is generally impractical because of the large amount of key that must be stored. In practice, one prefers to store only a short random key, from which a long pad can be produced with a suitable cryptographic operator. Such an operator, which can take a short random sequence $x$ and deterministically “expand” it into a pseudo-random sequence $y$, is called a pseudo-random sequence generator. Usually $x$ is called the seed for the generator. The sequence $y$ is called “pseudo-random” rather than random since not all sequences $y$ are possible outputs; the number of possible $y$’s is at most the number of possible seeds. Nonetheless, the intent is that for all practical purposes $y$ should be indistinguishable from a truly random sequence of the same length.

It is important to note that the use of pseudo-random sequence generator reduces but does not eliminate the need for a natural source of random bits; the pseudo-random sequence generator is a “randomness expander”, but it must be given a truly random seed to begin with.

To achieve a satisfactory level of cryptographic security when used in a one-time pad scheme, the output of the pseudo-random sequence generator must have the property that an adversary who has seen a portion of the generator’s output $y$ must remain unable to efficiently predict other unseen bits of $y$. For example, note that an adversary who knows the ciphertext $C$ can guess a portion of $y$ by correctly guessing the corresponding portion of the message $M$, such as a standardized closing “Sincerely yours,”. We would not like him thereby to be able to efficiently read other portions of $M$, which he could do if he could efficiently predict other bits of $y$. Most importantly, the adversary should not be able to efficiently infer the seed $x$ from the knowledge of some bits of $y$.

It seems that the notion of pseudo-random sequences is an approach to find a way to generate the pseudo-random number. Although I think the pseudo-random sequences have more functions perhaps. Thus, I think it is correct to use the definition of PRGs to define the pseudo-random sequences.

Let $G \colon \{\, 0,1 \,\}^{*} \rightarrow \{\, 0,1 \,\}^{\infty}$ be a generator of sequences if for all the polynomial $p(\cdot)$, $G_{p}$ is polynomial-time, where $G_{p}(s)$ is the first $p(|s|)$ bits of $G(s)$. We say $G$ is a pseudo-random-sequence generator if there exists a negligible function $\varepsilon(\cdot)$ such that for every polynomial $p(\cdot)$ and every PPT distinguisher $D$,

$$\left\vert \Pr\left[ x \leftarrow \{\, 0,1 \,\}^{p(n)}: D(x) = 1\right] - \Pr \left[ s \leftarrow \{\, 0,1 \,\}^{n}: D(G_{p}(s)) = 1 \right] \right\vert \leq \varepsilon(n)$$

there are some kinds of classical pseudo-random generators: linear feedback shift registers and the binary expansion of any algebraic number (such as $\sqrt{5}= 10.001111000110111 \ldots $). Although they are both insecure. It shows that the sequence does not need a finite period.

I still do not know how to define it by using the definition of PRFs. Because I cannot find a function like $f_{s} \colon \{\, 0,1 \,\}^{\lambda(|s|)} \rightarrow \{\, 0,1 \,\}^{\lambda(|s|)}$ where $s$ is the key.

Answer 5

The relevant Wikipedia entry states:-

In the asymptotic setting, a family of deterministic polynomial time computable functions $G_{k}: \{0,1\}^{k} \rightarrow \{0,1\}^{p(k)}$ for some polynomial $p$, is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input ( $p(k)>k$ for any $k$), and if its output is computationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithm $A$, which outputs $1$ or $0$ as a distinguisher,

$$\left|\Pr _{x\gets \{0,1\}^{k}}[A(G(x))=1]-\Pr _{r\gets \{0,1\}^{p(k)}}[A(r)=1]\right|<\mu (k)$$

for some negligible function $\mu$. (The notation $x \leftarrow X$ means that $x$ is chosen uniformly at random from the set $X$.)

There is an equivalent characterization: For any function family $ G_{k}:\{0,1\}^{k}\to \{0,1\}^{p(k)}$, $G$ is a PRNG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.

You also mention unpredictablility (as does the above definition), and indistinguishability. However I believe that is only true within a strictly limited context, whilst looking at nothing more than the output. Holistically, a pseudo random sequence is neither, as your $ \beta$:-

• Is entirely predictable and distinguishable by $ \in (Alice, Bob, Eve)$.

• It is distinguished by the fact that the cycle $|\beta| < \infty$.

• Only remains secret and random for $Eve$ whilst $N \neq NP$.

The conclusion seems to be that there are multiple definitions and distinctions.