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

DOI10.1016/J.TCS.2013.04.006zbMATH Open1347.11010DBLPjournals/tcs/Krenn13arXiv1209.0618OpenAlexW1992177671WikidataQ42154954 ScholiaQ42154954MaRDI QIDQ387802FDOQ387802

Daniel Krenn

Publication date: 17 December 2013

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

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.

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

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

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)

Cites Work

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

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)