Security Banner with Transparent Bottom

Post-Quantum Cryptography and its Impact on Higher Education

A poster on Post-Quantum Cryptography and its impact on Higher Education
Brian Epstein <bepstein@ias.edu>

Is the Quantum Apocalypse upon us?  Will the Internet break once quantum computers are readily available?  What should we do going forward in Higher Ed?

The story in the book, "Who Moved My Cheese?" goes over the adventures (and misadventures) of four friends, Sniff and Scurry, and Hem and Haw and their search for cheese.  The moral of the story identifies the four typical ways that people react to major changes in their lives.  Either you can anticipate that change is inevitable and be ready for it, or you can be indecisive and unprepared and left with no cheese.

In the beginning, we looked for ways to protect our things and our thoughts.  We started by rolling big rocks in front of our caves to keep unwanted people and animals out.  This worked well until someone moved our rock.  Since then we have continued forward to find new and innovative ways of protecting ourselves, from trained animals, seals, locks, codes, ciphers, etc.  Each time a technique was broken, we innovated and moved onto newer and better strategies.

Quantum computers and their impact on present day encryption is no different.  To show how we are Sniffing and Scurrying as opposed to Hemming and Hawing, here is a brief picture of the history of today's encryption environment.

In 1977, Rivest, Shamir, and Adleman came up with the RSA public key protocol that is used for many applications across the Internet to protect our data.  It is based on the principal that multiplying two large prime numbers together is easy, but factoring a large composite number into its primes is believed to be difficult.  Here is a simple example, in reality, the primes being used are much much larger.

827 x 829 = 685583                   ⇒ EASY

636179 = p x q (what is p and q)  ⇒ HARD

In 1994, Peter Shor came up with an algorithm that would make factoring composite numbers into its primes much faster ... as long as you had a reliable and large enough quantum computer.  This would make it possible to quickly break RSA (and other algorithms such as Elliptic Curve Cryptography - ECC).  Although the algorithm has been shown to be sound, the large number of reliable quantum bits (known as qubits) necessary has been difficult to achieve.

In 2001, IBM showed that Shor's algorithm worked on a 7 qubit computer that they built.  It was able to successfully factor the composite number 15 into its primes of 3 and 5.  15 is a 4 bit number, represented in binary as 1111.

Eight years later, the National Institute of Standards and Technology (NIST) reached out to cryptography experts around the United States to come up with new protocols that were safe from an algorithm like Shor's that relied on quantum computers.  This was the start of a multi-decade process to move the world toward Quantum-Safe Cryptography (QSC).

In 2012, 11 years after using a quantum computer to factor the number 15, the next prime was successfully factored using a quantum computer.  This time it was 21, a 5 bit number (10101) was factored into its primes, 3 and 7.  NIST continues holding conferences and coordinating experts in the development of QSC protocols to replace the ones we use today.

Then in 2019, they tried to factor the composite number 35 into its primes.  This is a 6 bit number (100011) that factors into 5 and 7.  Unfortunately, there were too many errors in the quantum states and the computer was unable to successfully complete the factorization.

Two years later, NIST selects 4 QSC algorithms after many rounds of testing.  These are the algorithms that are being focused on to replace RSA, ECC, and others as well.  Today in 2023, those algorithms are being scrutinized to ensure that they are resilient to both traditional, and quantum based attacks.  Issues are found and patched.

In 2024, NIST plans on finalizing the standards for using these new protocols so that software vendors can start implementing the new protocols.  Many vendors are ahead of the game and already working on integrating the new protocols into their products, like the Open Quantum Safe group.

So, the sky is not falling today.  However, we do need to stay diligent in our Information Security Programs.  Risks like "store today and decrypt tomorrow" can be mitigated using standard security practices to keep data thieves out of our environment.  We can continue to focus on our most vulnerable assets, the humans themselves who are the targets of phishing and scams made to convince them to give up their credentials and the keys to the vault.  And, we can be ready for when new protocols and software are available to be integrated into our environments.

For more information, see the resources below.  And as always, Safe Computing!
Brian

Blog