1
$\begingroup$

I would like to clarify something about the definition of computational indistinguishability and pseudorandom number generators. Suppose we wanted to show that linear congruential generators of the form $x_t = ax_{t-1} + b \pmod m$ are not pesudorandom number generators. Then we wish to show that given a sequence of numbers $x_0, x_1, \ldots$, we can distinguish whether these numbers came from the lcg process above, or are coming from a uniform distribution (in polynomial time, with high probability, etc...).

In doing so, do we assume that we are given the parameters $a,b$ and $m$? On the one hand, if we are given these parameters, then isn't this trivial? Just check if the given sequence satisfies the given lcg... On the other hand, even if we don't know $a,b,m$, there still clearly does exist a polynomial time algorithm that happens to have $a,b,m$ hard-coded into it that could be used to distinguish these sequences from truly random ones.

What is the correct interpretation here? Does it even make sense to ask whether LCGs are pseudorandom generators in the sense of computational indistinguishability?

$\endgroup$

3 Answers 3

1
$\begingroup$

Short answer

The distinguisher is only given the output of the generator on a uniformly chosen seed of appropriate length, along with a truly random string of the same length as the output of the generator. So, no, the distinguisher is not given $a$, $b$ and $m$. However, as you note we can still consider an algorithm in which those values are hardcoded, this problem is solved by randomly choosing new parameters on each run of the generator (see also the last paragraph below).


Long answer (my definitions come from the book of Goldreich)

First, computational indistinguishability. Remember that a probability ensemble is a sequence of random variables $X_0,X_1,X_2,\dots$, which we note $\{X_n\}_{n\in \mathbf{N}}$. In general, $X_n$ represents the output of some probabilistic algorithm on some input of length $n$ (typically either equal to $1^n$ or uniformly chosen).

Two probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are computationally indistinguishable (in polynomial time) if for every probabilistic polynomial-time algorithm $D$, every polynomial $p$ and all sufficiently large $n$, we have $$\left|\mathrm{Pr}[D(X_n,1^n) = 1] - \mathrm{Pr}[D(Y_n,1^n) = 1]\right| < \frac{1}{p(n)}.$$

We have not yet given a "meaning" to the random variables $X_n$ and $Y_n$, but jumping ahead we can say that the definition informally means the following. On an integer $n$, the distinguisher is given the output of the "algorithm" $X$ or $Y$ on an input of length $n$ (as well as $n$ itself in unary form), and tries to guess whether the string was the output of $X$ or the output of $Y$. We can say without loss of generality that the algorithm outputs $1$ if it guesses that the string is the output of $X$, and $0$ otherwise. Then clearly an algorithm which can reliably tell apart outputs of $X$ and outputs of $Y$ would violate the definition.

In the following, $U_n$ denotes a random variable with uniform distribution over all strings of length $n$.

A probability ensemble $X = \{X_n\}_{n\in\mathbf{N}}$ is pseudorandom if there is a function $\ell : \mathbf{N}\to\mathbf{N}$ such that $X$ and $\{U_{\ell(n)}\}_{n\in\mathbf{N}}$ are computationally indistinguishable.

Note that here, in the distinguishing experiment for $n$, $D$ is given $(X_n,1^n)$ on one side and $(U_{\ell(n)},1^n)$ on the other. Jumping ahead, $\ell(n)$ will be the length of the output of the pseudorandom generator on a seed of length $n$, and $X_n$ will be the output itself. Then $D$ must distinguish between $X_n$, the output of the generator, and $U_{\ell(n)}$, a uniform string of length equal to that of the output (as opposed to $U_n$, which is a uniform string of length equal to that of the seed).

A pseudorandom generator is a deterministic polynomial-time algorithm $G$ which satisfies the following two conditions.

  1. Expansion of input. There is a function $\ell:\mathbf{N}\to\mathbf{N}$ such that $\ell(n) > n$ for all integers $n$ and $|G(s)| = \ell(|s|)$ for all strings $s$.

  2. Pseudorandomness of output. The probability ensembles $\{G(U_n)\}_{n\in\mathbf{N}}$ and $\{U_{\ell(n)}\}_{n\in\mathbf{N}}$ are computationally indistinguishable.

The input of $G$ is the seed, so on a seed of length $n$ $G$ produces a "pseudorandom string" of length $\ell(n)$. As long as $s$ is uniformly chosen, $G(s)$ is computationally indistinguishable from a uniform string of length $\ell(|s|)$. And the distinguisher is only given $G(U_n)$ (i.e., $G(s)$ for a uniformly chosen $s$ of length $n$) and $1^n$, nothing else.

Note also that in this definition, there is no limit on the size of the input of $G$, but if you use a fixed modulus $m$, you cannot meaningfully handle seeds larger than $m$. Here too the solution is to generate parameters of appropriate length on each run of the generator.

$\endgroup$
10
  • $\begingroup$ Your last paragraph is essentially what's throwing me off. The definition of a pseudorandom generator seems to assume that the generator in question can handle inputs/outputs of arbitrary sizes. Your suggestion to generate parameters of appropriate length on each run of the generator leads me to believe we should imagine G as some sort of class of generators, which a single LCG with fixed parameters is not. Also, you said " the distinguisher is only given $G(U_n)$ (i.e., $G(s)$ for a uniformly chosen $s$ of length $n$) and $1^n$, nothing else", but this is for all $n$, right? $\endgroup$
    – grawtin
    Jul 13, 2015 at 17:04
  • $\begingroup$ The definition of a pseudorandom generator seems to assume that the generator in question can handle inputs/outputs of arbitrary sizes. Your suggestion to generate parameters of appropriate length on each run of the generator leads me to believe we should imagine G as some sort of class of generators, which a single LCG with fixed parameters is not. That's basically it, yes. $\endgroup$
    – fkraiem
    Jul 13, 2015 at 17:09
  • $\begingroup$ "but this is for all n, right" Yes, but only one at a time. ;) And for all sufficiently large $n$, the inequality in the definition holds. $\endgroup$
    – fkraiem
    Jul 13, 2015 at 17:10
  • 1
    $\begingroup$ The requirement that $G$ be able to handle seeds of arbitrary (or at least arbitrarily large) size is required if you want to analyse it asymptotically (the inequality in the definition must hold for arbitrarily large seeds). Using a single set of parameters, you can't do an asymptotic analysis, but you can still give concrete security bounds, like "the fastest computer known today would need to run for X hours in order to break this pseudorandom generator with probability Y". (If you have the book of Katz-Lindell, they speak breifly of these concrete v. asymptotic security bounds.) $\endgroup$
    – fkraiem
    Jul 13, 2015 at 17:17
  • 1
    $\begingroup$ What you are doing is simply to fix a value for the seed length (aka security parameter) $n$. This is the same as, say, fixing a key length in an encryption scheme: you have to do it sooner or later if you want to use it in practice. The benefit of keeping the asymptotic approach as long as possible, however, is that it allows you to increase the value of the security parameter without having to redo your entire analysis. $\endgroup$
    – fkraiem
    Jul 13, 2015 at 17:58
1
$\begingroup$

You're right: If you know the setup, calculating the next output from any given $x$ is fully deterministic and you know everything already.

Even if you don't know $a$ and $b$, those are easy to calculate from three consecutive $x_i$. If $n$ is not known, its calculation is still pretty easy, given a few consecutive $x_i$.

Anyway, LCGs are very unsuitable for cryptographic tasks. That's why in pretty much every standard library you find a warning not to use the standard Random class for cryptographic protocols (at least for Java and Python I know those warnings are there).

Usually not the entire output is used, but only a part of it, because otherwise two consecutive numbers can't be equal (and ever change again afterwards). Such an RNG is good enough for almost all non-security-related context, where randomness is needed (it is good enough for a little randomness. But e.g. in simulations, where a lot of random numbers are needed, you want "better" randomness, e.g. from the Mersenne Twister). Anyway, predictable PRNGs (without the CS) based on any such construction is not suited for cryptography. For CSPRNGs, you can find a couple of designs on wikipedia.

$\endgroup$
2
  • $\begingroup$ The Mersenne Twister is not a good PRNG in this context. First, it is predictable—after only 624 outputs we can completely predict it. Second, it is not statistically random precisely because there is a test that can distinguish its output from statistical randomness; specifically, with only 45,000 outputs it fails TestU01's Linear-Complexity test (which can detect most LFSR-based PRNGs). $\endgroup$
    – Charphacy
    Jul 13, 2015 at 23:25
  • $\begingroup$ I did not claim the Mersenne Twister is a good CSPRNG. It is a useful PRNG for simulations etc. where you need randomness with good statistical properties. It is kinda crucial to think of the "CS" part seperately: But I will point that out more explicitly $\endgroup$
    – tylo
    Jul 14, 2015 at 8:15
0
$\begingroup$

The goal of a random number generator is to generate a uniform distribution. Taken the LCG computational indistinguishability means that every sequence generated $\mod m$ is a uniform distribution over the values $0, ..., m-1$. The function parameters are not given. Instead you would have a sequnce $x_0, x_1, ...$ given and have to determine if all values are generated uniformly. The idea is to check if the LCG is $\epsilon$-distinguishable. Meaning that it is possible to predict the next generated value in polynomial time with a probability of $\frac{1}{n} + \epsilon$. The idea is to show that such the PRNG is not $\epsilon$-distinguishable for any value of $\epsilon$ in polynomial time.

$\endgroup$
5
  • $\begingroup$ So the strategy is then to show that LCGs are not pseudorandom generators because given a sequence $x_0, x_1, \ldots, x_n$, we could recover $a,b,m$ and hence claim that the provided sequence comes from some LCG with high probability, and was not generated from a truly uniform distribution? $\endgroup$
    – grawtin
    Jul 13, 2015 at 14:33
  • $\begingroup$ I think what is bothering me is: if we prove that $a,b,m$ could be recovered, does this show that LCGs are not pseudorandom generators, or that LCGs are not pseudoranom functions? $\endgroup$
    – grawtin
    Jul 13, 2015 at 14:36
  • $\begingroup$ They are not cryptographically secure pseudorandom number generators. They aren't PRFs in the cryptographical sense either. $\endgroup$
    – tylo
    Jul 13, 2015 at 16:05
  • $\begingroup$ I think what I'm struggling with is if it even makes sense to ask if they are pseudorandom number generators, in the computational indistinguishability sense. This definition requires that the generator in question can expand any seeds of any given length, (among other properties). I don't see how the LCGs can fit into this framework, they do not expand their inputs, and they do not accept variable length inputs. However, the pseudorandom function definition seems more applicable. Am I wrong? $\endgroup$
    – grawtin
    Jul 13, 2015 at 16:18
  • $\begingroup$ The seed must be a number in $0, .., m-1$ and is expanded to a list of numbers, so thats the expansions. If your $n$ is large, the expanded list is most likely larger too. You micht wonna take a look at the RSA-Generator: $s_i = s_{i-1}^e \pmod{n}$. Thats almost the same setup, but the RSA-Generator gives a way more unform distribution. $\endgroup$
    – Fleeep
    Jul 13, 2015 at 19:46

Your Answer

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

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