Oxford Mathematician Ali El Kaafarani explains how mathematics is tackling the issue of post-quantum digital security.
"Quantum computers are on their way to us, not from a galaxy far far away; they are literally right across the road from us in the Physics Department of Oxford University.
All cryptosystems currently used to provide confidentiality/authenticity/privacy rely on the hardness of number-theoretic assumptions, i.e., the integer factorization or discrete logarithm problems. And all was good until a well-known quantum attack, Shor’s algorithm, proved that both these problems can be solved efficiently; this means that once a scalable fault-tolerant quantum computer comes to life, our current cryptosystems become obsolete, and online transactions are deemed completely unsafe.
Cryptographers are currently preparing for that world, which they refer to as the "post-quantum era." Here in Oxford Mathematics, and in collaboration with TU Darmstadt and the University of Tokyo, we are developing post-quantum secure cryptosystems that mainly focus on enhancing and protecting the user's privacy.
At the heart of those cryptosystems is the so-called notion of anonymous digital signatures, which are an authentication method that reveals only the necessary information about the signer, be it a client at a pharmacy who doesn’t want to reveal why he/she doesn’t pay for prescriptions or a machine that wants to prove that it has the right system configuration while communicating with other machines without revealing any further details about itself ; or Internet users who want to stay anonymous while reviewing/rating products.
Those cryptosystems are based on lattices1 which are known to be the most promising quantum-resistant alternative to the number theoretic assumptions in use today. Lattices, those beautiful mathematical objects have come to save the day; they are rich with various sorts of computationally hard problems, namely, worst-case problems (e.g. Shortest Vector Problem), average-case problems (e.g. Short Integer Solution (SIS)2, Learning With Errors (LWE)3 ), and most importantly, the relationship between them. Such complexity is what we will need in the future."
The Public Key Cryptography 2018 and The Financial Cryptography and Data Security 2018 Conferences will feature some of this work.
- An $n$ -dimensional lattice is a (full-rank) discrete additive subgroup of $\mathbb{R}^n$ .
- The $\mathsf{SIS}_{n,q,\beta,m}$ problem: given a uniformly random matrix $\textbf{A}\in\mathbb{Z}_q^{n\times m}$ , find a non-zero vector $\textbf{z}\in\mathbb{Z}^m$ of norm bounded by $\beta$ such that $\textbf{A} \textbf{z} = \textbf{0} \in \mathbb{Z}_q^n$ .
- At a high level, given a set of "noisy/approximate" linear equations in (a secret) $s\in\mathbb{Z}_q^n$ , the (search) $\mathsf{LWE}$ problem asks to recover $s$.