3
$\begingroup$

The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$. One can choose $a,b$ in $k$ such that the orbit length of the iteration is exactly $p$. My question is very simple:

Is the Inversive Congruential Generator actually used in Cryptography? Is there any known attack against it?

$\endgroup$
1
$\begingroup$

The inversive congruential generator is not commonly used in cryptography. Its basic description, in fact, makes it entirely unsuitable for it—once you know a single value of $x$, you can predict the remainder of the sequence, which is something a secure pseudorandom generator should not allow.

To avoid the above trivial attack, you could truncate the output to, say, half of the bits of $x$. But the truncated inversive generator is also predictable by more elaborate means, as long as you truncate fewer than half the bits.

To top it off, inversion modulo $p$ is a very slow operation, which makes this generator very inefficient. So even for non-cryptographic purposes this is not a good generator to use.

$\endgroup$
  • $\begingroup$ I am not convinced: sending an hash of x instead of x would fix the issues above. $\endgroup$ – Reyx_0 Aug 30 '18 at 8:12
  • $\begingroup$ Sending an hash of $x, x+1, x+2, \dots$ would also be secure. Does that make $x, x+1, x+2, \dots$ a good random number generator? $\endgroup$ – Samuel Neves Aug 30 '18 at 18:48
  • $\begingroup$ Ok, but on the other hand x, x+1,... does not have nice distribution properties: how would you select an hash function such that when you hash x, x+1,... you can prove that the sequence has a nice discrepancy bound? It should be relatively easy to select a simple function of the bits of the elements in an ICG sequence such that the same discrepancy bound as the sequence is preserved (which is not sending "half of the bits" which does sound like a terrible idea). $\endgroup$ – Reyx_0 Aug 31 '18 at 11:21
-1
$\begingroup$

There are some inconsistencies with the arguments in the above answer.

You want to compare ICG with a cryptographically secure pseudorandom number generator.

Consider the cryptographically secure Blum Blum Shub (it should be one of the best, according to the abstract of this paper for example: https://pdfs.semanticscholar.org/8074/d7df08e2bcbe8f433ec368a5d84c8061f9be.pdf )

The pseudorandom number generator is simply given by $x_n= x_{n-1}^2$ modulo $M=pq$ that is the product of two large primes: see https://en.wikipedia.org/wiki/Blum_Blum_Shub for a quick introduction.

Observing even one iteration $x_n$ results in knowing exactly all the other terms of the sequence. The whole point is that only the "least significant bits" (notice: not "the most significant bits", in contrast with the setting of the attack mentioned in Samuel's answer) are sent or even only the bit parity of the element in the sequence (see again https://en.wikipedia.org/wiki/Blum_Blum_Shub for a reference)

Notice that this strategy of sending only the bit parity of $x_n$ is directly applicable to the Inversive Congruential Generator (ICG) and then the problem of predicting the sequence looks immediately untreatable (of course, if $a,b$ are hidden).

Concerning the computational cost: the ICG costs essentially one inversion mod p (notice that if in the definition of the ICG one chooses $a,b$ "very small", the multiplication of $a$ and $1/x$ can be counted as an addition). On the other hand, Blum Blum Shub costs one multiplication. The ratio of the cost of an inversion and a multiplication is only $O(log log log(p))$, which make the two generators very similar from a computational point of view.

On the other hand, ICG has the advantage of covering the entire space $\mathbb F_p$ is $a,b$ are suitably chosen.

That is never possible for the Blum Blum Shub generator: modulo $M=pq$, you will never get an element multiple of $p$ and also even the multiplicative group $(\mathbb Z/pqZ)^*$ (meaning the invertible elements modulo $pq$) is never cyclic for odd $p,q$.

$\endgroup$

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.