On the multidimensional distribution of the Naor-Reingold pseudo-random function

San Ling; Igor Shparlinski; Huaxiong Wang

doi:10.1090/S0025-5718-2014-02794-4

On the multidimensional distribution of the Naor-Reingold pseudo-random function

San Ling, Igor Shparlinski, Huaxiong Wang

School of Computing

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

56 Downloads (Pure)

Abstract

We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive anduseful property. Namely, it is proved that for almost all values of parameters itproduces a uniformly distributed sequence. The proof is based on some recentbounds of character sums with exponential functions.

Original language	English
Pages (from-to)	2429-2434
Number of pages	6
Journal	Mathematics of Computation
Volume	83
Issue number	289
DOIs	https://doi.org/10.1090/S0025-5718-2014-02794-4
Publication status	Published - 2014

Bibliographical note

Copyright 2014 American Mathematical Society. First published in Mathematics of computation, vol. 83, no. 289, published by the American Mathematical Society. The original article can be found at http://doi.org/10.1090/S0025-5718-2014-02794-4

Keywords

Discrepancy
Exponential sums
Naor-Reingold pseudo-random function

Access to Document

10.1090/S0025-5718-2014-02794-4

Publisher version (open access)Final published version, 159 KB

Cite this

@article{68c23d9fb71a44f49f3aa1cf956f7ab1,

title = "On the multidimensional distribution of the Naor-Reingold pseudo-random function",

abstract = "We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive anduseful property. Namely, it is proved that for almost all values of parameters itproduces a uniformly distributed sequence. The proof is based on some recentbounds of character sums with exponential functions.",

keywords = "Discrepancy, Exponential sums, Naor-Reingold pseudo-random function",

author = "San Ling and Igor Shparlinski and Huaxiong Wang",

note = "Copyright 2014 American Mathematical Society. First published in Mathematics of computation, vol. 83, no. 289, published by the American Mathematical Society. The original article can be found at http://doi.org/10.1090/S0025-5718-2014-02794-4",

year = "2014",

doi = "10.1090/S0025-5718-2014-02794-4",

language = "English",

volume = "83",

pages = "2429--2434",

journal = "Mathematics of Computation",

issn = "0025-5718",

publisher = "AMER MATHEMATICAL SOC",

number = "289",

}

TY - JOUR

T1 - On the multidimensional distribution of the Naor-Reingold pseudo-random function

AU - Ling, San

AU - Shparlinski, Igor

AU - Wang, Huaxiong

N1 - Copyright 2014 American Mathematical Society. First published in Mathematics of computation, vol. 83, no. 289, published by the American Mathematical Society. The original article can be found at http://doi.org/10.1090/S0025-5718-2014-02794-4

PY - 2014

Y1 - 2014

N2 - We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive anduseful property. Namely, it is proved that for almost all values of parameters itproduces a uniformly distributed sequence. The proof is based on some recentbounds of character sums with exponential functions.

AB - We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive anduseful property. Namely, it is proved that for almost all values of parameters itproduces a uniformly distributed sequence. The proof is based on some recentbounds of character sums with exponential functions.

KW - Discrepancy

KW - Exponential sums

KW - Naor-Reingold pseudo-random function

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

UR - http://purl.org/au-research/grants/arc/DP1092835

U2 - 10.1090/S0025-5718-2014-02794-4

DO - 10.1090/S0025-5718-2014-02794-4

M3 - Article

AN - SCOPUS:84909990950

SN - 0025-5718

VL - 83

SP - 2429

EP - 2434

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 289

ER -

On the multidimensional distribution of the Naor-Reingold pseudo-random function

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Mathematics of Cryptography

Cite this

On the multidimensional distribution of the Naor-Reingold pseudo-random function

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Mathematics of Cryptography

Cite this