Analysis of the width-w non-adjacent form in conjunction with hyperelliptic curve cryptography and with lattices

DOI10.1016/J.TCS.2013.04.006MaRDI QIDQ387802zbMATHOpenAlexDBLPWikidataFDO

Authors Daniel Krenn

Publication date 17 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1209.0618

zbMATH Keywords

latticesscalar multiplication\(\tau\)-adic expansionsFrobenius endomorphismhyperelliptic curve cryptographyKoblitz curvesnumeral systemsredundant digit setssum of digitswidth-\(w\) non-adjacent forms

Mathematics Subject Classification ID

Cryptography (94A60) Radix representation; digital problems (11A63) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Abstract: We analyse the number of occurrences of a fixed non-zero digit in the width-w non-adjacent forms of all elements of a lattice in some region (e.g. a ball). Our result is an asymptotic formula, where its main term coincides with the full block length analysis. In its second order term a periodic fluctuation is exhibited. The proof follows Delange's method. This result in a general lattice set-up is then used for numeral systems with an algebraic integer as base. Those come from efficient scalar multiplication methods (Frobenius-and-add methods) in hyperelliptic curves cryptography, and our result is needed for analysing the running time of such algorithms.

Recommendations

• Analysis of width-\(w\) non-adjacent forms to imaginary quadratic bases
• Speeding up the elliptic curve scalar multiplication using non adjacent form
• Minimality and other properties of the width-𝑤 nonadjacent form
• Optimality of the width-w non-adjacent form: general characterisation and the case of imaginary quadratic bases
• On the low Hamming weight discrete logarithm problem for nonadjacent representations

Cites work

• scientific article; zbMATH DE number 194082 (Why is no real title available?)
• scientific article; zbMATH DE number 1302857 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1088246 (Why is no real title available?)
• scientific article; zbMATH DE number 3056377 (Why is no real title available?)
• A note on window \(\tau\)-NAF algorithm
• Analysis of alternative digit sets for nonadjacent representations
• Analysis of width-\(w\) non-adjacent forms to imaginary quadratic bases
• Distribution results for low-weight binary representations for pairs of integers
• Efficient algorithms for Koblitz curves over fields of characteristic three
• Efficient arithmetic on Koblitz curves
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• La conjecture de Weil. I
• Measure, topology, and fractal geometry
• Nonadjacent Radix-τ Expansions of Integers in Euclidean Imaginary Quadratic Number Fields
• Numbers of solutions of equations in finite fields
• On the Rationality of the Zeta Function of an Algebraic Variety
• Optimality of the width-\(w\) non-adjacent form: general characterisation and the case of imaginary quadratic bases
• Sur la fonction sommatoire de la fonction 'somme des chiffres'

Cited in

(1)

• On the distribution of the coefficients of normal forms for Frobenius expansions

This page was built for publication: Analysis of the width-\(w\) non-adjacent form in conjunction with hyperelliptic curve cryptography and with lattices

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