A note on local randomness in polynomial random number and random function generators

作者:

Highlights:

摘要

A n-bit string is said to be (ϵ, e)-locally random, if for every choice of e ⩽ n positions the induced distribution on e-bit strings is in the L1-norm at most ϵ away from the uniform distribution on e-bit strings. Niederreiter and Schnorr [H. Niederreiter, C.P. Schnorr, Local randomness in polynomial random number and random function generators, SIAM Journal on Computing 22 (1993) 684–694] established local randomness in polynomial random number generators (RNG) and local randomness in families of cryptographic hash functions. However, their polynomial random functions must be linearly independent. In this paper, we shall give new families of cryptographic hash functions, which do not require linear independence. Local randomness of our functions is studied.

论文关键词:Local randomness,Hash functions,Random function generator,Discrepancy

论文评审过程:Available online 2 October 2006.

论文官网地址:https://doi.org/10.1016/j.amc.2006.07.159