How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$

Question

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?

Answer 1

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.