Research on attacking a special elliptic curve discrete logarithm problem (Q1793291)

Summary: Cheon first proposed a novel algorithm for solving discrete logarithm problem with auxiliary inputs. Given some points \(P, \alpha P, \alpha^2 P, \ldots, \alpha^d P \in \mathbb{G}\), an attacker can solve the secret key efficiently. In this paper, we propose a new algorithm to solve another form of elliptic curve discrete logarithm problem with auxiliary inputs. We show that if some points \(P, \alpha P, \alpha^k P, \alpha^{k^2} P, \alpha^{k^3} P, \ldots, \alpha^{k^{\varphi(d) - 1}} P \in \mathbb{G}\) and a multiplicative cyclic group \(K = \langle k \rangle\) are given, where \(d\) is a prime, \(\varphi(d)\) is the order of \(K\). The secret key \(\alpha \in \mathbb{F}_p^\ast\) can be solved in \(\mathcal{O}(\sqrt{(p - 1) / d} + d)\) group operations by using \(\mathcal{O}(\sqrt{(p - 1) / d})\) storage.