Algebraic groups and discrete logarithm

Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50) Cryptography (94A60)

Review text

The present paper discusses the existence of a subexponential algorithm for solving the discrete logarithm problem (DLP) in the context of algebraic groups. NEWLINENEWLINENEWLINEThe DLP can be defined in any finite abelian group \(G\): as is well known given \(g\in G\), of order \(n\), and \(a\in \langle g\rangle\), the DLP ask for the unique integer \(x\), \(0\leq x\leq n-1\), such that \(a=g^x\).NEWLINENEWLINENEWLINESince it was proposed as one-way function in the seminal paper of \textit{W. Diffie} and \textit{M. Hellman} [IEEE Trans. Inf. Theory 22, 644-654 (1976; Zbl 0435.94018)], the DLP is used in many public-key encryption and signature schemes. The group used was the multiplicative group \(F_q^{*}\) of a finite field \(F_q\).NEWLINENEWLINENEWLINEHowever the Index-Calculus method showed the existence of a subexponential algorithm for the group \(F_q^{*}\). Then \textit{V. Miller} [Advances in Cryptology -- Crypto '85, Lect. Notes Comput. Sci. 218, 417-426 (1986; Zbl 0589.94005)] and \textit{N. Koblitz} [Math. Comput. 48, 203-209 (1987; Zbl 0622.94015)], suggested the group of points \(E(F_q)\) on an elliptic curve over a finite field \(F_q\) as an alternative candidate. At present the DLP on elliptic curves has proved to be more intractable than the DLP in finite fields (except particular cases as anomalous or supersingular elliptic curves). Instead of \(E(F_q)\) the Jacobian of any algebraic group can be taken as basis group (the complexity issues of hyperelliptic curves have been particularly studied).NEWLINENEWLINENEWLINEIn Section 3 the author studies the asymptotic complexity of the DLP in Picard groups of algebraic curves over a fixed finite field \(F_q\). Theorem 1 proves the existence of a random subexponential algorithm computing the DLP in the Jacobians \({\mathcal H}_i\) of a family \(\{C_i\}\) of curves with genus tending to infinity and with bounded size of \({\mathcal H}_i\).NEWLINENEWLINENEWLINEConversely, in Section 4, the author considers DLP in a fixed algebraic group over increasing extensions of the base field and Theorem 2 lists some properties of easy algebraic groups. \(G\) is an easy algebraic group over \(F_q\) if there exists an algorithm that solves DLP in the groups \(G_k= G(F_{q^k})\) in subexponential random time.NEWLINENEWLINENEWLINEThe paper is finished by outlining some open questions about the category of easy algebraic groups.NEWLINENEWLINEFor the entire collection see [Zbl 0976.00054].

Recommendations

Cited in

(12)

This page was built for publication: Algebraic groups and discrete logarithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2764230)