IT Security for Critical Infrastructures

Security Made in Germany mtg.de

WHITE PAPER

Post-Quantum Cryptography
How to protect existing systems against future quantum computing threats

Post-quantum cryptography (PQC) is the field of cryptography that deals with cryptographic
primitives and algorithms that are secure against an attack by a large-scale quantum computer.
While this area gained widespread attention among academics, it has been largely overlooked by
industry. As we will see in this white paper, this is indeed a matter that industry should take seriously.

Quantum Computers principle of quantum mechanics that applies to qubits.

This principle allows qubits to interact and influence
A quantum computer operates on the basis of the
one another regardless of the distance and medium
quantum mechanical principles superposition and
between them.
quantum entanglement. The unit of information in
a quantum computer is called qubit. In contrast to Combined with other properties of quantum computers,
classical bits, which either have the value 1 or 0 and are these principles make it possible to calculate specific
therefore in one state or the other, a qubit is a super- problems much more efficiently than with conventional
position of these states. This means that it is both 0 computers. The main advantage of a quantum computer
and 1 at the same time and assumes both states. The is its ability to simulate the physical micro-world much
phenomenon of quantum entanglement is the second more accurately. As our world is governed by quantum
 White Paper

Post-Quantum Cryptography mtg.de

mechanics at atomic level, a computer that understands functions can be increased with relatively little effort. To
and uses these same phenomena can much better solve the first problem however, it is necessary to select
approximate quantum behaviours than a traditional new mathematical problems that are not vulnerable
computer. to quantum computers and to design, analyse, and
implement new cryptographic schemes based on these
Research on quantum computers has gained much
mathematical problems.
traction in recent years. With a quantum computer, it
is much faster to run simulations and perform certain
Who is affected
calculations. Therefore, it can be used to optimise var-
ious applications and products in the pharmaceutical, The probability to break RSA 2048 by 2031 is estimated
chemical, and other industries. A rather negative side at 50 % [Mos15]. Complex software solutions and products
effect of quantum computers is their ability to solve the usually entail long and arduous product development
mathematical problems on which today’s cryptography processes. Additionally, many industries like automotive,
is based very efficiently. aerospace, transportation, public and critical infrastructure
and others, design and produce products today that will
Quantum Computers and Cryptography be on the market for the next 20 to 50 years.

Small-scale quantum computers have already been

created by large companies and organisations around > 10 years product life cycle
the world. These computers are expanding rapidly, and
the goal of a large-scale quantum computer seems Developement 10 years product life cycle
within reach in the not-too-distant future. When these
computers become available, current public-key crypto-
systems like RSA or elliptic curves will become insecure. PKI broken
Shor’s algorithm [Sho94] shows how, using a quantum
computer, the prime factorisation of a large number and 2018 2020 2026 2031
the calculation of discrete logarithms can be done in
polynomial time. 1-in-7-chance 1-in-2-chance
Universal Quantum Universal Quantum
Computer available Computer available
Additionally, symmetric encryption algorithms and hash (Mosca, 2015) (Mosca, 2015)
functions that are not directly tied to a mathematical
problem are also at risk, as Grover’s algorithm [Gro96]
shows. In this case, the impact is not as devastating Another interesting aspect of these industries is their
as in public-key cryptography, but the time it takes to reliance on pre-orders that are produced now, but
break a symmetric scheme or a hash function through delivered far off in the future (+10 years). These products
a brute-force attack or an exhaustive search is reduced will most certainly face the threat of quantum computers.
by almost half. Consequently, it is essential to plan ahead and integrate
the required protection mechanisms in the design and
production processes that take place today.
Type Algorithm Key Strength Key Strength Quantum
Classic Quantum Attack
(bits) (bits) How to avoid this danger
RSA 2048 112 o
RSA 3072 128 Shor’s The good news is that there already are cryptographic
Asymmetric
ECC256 128 Algorithm systems that offer protection against strong quantum
ECC 521 256 computers. The scientific field dealing with this aspect
AES128 128 64 Grover’s is called post-quantum cryptography. It focuses on
Symmetric
AES 256 256 128 Algorithm the creation and deployment of what is known as
Source: isara.com post-quantum cryptosystems. But as discussed above,
this is no longer a mere scientific issue. There are cryp-
The solution to the latter problem is considered easy, tographic algorithms based on mathematical problems
since the security parameters of the cryptographic that cannot be easily solved by a quantum computer.
White Paper

Post-Quantum Cryptography mtg.de

These algorithms fall into five categories. contain errors, the security of the exchanged key would
be reduced to that of Diffie-Hellman, which is still what
> Hash-based
is considered secure and state of the art today.
> Code-based
> Lattice-based The use of hybrid schemes can therefore protect against
> Multivariate more types of future dangers and threats. It is highly
> Supersingular isogeny-based recommended in order to ease the transition into the
post-quantum era.
Each category focuses on a different set of mathemat-
ical problems, some of them as old, mature, and well
Current Standardisation Activities
understood as the mathematics of today´s public-key
cryptography, and others newer, more performant but A major issue for post-quantum cryptography is the lack
yet untested in practice. of standardisation, making a widespread deployment of
PQC difficult and impractical. Luckily, large standardisa-
The diversity of the PQC ecosystem can create uncer-
tion organisations have already started working on it.
tainty about the security promises of these schemes.
Academia and industry both agree that the way to tack- NIST, the National Institute of Standards and Technology
le this issue is through the use of hybrid schemes. in the USA, has made a call for proposals for crypto-
systems that are secure against quantum computers
Hybrid Schemes [NIST]. The 69 submitted algorithms will be evaluated
and some of them will be standardised.
A hybrid scheme is a combination of a traditional and
a post-quantum scheme, meaning that the resulting The European Standards Organization ETSI has also
scheme is at least as secure as one of the schemes started research in this area with some preliminary
used. In the example of key exchange, this would trans- publications [ETSI]. Furthermore, the IETF (Internet
late into performing two independent key exchanges, Engineering Task Force) has already published a stand-
one with a traditional scheme like Diffie-Hellman and ard for the post-quantum stateful hash-based XMSS
one with a post-quantum scheme. The two resulting scheme (eXtended Merkle Signature Scheme) [XMSS]
keys are then combined (e.g. with an XOR operation) to and is planning to release more soon.
create the final secret key that was exchanged.
However, standardisation takes time and it will be
Now, imagine what would happen if strong quantum years before the international community implements
computers come into widespread use and Diffie-Hellman these standards. Industries and governments that need
becomes insecure. The security of the key would remain to integrate PQC into their products, processes, and
as strong as that of the quantum key exchange scheme infrastructures today should start addressing this issue
that was used, and it could therefore still be used and as soon as possible. The longer they wait, the greater
considered secure. On the other hand, if the chosen the danger of finding themselves unprepared in the
post-quantum scheme was proven to be faulty or to post-quantum era.

Sources:
[Shor94] P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, Proc. 35nd Annual Symposium on Foundations of Computer Science (Shafi Goldwasser, ed.),
IEEE Computer Society Press (1994), pp. 124-134
[Grover96] L. K. Grover, A fast quantum mechanical algorithm for database search, STOC ‚96 Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219
[Mosca15] https://eprint.iacr.org/2015/1075.pdf
[NIST] https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf
[ETSI] https://www.etsi.org/technologies-clusters/technologies/quantum-safe-cryptography
[XMSS] https://tools.ietf.org/html/rfc8391

MTG is a leading expert for encryption technologies in Germany.

MTG’s IT security solutions effectively secure critical infrastructures
and the Internet of Things (IoT). MTG offers a comprehensive portfolio
of state-of-the-art quantum-safe security products and services.
Working closely with our customers, we integrate PQC into existing
applications and protocols by means of hybrid processes.
© MTG

MTG AG · Dolivostr. 11 · 64293 Darmstadt · Germany

For further information feel free to contact us! Tel +49 6151 8193-0 · [email protected] · mtg.de