Paper 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 ECDLP. 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.

Note: Several small corrections have been made.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
Pseudorandomnessindistinguishability
Contact author(s)
a sidorenko @ tue nl
History
2006-09-15: revised
2006-06-19: received
See all versions
Short URL
https://ia.cr/2006/190
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/190,
      author = {Berry Schoenmakers and Andrey Sidorenko},
      title = {Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator},
      howpublished = {Cryptology ePrint Archive, Paper 2006/190},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/190}},
      url = {https://eprint.iacr.org/2006/190}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.