Cameron Foreman

Achieving computational advantage using NISQ devices on practically useful problems is a long standing challenge. We report two papers that experimentally demonstrate a concrete application, namely certified randomness generation, which could be useful for multi-party cryptographic protocols and improving imperfect physical sources of randomness. Both papers involve substantial theoretical contributions to the protocol. We devise a realistic protocol that maximizes practical hardness. The verifier first asks the server to prepare a quantum state using a random circuit and then sends a random measurement basis right before the result must be received. This is repeated for many rounds. We show complexity theoretic evidence for entropy generation and provide improved entropy bounds against adversaries with oracle access to the random circuits. We also construct an end-to-end application of randomness amplification of imperfect sources into nearly perfect randomness, notably achieving everlasting security which uplifts computational security to information theoretic security.

We prove that binary linear error correcting codes (ECCs) can act as deterministic extractors in a randomness expansion protocol, achieving rates comparable to existing seeded extractors. In addition to reducing the initial randomness consumed, the computational cost of implementing some binary linear ECCs is significantly lower in terms of both computation time and memory size.

Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. An essential step in DI protocols is randomness extraction (or privacy amplification) which requires the honest parties to have a seed of additional bits with sufficient entropy and statistical independence of any bits generated during the protocol. In this work we introduce a method for extraction in DI protocols which does not require a seed and is secure against computationally unbounded quantum adversary. The key idea is to use the Bell violation of the raw data, instead of its min-entropy, as the extractor promise.

Randomness extractors are an essential component in numerous applications, for example, for privacy amplification in quantum key distribution and randomness extraction in random number generation. Despite their importance, selecting, optimising and implementing the appropriate extractor and parameters requires significant expertise and time investment. We present Cryptomite, a publicly available software library that provides a variety of two-source, seeded, and deterministic randomness extractor implementations with state-of-the-art performance. The software is efficient, numerically precise and capable of handling input sizes up to $10^{12}$, allowing for use even in resource intensive protocols, e.g. device-independent ones. Alongside the software, we provide theoretical contributions that include improvements and generalisations to existing extractors, new extractor constructions and parameter calculation in a variety of useful security models. To showcase the library, we empirically compare the properties of the output of several random number generators and the effect of different randomness extraction methods on it, using intense statistical testing.