Posts  / #POST-223186
REDDIT

How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case ?

A
Nov 4, 2024 · 15:25

So I was reading about [this paper](https://eprint.iacr.org/2024/1321). The underlying idea is to lift the discrete logarithm problem to *prime−1* for prime curves or *order−1* for binary curves since most elliptic curves only have small factors in that case. But [their baby‑step giant‑step variant seems to only work when the private key already lie in a specific subgroup](https://github.com/cysecud/ecc_weak_keys/blob/master/gp_code/alg.gp#L21). That is : no indication is made on how to move the key to each underlying order subgroup.
And of course, using exponentiations to solve the problem isn’t a reason that allow building an index calculus algorithm…

If I understand correctly (or maybe I’m wrong), being able to use Pohlig Hellman would require using auxiliary inputs **as proposed by Cheon** : but in my case, I only have 48 of them over the extension of a pairing friendly curve of large characteristic.

Post image