Non-linear complexity of the naor-reingold pseudo-random function

William D. Banks; Frances Griffin; Daniel Lieman; Igor E. Shparlinski

doi:10.1007/10719994_5

Non-linear complexity of the naor-reingold pseudo-random function

William D. Banks, Frances Griffin, Daniel Lieman, Igor E. Shparlinski

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

7 Citations (Scopus)

Abstract

We obtain an exponential lower bound on the non-linear complexity of the new pseudo-random function, introduced recently by M. Naor and O. Reingold. This bound is an extension of the lower bound on the linear complexity of this function that has been obtained by F. Griffin and I. E. Shparlinski.

Original language	English
Title of host publication	Information Security and Cryptology - ICISC '99
Subtitle of host publication	Second International Conference Seoul, Korea, December 1999 Proceedings
Editors	JooSeok Song
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	53-59
Number of pages	7
Volume	1787
ISBN (Print)	3540673806
DOIs	https://doi.org/10.1007/10719994_5
Publication status	Published - 2000
Event	2nd International Conference on Information Security and Cryptology, ICISC 1999 - Seoul, Korea, Republic of Duration: 9 Dec 1999 → 10 Dec 1999

Publication series

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

Other

Other	2nd International Conference on Information Security and Cryptology, ICISC 1999
Country/Territory	Korea, Republic of
City	Seoul
Period	9/12/99 → 10/12/99

Access to Document

10.1007/10719994_5

Cite this

Banks, W. D., Griffin, F., Lieman, D., & Shparlinski, I. E. (2000). Non-linear complexity of the naor-reingold pseudo-random function. In J. Song (Ed.), Information Security and Cryptology - ICISC '99 : Second International Conference Seoul, Korea, December 1999 Proceedings (Vol. 1787, pp. 53-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1787). Springer, Springer Nature. https://doi.org/10.1007/10719994_5

Banks, William D. ; Griffin, Frances ; Lieman, Daniel et al. / Non-linear complexity of the naor-reingold pseudo-random function. Information Security and Cryptology - ICISC '99 : Second International Conference Seoul, Korea, December 1999 Proceedings. editor / JooSeok Song. Vol. 1787 Berlin : Springer, Springer Nature, 2000. pp. 53-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2baa1be58c8d4c4ca0c87b90195c3a95,

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

abstract = "We obtain an exponential lower bound on the non-linear complexity of the new pseudo-random function, introduced recently by M. Naor and O. Reingold. This bound is an extension of the lower bound on the linear complexity of this function that has been obtained by F. Griffin and I. E. Shparlinski.",

author = "Banks, {William D.} and Frances Griffin and Daniel Lieman and Shparlinski, {Igor E.}",

year = "2000",

doi = "10.1007/10719994_5",

language = "English",

isbn = "3540673806",

volume = "1787",

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

publisher = "Springer, Springer Nature",

pages = "53--59",

editor = "JooSeok Song",

booktitle = "Information Security and Cryptology - ICISC '99",

address = "United States",

note = "2nd International Conference on Information Security and Cryptology, ICISC 1999 ; Conference date: 09-12-1999 Through 10-12-1999",

}

Banks, WD, Griffin, F, Lieman, D & Shparlinski, IE 2000, Non-linear complexity of the naor-reingold pseudo-random function. in J Song (ed.), Information Security and Cryptology - ICISC '99 : Second International Conference Seoul, Korea, December 1999 Proceedings. vol. 1787, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1787, Springer, Springer Nature, Berlin, pp. 53-59, 2nd International Conference on Information Security and Cryptology, ICISC 1999, Seoul, Korea, Republic of, 9/12/99. https://doi.org/10.1007/10719994_5

Non-linear complexity of the naor-reingold pseudo-random function. / Banks, William D.; Griffin, Frances; Lieman, Daniel et al.
Information Security and Cryptology - ICISC '99 : Second International Conference Seoul, Korea, December 1999 Proceedings. ed. / JooSeok Song. Vol. 1787 Berlin: Springer, Springer Nature, 2000. p. 53-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1787).

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

TY - GEN

T1 - Non-linear complexity of the naor-reingold pseudo-random function

AU - Banks, William D.

AU - Griffin, Frances

AU - Lieman, Daniel

AU - Shparlinski, Igor E.

PY - 2000

Y1 - 2000

N2 - We obtain an exponential lower bound on the non-linear complexity of the new pseudo-random function, introduced recently by M. Naor and O. Reingold. This bound is an extension of the lower bound on the linear complexity of this function that has been obtained by F. Griffin and I. E. Shparlinski.

AB - We obtain an exponential lower bound on the non-linear complexity of the new pseudo-random function, introduced recently by M. Naor and O. Reingold. This bound is an extension of the lower bound on the linear complexity of this function that has been obtained by F. Griffin and I. E. Shparlinski.

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

U2 - 10.1007/10719994_5

DO - 10.1007/10719994_5

M3 - Conference proceeding contribution

AN - SCOPUS:84958770143

SN - 3540673806

VL - 1787

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

SP - 53

EP - 59

BT - Information Security and Cryptology - ICISC '99

A2 - Song, JooSeok

PB - Springer, Springer Nature

CY - Berlin

T2 - 2nd International Conference on Information Security and Cryptology, ICISC 1999

Y2 - 9 December 1999 through 10 December 1999

ER -

Banks WD, Griffin F, Lieman D, Shparlinski IE. Non-linear complexity of the naor-reingold pseudo-random function. In Song J, editor, Information Security and Cryptology - ICISC '99 : Second International Conference Seoul, Korea, December 1999 Proceedings. Vol. 1787. Berlin: Springer, Springer Nature. 2000. p. 53-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/10719994_5

Non-linear complexity of the naor-reingold pseudo-random function

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this