On the linear complexity of the naor—reingold pseudo-random function

Frances Griffin; Igor E. Shparlinski

doi:10.1007/978-3-540-47942-0_25

On the linear complexity of the naor—reingold pseudo-random function

Frances Griffin, Igor E. Shparlinski

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

10 Citations (Scopus)

Abstract

We show that the new pseudo-random function, introduced recently by M. Naor and O. Reingold, possesses one more attractive and useful property. Namely, it is proved that, under a certain not too restrictive condition on the parameters of this function, for almost all seeds it produces a sequence with exponentially large linear complexity.

Original language	English
Title of host publication	Information and Communication Security
Subtitle of host publication	Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings
Editors	Vijay Varadharajan, Yi Mu
Place of Publication	Berlin; New York
Publisher	Springer, Springer Nature
Pages	301-308
Number of pages	8
ISBN (Electronic)	9783540479420
ISBN (Print)	3540666826, 9783540666820
DOIs	https://doi.org/10.1007/978-3-540-47942-0_25
Publication status	Published - Nov 1999
Event	2nd International Conference on Information and Communication Security, ICICS - 1999 - Sydney, Australia Duration: 9 Nov 1999 → 11 Nov 1999

Publication series

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

Other

Other	2nd International Conference on Information and Communication Security, ICICS - 1999
Country/Territory	Australia
City	Sydney
Period	9/11/99 → 11/11/99

Access to Document

10.1007/978-3-540-47942-0_25

Cite this

Griffin, F., & Shparlinski, I. E. (1999). On the linear complexity of the naor—reingold pseudo-random function. In V. Varadharajan, & Y. Mu (Eds.), Information and Communication Security: Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings (pp. 301-308). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1726). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-47942-0_25

Griffin, Frances ; Shparlinski, Igor E. / On the linear complexity of the naor—reingold pseudo-random function. Information and Communication Security: Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings. editor / Vijay Varadharajan ; Yi Mu. Berlin; New York : Springer, Springer Nature, 1999. pp. 301-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a9fc3a526e4346189dea68eaa4bda305,

title = "On the linear complexity of the naor—reingold pseudo-random function",

abstract = "We show that the new pseudo-random function, introduced recently by M. Naor and O. Reingold, possesses one more attractive and useful property. Namely, it is proved that, under a certain not too restrictive condition on the parameters of this function, for almost all seeds it produces a sequence with exponentially large linear complexity.",

author = "Frances Griffin and Shparlinski, {Igor E.}",

year = "1999",

month = nov,

doi = "10.1007/978-3-540-47942-0_25",

language = "English",

isbn = "3540666826",

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

publisher = "Springer, Springer Nature",

pages = "301--308",

editor = "Vijay Varadharajan and Yi Mu",

booktitle = "Information and Communication Security",

address = "United States",

note = "2nd International Conference on Information and Communication Security, ICICS - 1999 ; Conference date: 09-11-1999 Through 11-11-1999",

}

Griffin, F & Shparlinski, IE 1999, On the linear complexity of the naor—reingold pseudo-random function. in V Varadharajan & Y Mu (eds), Information and Communication Security: Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1726, Springer, Springer Nature, Berlin; New York, pp. 301-308, 2nd International Conference on Information and Communication Security, ICICS - 1999, Sydney, New South Wales, Australia, 9/11/99. https://doi.org/10.1007/978-3-540-47942-0_25

On the linear complexity of the naor—reingold pseudo-random function. / Griffin, Frances; Shparlinski, Igor E.
Information and Communication Security: Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings. ed. / Vijay Varadharajan; Yi Mu. Berlin; New York: Springer, Springer Nature, 1999. p. 301-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1726).

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

TY - GEN

T1 - On the linear complexity of the naor—reingold pseudo-random function

AU - Griffin, Frances

AU - Shparlinski, Igor E.

PY - 1999/11

Y1 - 1999/11

N2 - We show that the new pseudo-random function, introduced recently by M. Naor and O. Reingold, possesses one more attractive and useful property. Namely, it is proved that, under a certain not too restrictive condition on the parameters of this function, for almost all seeds it produces a sequence with exponentially large linear complexity.

AB - We show that the new pseudo-random function, introduced recently by M. Naor and O. Reingold, possesses one more attractive and useful property. Namely, it is proved that, under a certain not too restrictive condition on the parameters of this function, for almost all seeds it produces a sequence with exponentially large linear complexity.

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

U2 - 10.1007/978-3-540-47942-0_25

DO - 10.1007/978-3-540-47942-0_25

M3 - Conference proceeding contribution

AN - SCOPUS:0007057181

SN - 3540666826

SN - 9783540666820

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

SP - 301

EP - 308

BT - Information and Communication Security

A2 - Varadharajan, Vijay

A2 - Mu, Yi

PB - Springer, Springer Nature

CY - Berlin; New York

T2 - 2nd International Conference on Information and Communication Security, ICICS - 1999

Y2 - 9 November 1999 through 11 November 1999

ER -

Griffin F, Shparlinski IE. On the linear complexity of the naor—reingold pseudo-random function. In Varadharajan V, Mu Y, editors, Information and Communication Security: Second International Conference, ICICS’99, Sydney, Australia, November 9-11, 1999. Proceedings. Berlin; New York: Springer, Springer Nature. 1999. p. 301-308. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-47942-0_25

On the linear complexity of the naor—reingold pseudo-random function

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this