Provably secure and efficient pseudorandom number generation

摘要

A pseudorandom number is generated from a random seed number using a collision-resistant hash function. A iteration input is extracted from the seed number. A hardcore predicate is applied to the iteration input to generate a pseudorandom bit. A pairwise-independent function is identified using a pairwise-independent function identifier extracted from the seed number and applied to the iteration input to produce a randomized iteration input. The collision-resistant hash function is applied to the randomized iteration input to produce a hash result and pad the output. The padded hash result is assigned as the iteration input for the next iteration. The process repeats iteratively and pseudorandom bits are generated using the hardcore predicate in each iteration until a predetermined number of pseudorandom bits are generated. The pseudorandom number is constructed using the generated pseudorandom bits.

主权项

1. A computer-implemented method for generating a pseudorandom number, comprising:
using a computer to perform steps comprising:
determining a seed number;determining an iteration input based on an iteration input portion of the seed number;applying a hardcore predicate to the iteration input to generate a pseudorandom bit;applying a cryptographic collision-resistant hash function to the iteration input to generate a hash result;assigning the hash result as the iteration input for a next iteration;constructing a pseudorandom number based on the pseudorandom bit; andoutputting the pseudorandom number.