Koblitz curve cryptosystems
type: Item
instance of: scholarly article
title: Koblitz curve cryptosystems
zbMATH Open document ID: 1073.94013
author: Tanja Lange
published in: Finite Fields and their Applications
publication date: 2005-06-01T00:00:00Z
review text: In elliptic and hyperelliptic Public Key Cryptography one needs to compute scalar multiples of a point of the curve or a divisor of its Jacobian. It is then crucial having methods to speed up such an arithmetic operation. In her Ph.D. Thesis [Efficient arithmetic on hyperelliptic curves, University Essen (2001; Zbl 1047.94008)] and several papers the author addressed the problem of efficiently carring out the arithmetic in hyperelliptic curves. The present paper investigates the use of Koblitz hyperelliptic curves (curves defined over and small finite field and consider over a large extension field). The use of Koblitz curves was proposed by \textit{N. Koblitz}, [Crypto'91, Lect. Notes Comput. Sci. 576, 279--287 (1992; Zbl 0780.14018)]. For these curves the point counting is easy and \textit{A. J. Menezes} and \textit{S. Vanstone} [Auscrypt 90, Lect. Notes Comput. Sci. 453, 2--13 (1990; Zbl 0722.94012)] proposed the use of the Frobenius endomorphism to speed up the computation of scalar multiples of a point, using a certain scalar's expansion. Several authors studied the generalization of Koblitz idea to hyperelliptic curves. This paper presents new techniques to apply the Frobenius endomorphism to the computation of scalar multiples and investigates the properties of the expansions. The author claims that her approach is different from alternative ones [\textit{Y. Choie} and \textit{J. W. Lee}, Indocrypt 2002, Lect. Notes Comput. Sci. 2551, 285--295 (2002; Zbl 1033.11504); \textit{Y.-H. Park, S. Jeong} and \textit{J. Lim}, Eurocrypt 2002, Lect. Notes Comput. Sci. 2332, 197--208 (2002; Zbl 1055.94022)] ``as our expansions are shorter and are proven to be finite''. Section 2 and 3 recall the needed mathematical background. The core of the paper is Section 4 where the main results and algorithms are provided. The author shows that for \(m\sim q^{gn}\)\, the computation of \(mD\) needs only \(\sim n^{(q^g-1)/q^g}\) group operations (the drawback is that \((q^g-1/2)\) e…
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 2173075
zbMATH Keywords: cryptography
zbMATH Keywords: discrete logarithm systems
zbMATH Keywords: hyperelliptic curves
zbMATH Keywords: Koblitz curves
zbMATH Keywords: Frobenius expansions
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: j.ffa.2004.07.001
OpenAlex ID: W2058562429
cites work: Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
cites work: Computing in the Jacobian of a Hyperelliptic Curve
cites work: Q4417413
cites work: Improved low-density subset sum algorithms
cites work: New directions in cryptography
cites work: Q4502491
cites work: A public key cryptosystem and a signature scheme based on discrete logarithms
cites work: Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
cites work: Public Key Cryptography – PKC 2004
cites work: Fast addition on non-hyperelliptic genus 3 curves
cites work: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
cites work: Q4474195
cites work: Constructive and destructive facets of Weil descent on elliptic curves
cites work: Advances in Cryptology - EUROCRYPT 2004
cites work: Q2762749
cites work: Q4536202
cites work: Q4736431
cites work: Lattice attacks on digital signature schemes
cites work: Hyperelliptic cryptosystems
cites work: Q4035791
cites work: Q4530230
cites work: Formulae for arithmetic on genus 2 hyperelliptic curves
cites work: Collisions in fast generation of ideal classes and points on hyperelliptic and elliptic curves
cites work: Q4871722
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Q4718481
cites work: Q2724449
cites work: Q3211242
cites work: Q4318707
cites work: Fast multiplication on elliptic curves over small fields of characteristic two
cites work: The insecurity of the elliptic curve digital signature algorithm with partially known nonces
cites work: Q4941845
cites work: Q4737244
cites work: Elliptic curve cryptosystems over small fields of odd characteristic
cites work: Q4364563
cites work: Efficient arithmetic on Koblitz curves
cites work: Algebraic function fields and codes
cites work: Q4250816
DOI: 10.1016/J.FFA.2004.07.001
description: scientific article; zbMATH DE number 2173075