Efficient Pseudorandom Generators Based on the DDH Assumption

Reza Rezaeian Farashahi; Berry Schoenmakers; Andrey Sidorenko

Paper 2006/321

Efficient Pseudorandom Generators Based on the DDH Assumption

Reza Rezaeian Farashahi, Berry Schoenmakers, and Andrey Sidorenko

Abstract

A family of pseudorandom generators based on the decisional Diffie-Hellman assumption is proposed. The new construction is a modified and generalized version of the Dual Elliptic Curve generator proposed by Barker and Kelsey. Although the original Dual Elliptic Curve generator is shown to be insecure, the modified version is provably secure and very efficient in comparison with the other pseudorandom generators based on discrete log assumptions. Our generator can be based on any group of prime order provided that an additional requirement is met (i.e., there exists an efficiently computable function that in some sense enumerates the elements of the group). Two specific instances are presented. The techniques used to design the instances, for example, the new probabilistic randomness extractor are of independent interest for other applications.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: Pseudorandom generator DDH problem concrete security
Contact author(s): a sidorenko @ tue nl
History: 2006-11-07: revised; 2006-09-26: received; See all versions
Short URL: https://ia.cr/2006/321
License: CC BY

BibTeX

@misc{cryptoeprint:2006/321,
      author = {Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko},
      title = {Efficient Pseudorandom Generators Based on the DDH Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2006/321},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/321}},
      url = {https://eprint.iacr.org/2006/321}
}