Cryptography is a cornerstone of information security. It is used to
encode and decode data in order to fulfill the requirement for confidentiality, integrity, authenticity as
well as non-repudiation. Together,
these are frequently referred to as cryptography services.
Advances in cryptanalysis, computer science and engineering are always
pushing the limits of what is considered secure. RSA, which once was believed secure under 129 bit-keys, nowadays is not considered secure
using keys smaller than 2,048 bits. MD5, which was designed in 1992 and had
been one of the most widely used hash functions, was proven to be breakable (in the sense of collision-attack) in 2004. Likewise, freestart collision against SHA-1, which is somewhat easier to find than
standard collisions, was demonstrated and
published at Eurocrypt 2016.
One of the resources in the toolkit of cryptanalysts is quantum computing. Quantum computing is based on physical
quantum properties to perform operations, which behaves differently than the
electronic properties we are used to find in today’s computers and its basic
unit of information, instead of bit, is called quantum bit or qubit. It started to be used in theoretical attacks against
cryptosystems back in 1994, when Peter Shor published a quantum algorithm to
find the prime factors of a given integer. This algorithm enables the solving
of integer factorization and discrete logarithm problems, which are the basis
of most (not to say all) widely used public-key cryptography algorithms. Less
devastating in its impact but still of major importance, Grover’s quantum
algorithm enables a huge speedup in search algorithms that impacts the security
of many cryptosystems, including AES. This leads us to make a fairly surprising
statement: all major cryptographic algorithms in use today are (virtually)
broken!
Today, the only mitigating factor is the absence of a quantum computer
large enough to run such algorithms against the parameters currently in use by crypto
algorithms.
In the landscape of quantum computing everything is evolving fast. In
April 2016, the European Commission announced plans to invest one billion euros
in an EU project for a “large-scale EU-wide quantum technologies flagship”. As with
this program, many others have been launched to fund the development of
large-scale quantum computers.
Also in April 2016, researchers in Canada established a new record in
quantum computer factorization, after factoring the number 200,099 using a D-Wave 2X processor, although it is not clear whether
D-WAVE produces universal quantum computers able to
run the Shor’s algorithm. Furthermore, 200,099 is only an 18-bit number, way too small to need
the computation power required to factor a 2,048-bit integer to break current RSA
parameters.
The current stage of large-scale deployment of public key cryptosystems
counts on pretty elderly algorithms like Diffie-Hellman
(1976), RSA (1977) and Elliptic Curves (1985). The latter was
first published more than 30 years ago, but has recently started to be deployed on a large
scale.
To tackle the cryptography Armageddon imposed by
large-scale quantum computers, cryptographers around the world have been
working for at least a decade to design and improve cryptosystems resistant to
quantum attacks, known as post-quantum cryptography
or PQCrypto. Many cryptosystems have been
designed and even standardized, like NTRU, nonetheless confidence in such new
cryptosystems takes time to earn by being thoroughly scrutinized over and over
again until they are proven to be ready for large-scale deployment.
What is the current state of PQCrypto?
In 2006 the first PQCrypto Conference was hosted, bringing together
researchers to look for secure alternatives against quantum computing attacks. At
the time, some alternatives were already at hand, such as McEliece encryption (1978), and ever since many programs
to fund research in PQCrypto have been launched, such as European Commission’s SAFECrypto, a program for the development of quantum-resistant
lattice-based cryptography, or CryptoWorks21, a Canadian program to develop next-generation quantum-safe
cryptographic tools for the 21st century. The outcome of all these efforts
towards PQCrypto is a huge advance in the field that has already provided post-quantum
candidates that meet all desired features of like efficiency and key-size
comparable to classic algorithms.
PQCrypto does not entail any special hardware. It is like classic
crypto, but built on problems that are infeasible even for large quantum
computers. PQCrypto algorithms have been designed to fulfill the services
provided by classic crypto and many of them are able to run even on the most limited
platforms.
How will PQCrypto evolve?
Even in a quantum world, current security protocols will continue to be
as secure as they are today if their design assumptions are fulfilled using
post-quantum cryptosystems. Thus, we should see a gradual adoption of modern
PQCrypto algorithms by existing protocols over the coming years.
We should see a decline in the use of public-key algorithms most used
nowadays, such as RSA and Elliptic Curves; in the cases like symmetric crypto
and hash functions, the current parameters will have to be revisited (usually
doubled) to ensure that they stay secure in a quantum world. This shift to
modern algorithms should happen transparently to end users; however, whoever is
responsible for development or configuration of security applications should be
ready for the coming changes – in particular, those who support these
functionalities in legacy systems.
By way of speculating on how long it will take until large quantum
computers are able to perform attacks on cryptosystems set with today’s parameters,
let’s assume that Moore’s law will be valid throughout the development of
quantum computation. Shor’s algorithm requires roughly 3 log2(N)
qubits to factor an integer N (it means that Shor’s algorithms require roughly
6K qubits to break RSA-2048), whereas Moore’s law states that the number of
bits - qubits here - that can be packed into a circuit doubles every 12-24
months. As an exercise, let’s take a 5-qubit quantum computer such as the one made available online by IBM this
month; then
the total number of qubits available to run Shor’s algorithm after M cycles of
Moore’s law can be calculated as 5 * 2M, therefore taking 18 months
as an average cycle span of Moore’s law, we end up with approximately sixteen
years from now until attacks against RSA-2048 become feasible – it takes 16.5 years
to go over 11 cycles of Moore’s law; this results in the availability of 10K qubits
(more precisely 10240=5*211) after this period, which is able to supply the 6K qubits required
to run the aforementioned attack. The same magnitude of qubits goes for Grover’s algorithm (“between around 3,000 and 7,000
logical qubits”) to mount attacks against AES, so that their security level will
be halved within that period of time. It means that if our assumptions hold, in
sixteen years AES-256 will be as secure as AES-128 is today and AES-128 will be
broken. Therefore, if we recall the time taken by Elliptic Curves until it was
ready for wide deployment, we realize that clock is ticking for PQCrypto.
What should I care about and what should I do?
A topic that will have major impact along with the advance of quantum computing
is long-term security, which can be related to:
·
Long-term
authenticity; such as the life span of a digitally-signed contract;
·
Long-term
confidentiality; on legal grounds – for instance, the German Legal Code stipulates
that medical data must remain confidential even after the patient´s death – or for
strategic reasons, such as organization or government secrets;
Long-term authenticity can be accomplished using simple techniques, like
re-signing a document using secure algorithms for as long as needed. Nonetheless,
this possibility has to be foreseen and guaranteed by the underlying laws or
any system of rules in place; otherwise it will also be threatened by the
advance of quantum computation.
Yet, long-term confidentiality is a much more difficult task. There is
no established way to address this issue and it is fair to state that none of
the current public-key cryptosystems can fulfill this task. It might be a good
choice to encrypt these data using strong symmetric ciphers using keys of at
least 192 bits to stay secure even if their security level is halved by quantum computers .
Finally, if you expect long-term security for your information, then you
should start looking for alternatives or planning for these changes right away.
Adversaries who cannot overcome the security of your information today, by
decrypting your data or forging your signature, can nevertheless keep a record
of the data until they have quantum computers, at which point their attacks
will succeed.