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

DOI10.1007/S10623-015-0140-0zbMATH Open1383.94010arXiv1509.06909OpenAlexW2263720025MaRDI QIDQ306337FDOQ306337

Arne Winterhof, László Mérai

Publication date: 31 August 2016

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster Addition and Doubling on Elliptic Curves
• A normal form for elliptic curves
• A complete set of addition laws for incomplete Edwards curves
• On the linear complexity and multidimensional distribution of congruential generators over elliptic curves
• On the linear complexity profile of the power generator
• Applied Number Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recent Results on Recursive Nonlinear Pseudorandom Number Generators
• Certain Exponential Sums and Random Walks on Elliptic Curves
• Character sums with exponential functions
• Progress in Cryptology - INDOCRYPT 2003
• On the joint linear complexity profile of explicit inversive multisequences
• On the linear complexity of the power generator

Cited In (9)

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

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)