9
$\begingroup$

The Blum-Micali is a cryptographically secure pseudorandom number generator.

The construction (from wikipedia):

  • Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.

  • Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ \bmod{\ p}$.

  • The $i$-th output of the algorithm is 1 if $x_i < \frac{p-1}{2}$. Otherwise the output is 0.

I have toyed with small values of $p$ and have noticed that cycles occur if there's a fixed point, that is $x_{i+1} = x_i = g^{x_i}$.

For example when $g=3$ and $p=7$ (from wikipedia primitive root example), there are two fixed points where $3^4 = 4 \bmod 7$ and $3^5 = 5 \bmod 7$. This would be problematic for Blum-Micali generator since it would cycle and repeatedly output the same bit.

Is there a relationship with the size of $p$ and the period which is based on the likelihood of a fixed point?

$\endgroup$
  • 1
    $\begingroup$ Interesting question. The heuristic argument is obvious but I'd be interested in seeing some real (i.e. non-generic) analysis of the properties of $x \mapsto g^x \mod{p}$. Searching for "discrete logarithm fixed point" I found some references, but they all seem to focus on describing the set of primes and primitive roots with at least one fixed point, rather than a lower bound on the number of fixed points for any given $p$. $\endgroup$ – Thomas Apr 7 '14 at 7:41
  • 2
    $\begingroup$ The premise seems faulty. Cycles can occur even if there is no fixed point. So, focusing on fixed points seems mis-placed, if you really care about cycles. But, as I explain in my answer, worrying about short cycles is also mis-placed concern. $\endgroup$ – D.W. Apr 7 '14 at 8:50
1
$\begingroup$

Under the question's hypothesis, $x\mapsto g^x\bmod p$ is a permutation of $\mathbb Z_p^*$, that has some characteristics of being random.

If we take a random permutation of a set of size $s$, the length of the cycle iterating that permutation from a random point has length $l$ with probability exactly $1/s$, independent of integer $l$ with $1\le l\le s$. It follows that the cycle has length $l$ or less with probability exactly $l/s$.

This forms an heuristic argument (obvious, as pointed by Thomas in comment) that perhaps it is $\epsilon$-rare that the cycle length of the question's generator is much less than $\epsilon\,p$.

This is however very far from a proof or even a convincing argument. In particular, because $x\mapsto g^x\bmod p$ belongs to a very small and special subset of the permutations of $\mathbb Z_p^*$, with that subset having $(p-1)/2$ elements out of $(p-1)!$ permutations.

By contrast, D.W.'s argument is a valid proof that the cycle length is too large to be found when $p$ is such that the discrete logarithm problem is hard. However that gives a considerably looser safe estimate of the cycle length; perhaps likely at least $2^{100}$ for $2048$-bit randomly-seeded $p$, when the above heuristic argument suggests likely at least $2^{2040}$.

$\endgroup$
0
$\begingroup$

Since Blum-Micali is cryptographically secure, you know that there won't be a short cycle (not one short enough to detect in polynomial time), because a short cycle would violate cryptographic security. Therefore, you don't need to worry about this. It's not worth your time worrying about it: it's very unlikely you'll run into a short cycle.

That said, why do you want to use Blum-Micali? I wouldn't recommend it for any practical application. Instead, I'd recommend something like AES-CTR.

$\endgroup$
  • 2
    $\begingroup$ Regarding the last sentence, how exactly did you arrive at the conclusion that the OP wanted to use Blum-Micali? Seems to me he was only curious about the implications of fixed points in the permutation function. $\endgroup$ – Thomas Apr 7 '14 at 10:48
-3
$\begingroup$

What is often recommended is to make sure that your value of g is a "generator" mod p. I don't know if this term is often used, but I've had it defined as cycling through the entirety of a set {0, 1, ..., p - 1} by raising it to consecutive powers mod p. If you use a number with this property, you will never have any short cycles and will in fact generate every value available mod p.

$\endgroup$
  • 1
    $\begingroup$ This doesn't really seem to answer the question. $\endgroup$ – Maeher Feb 5 '18 at 11:10
  • $\begingroup$ $g$ is a generator if and only if $x\mapsto g^x\bmod p$ is a permutation. But permutations can have short cycles, hence it does not follows from $g$ being a generator that the construction in the question has maximum cycle; and experiment (as pointed by the question) shows otherwise. Further, the problem statement has "let $g$ be a primitive root modulo $p$", which means $g$ is a generator, thus this answer's recommendation is already part of the problem statement. $\endgroup$ – fgrieu Feb 5 '18 at 14:09

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.