Cryptology ePrint Archive: Report 2006/190
Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator
Berry Schoenmakers and Andrey Sidorenko
Abstract: The Dual Elliptic Curve Pseudorandom Generator (DEC PRG) is
proposed by Barker and Kelsey in a draft NIST Special Publication.
It is claimed that the pseudorandom generator is
secure unless the adversary can solve the elliptic curve discrete
logarithm problem (ECDLP) for the corresponding elliptic curve.
The claim is supported only by an informal discussion. No security
reduction is given, that is, it is not shown that an adversary
that breaks the pseudorandom generator implies a solver for the
Our experimental results and also empirical argument show that the
DEC PRG is insecure. The attack does not imply
solving the ECDLP for the corresponding elliptic curve. The attack
is very efficient.
Category / Keywords: Pseudorandomness, indistinguishability
Date: received 7 Jun 2006, last revised 15 Sep 2006
Contact author: a sidorenko at tue nl
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: Several small corrections have been made.
Version: 20060915:153341 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]