Divide and Conquer Modification of the Blum-Micali Pseudorandom Number Generator
Abstract
The Blum-Micali pseudorandom number generator (PRNG) outputs cryptographically secure sequences of pseudorandom bits. One of the primary drawbacks of the Blum-Micali PRNG is that it can be computationally expensive and slow to run. This thesis proposes a modification to the Blum-Micali PRNG that allows for more pseudorandom bits to be extracted per iteration of the algorithm while retaining cryptographic security. We use the National Institute of Standards and Technology (NIST) Statistical Test Suite for PRNGs to evaluate the performance of sequences produced using this modification. In addition we compare the computational run time of our modification with that of the original Blum-Micali PRNG. Previous research indicates that there is an upper limit on the number of bits that may be extracted periteration while retaining cryptographic security. Our test data suggest that our modification to the Blum-Micali PRNG performs just as well as the original version when extracting up to 11 bits per iteration. Furthermore, our data suggest that our modification can speed up computational run times in direct proportion to the number of bits extracted per iteration. We consider additional possible extensions that could further increase the speed of computation while still retaining randomness and cryptographic security.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2023
- Accession Number
- AD1213282
Entities
People
- Daniel K. Gillespie
Organizations
- Naval Postgraduate School