The Xedni calculus and the elliptic curve discrete logarithm problem
type: Item
instance of: scholarly article
title: The Xedni calculus and the elliptic curve discrete logarithm problem
zbMATH Open document ID: 0948.11049
DOI: 10.1023/A:1008319518035
author: Joseph H. Silverman
published in: Designs, Codes and Cryptography
publication date: 2000-07-19T00:00:00Z
review text: This paper describes a possible way to solve the elliptic curve discrete logarithm problem, a problem upon which a number of cryptographic systems are based. The basic idea of the paper is to lift an elliptic curve over a finite field, together with some points on it, to the rationals. Then, by finding a linear combination between the lifted points, assuming the lifted points are independent in the Mordell-Weil group, one can hopefully solve the original discrete logarithm problem. The method was independently developed by the current paper and by \textit{H. J. Kim} et. al. [Proc. Japan Acad., Ser A 75, 166-169 (1999; Zbl 0948.11050)]. Silverman called this method the Xedni calculus (Xedni is index spelt backwards) since it resembles the exact opposite of what one does in the Index calculus method. In index calculus one usually attempts to solve a discrete logarithm by collecting a set of linear relations amongst a set of generators of the group (the so called factorbase). Once enough relations have been found, linear algebra can be used to determine the desired discrete logarithm. The relations in index calculus are found by taking some global information and looking at it locally. In the Xedni calculus one takes some local information, i.e. some points on an elliptic curve over a finite field, and hopefully then lifts this to the global situation, i.e. some points on an elliptic curve over the rationals. Then one aims to produce a single global relation which will give rise to a single local relation. In a later paper \textit{M. J. Jacobson}, et. al., Des. Codes Cryptography 20, 41-64 (2000; Zbl 0948.11049)] the Xedni calculus is shown not to be a threat to elliptic curve cryptosystems. However, the method does contain some interesting mathematical ideas which are of independent interest away from the main application of cryptography.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14Q05
Mathematics Subject Classification ID: 11G05
zbMATH DE Number: 1441590
zbMATH Keywords: elliptic curves
zbMATH Keywords: discrete logarithm
zbMATH Keywords: cryptography
MaRDI profile type: Publication
Recommended article: Elliptic curve lifting problem and its applications
Recommended article: Analysis of the Xedni calculus attack
Recommended article: Lifting and Elliptic Curve Discrete Logarithms
Recommended article: Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
Recommended article: Q2739457
Recommended article: Q4249259
Recommended article: A Las Vegas algorithm to solve the elliptic curve discrete logarithm problem
Recommended article: Handbook of Elliptic and Hyperelliptic Curve Cryptography
Recommended article: Q3374896
Recommended article: On remarks of lifting problems for elliptic curves
description: scientific article; zbMATH DE number 1441590