O28 — Discrete logarithms in elliptic-curve groups

Definitions and mathematical statement

An elliptic curve $E$ over a prime field $\mathbb F_p$ is a nonsingular projective genus-one curve with a specified rational identity point $O$. It may be supplied by the coefficients of a nonsingular Weierstrass equation. Its rational points form a finite abelian group, with addition given by the usual chord-and-tangent law and $O$ as identity.

The input consists of $p$, the curve coefficients, and points $P,Q\in E(\mathbb F_p)$, all in standard binary coordinate encodings. It is promised that $P\in\langle Q\rangle=\{[j]Q:j\in\mathbb Z\}$. Here $[j]Q$ denotes repeated group addition, with the usual extension to zero and negative integers.

Is there a deterministic classical algorithm which returns an integer $t$ such that $P=[t]Q$ in time polynomial in the input length? The output may be any valid nonnegative representative of polynomial binary length; the least representative is not required. When $Q=O$, the promise forces $P=O$ and $t=0$ qualifies.

Neither the order of $Q$ nor a factorization of the group order is supplied as extra input. The algorithm must work uniformly across all prime fields, nonsingular curves, and promised point pairs. It is not restricted to a cryptographic family or random instances. The problem concerns classical bit complexity; quantum group operations are not allowed as primitive operations.

Short English statement

Can every promised elliptic-curve discrete logarithm over a prime field be computed deterministically in polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400032 (AMR-083-0032), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O28, p19 / LNCS p309. Original source indexed by AMR-083-0032. https://mccurley.org/papers/open.ps.gz.