On the Multidimensional Distribution of the Naor--Reingold Pseudo-Random Function

We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive and useful property. Namely, it is proved that for almost all values of parameters it produces a uniformly distributed sequence. The proof is based on some recent bounds...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of computation 2014-09, Vol.83 (289), p.2429-2434
Main Authors: LING, SAN, SHPARLINSKI, IGOR, WANG, HUAXIONG
Format: Article
Language:English
Subjects:
Cauchy Schwarz inequality
Exponential functions
Integers
Mathematical functions
Mathematical sequences
Mathematical vectors
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive and useful property. Namely, it is proved that for almost all values of parameters it produces a uniformly distributed sequence. The proof is based on some recent bounds of character sums with exponential functions.
ISSN:0025-5718
1088-6842
DOI:10.1090/S0025-5718-2014-02794-4