Efficient pseudorandom generators based on the DDH assumption

Reza Rezaeian Farashahi; Berry Schoenmakers; Andrey Sidorenko

Efficient pseudorandom generators based on the DDH assumption

Reza Rezaeian Farashahi^*, Berry Schoenmakers, Andrey Sidorenko

^*Corresponding author for this work

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

30 Citations (Scopus)

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.

Original language	English
Title of host publication	Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
Editors	Tatsuaki Okamoto, Xiaoyun Wang
Pages	426-441
Number of pages	16
Volume	4450 LNCS
Publication status	Published - 2007
Event	10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007 - Beijing, China Duration: 16 Apr 2007 → 20 Apr 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4450 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007
Country	China
City	Beijing
Period	16/04/07 → 20/04/07

Access to Document

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Efficient pseudorandom generators based on the DDH assumption'. Together they form a unique fingerprint.

Cite this

Farashahi, R. R., Schoenmakers, B., & Sidorenko, A. (2007). Efficient pseudorandom generators based on the DDH assumption. In T. Okamoto, & X. Wang (Eds.), Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings (Vol. 4450 LNCS, pp. 426-441). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4450 LNCS).

Farashahi, Reza Rezaeian ; Schoenmakers, Berry ; Sidorenko, Andrey. / Efficient pseudorandom generators based on the DDH assumption. Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. editor / Tatsuaki Okamoto ; Xiaoyun Wang. Vol. 4450 LNCS 2007. pp. 426-441 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{39e2ffd2dd9b4f30ae99a101a9fc0d50,

title = "Efficient pseudorandom generators based on the DDH assumption",

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.",

author = "Farashahi, {Reza Rezaeian} and Berry Schoenmakers and Andrey Sidorenko",

year = "2007",

language = "English",

isbn = "9783540716761",

volume = "4450 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "426--441",

editor = "Tatsuaki Okamoto and Xiaoyun Wang",

booktitle = "Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings",

note = "10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007 ; Conference date: 16-04-2007 Through 20-04-2007",

}

Farashahi, RR, Schoenmakers, B & Sidorenko, A 2007, Efficient pseudorandom generators based on the DDH assumption. in T Okamoto & X Wang (eds), Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. vol. 4450 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4450 LNCS, pp. 426-441, 10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007, Beijing, China, 16/04/07.

Efficient pseudorandom generators based on the DDH assumption. / Farashahi, Reza Rezaeian; Schoenmakers, Berry; Sidorenko, Andrey.

Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. ed. / Tatsuaki Okamoto; Xiaoyun Wang. Vol. 4450 LNCS 2007. p. 426-441 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4450 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Efficient pseudorandom generators based on the DDH assumption

AU - Farashahi, Reza Rezaeian

AU - Schoenmakers, Berry

AU - Sidorenko, Andrey

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38049035823&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:38049035823

SN - 9783540716761

VL - 4450 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 426

EP - 441

BT - Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings

A2 - Okamoto, Tatsuaki

A2 - Wang, Xiaoyun

T2 - 10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007

Y2 - 16 April 2007 through 20 April 2007

ER -

Farashahi RR, Schoenmakers B, Sidorenko A. Efficient pseudorandom generators based on the DDH assumption. In Okamoto T, Wang X, editors, Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Vol. 4450 LNCS. 2007. p. 426-441. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).