Randomness in Cryptography: Theory Meets Practice

Daniel Hutchinson

Research output: ThesisDoctoral Thesis

134 Downloads (Pure)

Abstract

Randomness is a key ingredient in every area of cryptography; and as the quote
goes, producing it should not be left to chance. Unfortunately it's very dicult
to produce true randomness, and consuming applications often call for large, high quality amounts on boot or in quick succession. To meet this requirement we make use of Pseudo-Random Number Generators (PRNGs) which we initialise with a small amount of randomness to produce what we hope to be high quality pseudo-random output.

In this thesis we investigate some of the different security models associated with capturing what makes a good" PRNG, along with the problem of constructing a secure PRNG by adapting primitives available. We focus mainly on the sponge construction, noting that the original formulation does not lend itself well to a secure PRNG but with some adjustment can be made into a robust and secure PRNG. This is done by utilising a feed-forward of the inner, secure part of the sponge state, which establishes an efficient forward security mechanism.

We then present an updated security model for PRNGs designed to capture variable output subroutines present in some PRNGs where an adversary is allowed to request differing amounts of output with each call to the PRNG. We maintain the ability to prove robustness via two simpler security notions which are now extended to variable-output versions.

We then follow with an analysis of the NIST PRNGs in this new security model,
which served as motivation for updating the security model. We show that under
certain assumptions the NIST generators do satisfy security in this model.
Original languageEnglish
QualificationPh.D.
Awarding Institution
  • Royal Holloway, University of London
Supervisors/Advisors
  • Paterson, Kenneth, Supervisor
Award date1 Mar 2019
Publication statusUnpublished - 23 Feb 2019

Cite this