Predicting the elliptic curve congruential generator

DOI10.1007/S00200-016-0303-XzbMATH Open1369.11099arXiv1609.03305OpenAlexW2514154808MaRDI QIDQ2363380FDOQ2363380

Authors: László Mérai 

Publication date: 19 July 2017

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Abstract: Let $p$ be a prime and let $mathbfE$ be an elliptic curve defined over the finite field $mathbb{F}_p$ of $p$ elements. For a point $GinmathbfE(mathbb{F}_p)$ the elliptic curve congruential generator (with respect to the first coordinate) is a sequence $(x_n)$ defined by the relation $x_n=x(W_n)=x(W_{n-1}oplusG)=x(nGoplus{W}_0)$, $n=1,2,dots$, where $oplus$ denotes the group operation in $mathbfE$ and $W_0$ is an initial point. In this paper, we show that if some consecutive elements of the sequence $(x_n)$ are given as integers, then one can compute in polynomial time an elliptic curve congruential generator (where the curve possibly defined over the rationals or over a residue ring) such that the generated sequence is identical to $(x_n)$ in the revealed segment. It turns out that in practice, all the secret parameters, and thus the whole sequence $(x_n)$, can be computed from eight consecutive elements, even if the prime and the elliptic curve are private.

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

Recommendations

• Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
• Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith’s Methods
• Attacking the linear congruential generator on elliptic curves via lattice techniques
• Inferring sequences produced by elliptic curve generators using Coppersmith's methods
• scientific article; zbMATH DE number 1972846

zbMATH Keywords

cryptographyelliptic curvepseudorandom sequencecongruential generator

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Pseudo-random numbers; Monte Carlo methods (11K45) Computer solution of Diophantine equations (11Y50) Elliptic curves (14H52) Calculation of integer sequences (11Y55)

Cites Work

• Pseudorandom sequences
• Elliptic curves. Number theory and cryptography
• On the linear complexity and multidimensional distribution of congruential generators over elliptic curves
• Title not available (Why is that?)
• On a Class of Pseudorandom Sequences From Elliptic Curves Over Finite Fields
• A family of elliptic curve pseudorandom binary sequences
• Remarks on pseudorandom binary sequences over elliptic curves
• Construction of pseudorandom binary sequences over elliptic curves using multiplicative characters
• Elliptic curve analogue of Legendre sequences
• Construction of Pseudo-random Binary Sequences from Elliptic Curves by Using Discrete Logarithm
• Pseudorandom Points on Elliptic Curves over Finite Fields
• Title not available (Why is that?)
• Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
• Title not available (Why is that?)
• Large families of elliptic curve pseudorandom binary sequences
• On lattice profile of the elliptic curve linear congruential generators

Cited In (5)

• Pseudorandom vector generation using elliptic curves and applications to Wiener processes
• Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith’s Methods
• Inferring sequences produced by elliptic curve generators using Coppersmith's methods
• Attacking the linear congruential generator on elliptic curves via lattice techniques
• An improved method for predicting truncated multiple recursive generators with unknown parameters

This page was built for publication: Predicting the elliptic curve congruential generator

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