International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator

Authors:
Berry Schoenmakers
Andrey Sidorenko
Download:
URL: http://eprint.iacr.org/2006/190
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21683,
  title={Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator},
  booktitle={IACR Eprint archive},
  keywords={Pseudorandomness, indistinguishability},
  url={http://eprint.iacr.org/2006/190},
  note={ a.sidorenko@tue.nl 13406 received 7 Jun 2006, last revised 15 Sep 2006},
  author={Berry Schoenmakers and Andrey Sidorenko},
  year=2006
}