Even though we have some basic understanding of the power of quantum computation, and its impact on cryptography and cryptanalysis, there are many open problems, some of them purely technical and some more fundamental. During our residency at STIAS we propose to investigate the weakness of the existing cryptographic schemes and propose some counter-measures. Our investigations and discussions will be structured around the following three main themes;
- Quantum Algorithms. In order to make a reasonable assessment of the risk posed by quantum technology we will look into quantum algorithms that can impact cryptanalysis. These will involve variants of Shor’s factoring and discrete log algorithms, different versions of Grover’s search algorithm and attempts to design a quantum algorithm that may challenge the integrity of the lattice based cryptography.
- Quantum Cryptography. We shall investigate the physical limits of privacy offered by quantum theory, including device independent key distribution, randomness amplification and expansion, and some aspects of blind quantum computation that may be relevant to designing a quantum homomorphic encryption.
- Quantum Resistant Cryptography. It is still an open question which particular mathematical problems will be most suitable for designing public key cryptosystems that will be resistant to quantum attacks. The candidates range from problems involving vectors in lattices to arithmetic modulo Mersenne numbers. The latter has been proposed by Miklos Santha and Antoine Joux, and we plant to discuss its comparative advantages.
In particular, as an overarching theme, we will analyse quantum attacks that can disrupt the existing cryptocurrencies, e.g. bitcoins, and the underlying blockchain protocols. We plan to organise a small workshop, half-way into the programme, to which will also invite the leading experimentalists in quantum computation and quantum cryptography. This will allow to form a more comprehensive picture of the current state of the art in quantum technologies and the anticipated impact of data security.