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]$

J. Doe

6/25/23, 8:02 AM

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?

0 + 0

permutation

discrete-logarithm

finite-field

complexity

attack

Score:3

Crypto

Daniel S

6/25/23, 9:36 AM

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.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: 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]$

TH: การหา $i$ สำหรับลำดับนั้นยากเพียงใด $s_{i} = g^{s_{i-1}} \mod P$ กับ $s_0 = g$ สำหรับค่าที่กำหนด $v\in [1,P-1]$

RO: Cât de dificil este să găsești $i$ pentru secvența $s_{i} = g^{s_{i-1}} \mod P$ cu $s_0 = g$ pentru valoarea dată $v\in [1,P-1]$

RU: Насколько сложно найти $i$ для последовательности $s_{i} = g^{s_{i-1}} \mod P$ с $s_0 = g$ для заданного значения $v\in [1,P-1]$

VI: Tìm $i$ cho chuỗi $s_{i} = g^{s_{i-1}} \mod P$ với $s_0 = g$ cho giá trị đã cho $v\in [1,P-1]$ khó đến mức nào

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.