Quantum Computing for Modern Cryptography (QCMC)
Quantum Computing for Modern Cryptography (QCMC)
Introduction
The development of quantum computers brings new, in some cases unprecedented, computational capabilities. The security of most of cryptographic applications, from simple encryption and authentication to involved functionalities such as auctions or e-voting, relies on certain assumptions about which problems are easy (can be solved quickly) and which problems are hard (require long time). It follows that the security of all these applications will need to be revisited in the light of the new capabilities that quantum computers bring.
In this project we examine the effects of quantum computers on modern cryptography, focusing on three problems: First, we analyse the consequences that quantum algorithms, used by honest and dishonest parties, bring to the security of Bitcoin and other “proof-of-work” blockchains. Second, we analyse how the security definitions and existing constructions change for another modern cryptographic application, the functional encryption. This application essentially enables a central party to grant access to sensitive (e.g. medical) data to clients in a way that they cannot obtain any information about the sensitive data (medical history of patients) beyond the property/function that they are authorised. Third, we re-examine the capabilities of near-term quantum computers in factoring – a crucial problem for cryptography. While it is known that large fault-tolerant quantum computers (likely to be developed in the next decades) will be able to solve these problems efficiently, we examine what imperfect quantum computers will be able to offer in the next couple of years. This is crucial for the confirming or questioning the security of many currently used cryptosystems in the imminent future.
Objectives and impact
The main objective is to understand and evaluate the capabilities that near-term and “long-term” quantum computers bring with respect to the security of modern cryptographic tasks. Concretely, objective 1 is to evaluate the security of bitcoin and other similar blockchain technologies in the presence of miners with quantum computers, objective 2 is to formally define and analyse the security of functional encryption in the quantum setting and objective 3 is to evaluate the capabilities of near-term quantum algorithms in breaking widely used cryptosystems.
The impact of this research is magnified by the great promise (and great revenue) that these new technologies (blockchain, functional encryption) bring and by the fact that central to the adaptation of these technologies is the confidence in the security guarantees they provide.
Applicants:
Dr Petros Wallden
School of Informatics
University of Edinburgh
Prof Aggelos Kiayias
School of Informatics
University of Edinburgh
