← Back to projects

Quantum Computing and Cryptography

Project overview

The era of scalable quantum computing is upon us. With recent, exciting, advances in quantum computing architectures, quantum error-correction and quantum fault-tolerance, we are making rapid progress towards a world where there are scalable quantum computers that can solve classically intractable problems (a world of ``quantum supremacy'' or more modestly, ``quantum advantage''). A world where large-scale quantum computers exist is deeply consequential to the very possibility of a secure and trustworthy cyberspace, largely due to the groundbreaking work of Shor who showed how to factor and compute discrete logarithms in quantum polynomial time, thereby breaking public-key cryptosystems that form the foundations of secure communication today. The focus of our research is to investigate the foundations of cryptography in this quantum world.

We consider three possible worlds where large-scale quantum computers exist: In PostQuant, our adversaries may have scalable quantum computers that help them break cryptosystems. In MiniQuant, large organizations such as Google, IBM and Microsoft have scalable quantum computing capabilities that users can ``rent'' them, much like the cloud computing architectures of today. In Omniquant, users have at their disposal commodity quantum computing machines perform interesting, classically infeasible, computations.

We develop cryptographic algorithms that cater to all these worlds. In PostQuant, we explore improved quantum algorithms as well as methods of achieving security despite the existence of such powerful adversaries. We study and diversify cryptographic assumptions, constructions and proof techniques that deliver post-quantum security. In MiniQuant, we develop techniques to protect the privacy and integrity of computations by designing blind and verifiable delegated computation protocols. In OmniQuant, we come up with novel instantiations of quantum cryptographic protocols such as quantum money schemes, as well as entirely new capabilities such as quantum program obfuscation and quantum one-time programs.

Publications