2
$\begingroup$

Assuming we found a constant $g$ and a prime $P$ which is able to produce all values from $1$ to $P-1$ with it's sequence $$s_{i} = g^{s_{i-1}} \mod P$$ $$s_0 = g$$

How many steps are needed to compute $i$ for a given value $v$ ($=s_i$) with known $g,P$?
Can it be faster than $i$ steps?


toy example:

With $P=5, g=3$ the sequence would be $$\begin{split} &[3, 3^3\equiv 2, 3^{2} \equiv 4, 3^{4} \equiv 1] \mod 5 \\ \equiv&[3, 2, 4, 1] \mod 5 \end{split}$$

Or for $P=23, g=20$ the values would be: $$[20,18,2,9,5,10,8,6,16,13,14,4,12,3,19,17,7,21,15,11,22,1]$$ or $P=59, g=39$


side-questions:

  • How many steps are needed to compute the resulting $s_i$ for given $i,g,P$? Faster than $O(i)$?

  • Is it also possible to compute $s_{i-1}$ out of $s_{i}$ ? Or is it similar to the DLP?

  • Has this kind of sequence already some name?

$\endgroup$

1 Answer 1

3
$\begingroup$

This sequence is the sequence of states of the Blum-Micali algorithm with seed $g$.

The question of whether $s_i$ can be computed in fewer than $i$ steps is a question as to whether the generator can be "giant stepped". To my knowledge we do not know of a way to do this.

Computing $s_{i-1}$ from $s_i$ is precisely equivalent to the discrete logarithm problem and is used to demonstrate the forward security of the generator.

$\endgroup$

Your Answer

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

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