On the linear complexity profile of some sequences derived from elliptic curves

DOI10.1007/S10623-015-0140-0MaRDI QIDQ306337zbMATH OpenOpenAlexFDO

Authors László Mérai, Arne Winterhof

Publication date 31 August 2016

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

elliptic curveslinear complexitypseudorandom sequencesEdwards coordinateselliptic curve generatorelliptic curve power generator

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Cryptography (94A60) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Elliptic curves (14H52)

Abstract: For a given elliptic curve $mathbfE$ over a finite field of odd characteristic and a rational function $f$ on $mathbfE$ we first study the linear complexity profiles of the sequences $f(nG)$, $n=1,2,dots$ which complements earlier results of Hess and Shparlinski. We use Edwards coordinates to be able to deal with many $f$ where Hess and Shparlinski's result does not apply. Moreover, we study the linear complexities of the (generalized) elliptic curve power generators $f(e^{n}G)$, $n=1,2,dots$. We present large families of functions $f$ such that the linear complexity profiles of these sequences are large.

Recommendations

• On the linear complexity of the Naor-Reingold pseudo-random function from elliptic curves.
• On the linear complexity and multidimensional distribution of congruential generators over elliptic curves
• Inferring sequences produced by elliptic curve generators using Coppersmith's methods
• On the linear complexity profile of the power generator
• Linear complexity and related complexity measures
• On the linear complexity of the power generator
• On pseudorandom properties of certain sequences of points on elliptic curve
• Construction of \(k\)-ary pseudorandom elliptic curve sequences
• Generation of pseudorandom sequence over elliptic curve group and their properties
• scientific article; zbMATH DE number 1440879

Cites work

• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• A complete set of addition laws for incomplete Edwards curves
• A normal form for elliptic curves
• Applied number theory
• Certain Exponential Sums and Random Walks on Elliptic Curves
• Character sums with exponential functions
• Elliptic curves. Number theory and cryptography
• Faster Addition and Doubling on Elliptic Curves
• Linear complexity and related complexity measures
• On the elliptic curve power generator
• On the joint linear complexity profile of explicit inversive multisequences
• On the linear complexity and multidimensional distribution of congruential generators over elliptic curves
• On the linear complexity of the power generator
• On the linear complexity profile of the power generator
• Progress in Cryptology - INDOCRYPT 2003
• Pseudorandom sequences
• Recent results on recursive nonlinear pseudorandom number generators (invited paper)

Cited in

(9)

• Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
• Sequences with almost perfect linear complexity profiles and curves over finite fields
• Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith’s Methods
• Linear complexity of some sequences derived from hyperelliptic curves of genus 2
• On the elliptic curve endomorphism generator
• Linear complexity of sequences on Koblitz curves of genus 2
• On the linear complexity of the Naor-Reingold sequence with elliptic curves
• Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
• Secure simultaneous bit extraction from Koblitz curves

This page was built for publication: On the linear complexity profile of some sequences derived from elliptic curves

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