Omar Amer

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.

Client authentication (CA) is a cryptographic protocol where a server tries to validate the identity of a client. Fehr et. al. proposed a CA protocol with pre-shared basis information between the client and server which has a nice key recycling property, where secrets including the pre-shared basis can be securely reused after each successful round. We extend the protocol to a practical setting by including decoy state and error correction, but the leakage of pre-shared basis information via multi-photon events limits the performance of such a protocol. As such, we propose the use of a pseudorandom number generator (PRNG), assumed to be secure only during each run of the protocol, to perform basis selection to reduce information leakage. A formal proof of the protocol security is provided by modifying the entropic uncertainty relation to account for basis generated by a PRNG, which could be of independent interest as it may be applicable to other protocols such as quantum key distribution. An experimental implementation of the protocol, with appropriate post-selection, was performed to demonstrate its feasibility. We also designed a CA protocol secure in the practical setting with only two rounds of communication: a challenge by the server and a response by the client.

There are two critical challenges that must be addressed for Quantum Key Distribution (QKD) to achieve wide-scale adoption. First, overcoming distance limitations and second increasing secret key generation rates. Our work investigates the design of novel routing algorithms for near-future QKD networks to help mitigate these problems. The networks we consider also may serve as a bridge between today's QKD networks and the long-term goal of a true Quantum Internet.