Score:3

Crypto

How to choose Kangaroo algorithm parameters?

Rudeus

11/5/23, 8:38 PM

I am implementing pollard kangaroo to compute the discrete logarithm of a group element $G$ of generator $g$. $G$ is a$\mod p$ multiplicative group ($p$ a prime number). So, I want to solve $g^a=h$ knowing $a\in[[0,w]]$.

What I am basically doing:

Define $w=2^{58}$
I define $k$.
Split $G$ into $k$ subset $S_i$.
I define $f(x)=xg^{2 ^ {x \mod k}}$
From here I make two kangaroo walk alternatively...

The first wild kangaroo : $y_0=h$ and $y_{i+1}=f(y_i)$. I store the values in a Hash map. The second tame kangaroo : $x_0=int(w/2)$ and $x_{i+1}=f(x_i)$. I store the values in another Hash map.

Whenever a kangaroo value at an iteration is in the other kangaroo hash map, I can easily retrieve the discrete log.

My implementation works if $w$ is very close to $2h$. Otherwise it take a lot of time and memory.

What I think I might have done wrong:

The distinguisher: I was not able to define a good distinguisher. I am storing all my values of $y_i$ and $x_i$
The value of $k$ and how I split $G$. I defined the exponents as $e_i = 2^i$ (affecting my definition of $f$). Was that bad?

Any help will be much appreciated. I can even give the code if you are interested but it is really a long code...

178

1 + 2

discrete-logarithm

algorithm-design

Daniel S

11/6/23, 12:58 PM

It's not clear what $G$ and $C$ are, but presumably a mod $p$ multiplicative group? In any event, this doesn't look to be set-up correctly. $x_0=w/2$ is a value of unknown logarithm (you've not made it clear how it can be treated as a member of $G$) and should not allow recovery of anything.

Rudeus

11/6/23, 2:22 PM

I corrected a typo with $C$... Indeed we are working in a multiplicative group mod p aka all the multiplication and addition are done modulo a prime number p. The kangaroo algorithm assumes we know a $w$ that bounds $a$. I am not sure about the algorithm caring if $w/2$ is a member of $G$ or not ... @DanielS

Score:1

Crypto

Daniel S

11/6/23, 4:17 PM

Things look broadly correct, though I really think that $x_0$ should be $g^{w/2}$ rather than $\mathtt{int}(w/2)$.

Note that if we write $a=w/2+\delta$ for some $-w/2\le \delta\le w/2$ then with $s$ steps we can at most be testing for $\delta$ of size $O(s\sqrt w)$ and so we expect the method to perform better for small $\delta$, though this means $w$ is close to $2a$ rather than $2h$ (being close to $2h$ should not be having any effect).

In terms of time I hope that you are precomputing $m(i):=g^{2^i}$ for $0\le i\le k-1$ using the recurrence $m(i+1)=g\cdot m(i)\mod p$, storing the result and then computing $f(x)$ as $f(x)=x\cdot m(x\mod k)\mod p$.

In terms of memory, only storing distinguished points might involve only saving $y_i$ and $x_j$ where the trailing bits are all 1s (e.g. the last 5 bits are all 1), though the number of steps will increase marginally.

+ 5

Rudeus

11/6/23, 5:09 PM

Thank you so much. Indeed it is my mistake another typo: $x_0$ is $g^{w/2}$ in my program ... I did not think about this optimization with precomputing $m$. I will surely try it out !!! I understand your idea of trailing bits but I can't see why it does mathematically work ... I mean by using this distinguisher isn't there a possibility of filtering out a possible kangaroo collision ?

Daniel S

11/6/23, 5:55 PM

Note that once there is a collision such as $y_i=x_j$ then all future increments will also be collisions i.e. $y_{i+1}=x_{j+1}$, $y_{i+2}=x_{j+2}$ etc. After a few increments you should hit a filtered point (e.g. after 32 or so increments if we look for the last 5 bits to be all 1s.

Rudeus

11/7/23, 1:43 PM

Your answer made my implementation much better. In my tests, when $a \simeq 2^{54.1}$ I choose $w = 2^{55}$. My program then breaks the log really fast. However, when $a \simeq 2^{57,781}$ I choose $w = 2^{58}$. My program is then taking a lot of time to break the discrete log to get $a$. Is this normal or I am missing something again ?

Rudeus

11/7/23, 1:55 PM

When I say takes a lot of time I mean I made each kangaroos walk $1 000 000 000$ times and still nothing. Plus my algorithm doesn't have a stopping point: it either find the discrete log or run forever ...

Daniel S

11/7/23, 2:53 PM

1,000,000,000 does not sound unreasonable; [Pollard](https://link.springer.com/content/pdf/10.1007/s001450010010.pdf) estimates an average $3w^{1/2}$ steps when near the end of the interval which would be over 1,600,000,000 steps when $w=2^{58}$.

Elon Musk

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

EN: How to choose Kangaroo algorithm parameters?

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.