How can game theory be used to determine the best possible paths forward to prepare for cryptography in a post-quantum world?



First, some background:

  • Quantum computers use qubits instead of bits. Classical computers use electrical or optical pulses that represent zeros and ones while quantum computers typically use subatomic particles such as electrons or photons. Different quantum computers use different strategies to create and manage qubits. 
  • Quantum computers harness the principles of quantum mechanics such as superpositions (where qubits can represent different combinations of 0 and 1 simultaneously) and entanglement (where the state of one qubit instantaneously affects another) to perform tasks faster than classical computers. 
  • While quantum computers will have applications in many fields from materials science to pharmaceuticals research, they will probably not totally replace classical computers (Giles).

  • Currently, complex mathematical formulas are used to encrypt and decrypt data.
  • Symmetric cryptography uses the same key for both encryption and decryption. Asymmetric, or public-key, cryptography uses two mathematically linked keys, “one shared publicly to let people encrypt messages for the key pair’s owner, and the other stored privately by the owner to decrypt messages.” (Denning)
  • While symmetric cryptography is much faster and is thus used for communications and stored data, public-key cryptography is used for exchanging symmetric keys and digital authentication. Because almost all internet applications use a combination of the two, everything needs to be secure. (Denning)

  • Quantum computers could break symmetric cryptography by simply trying all possible keys. While they would be much faster than classical computers and thus be able to realistically break keys, making keys longer would be a easy solution.
  • Quantum computers pose a great threat to public-key cryptography.
    • “The algorithms for public-key encryption that are popular today—which are called RSA, Diffie-Hellman, and elliptic curve—all make it possible to start with a public key and mathematically compute the private key without trying all the possibilities.” (Denning)
    • Public-key cryptography is currently uncrackable when very long key pairs are used. Both classical and quantum computers don’t have the ability to factor large enough numbers or perform advanced math quickly enough to crack them. However, in the future, a sufficiently advanced quantum computer could easily break public-key encryption using a quantum computer. (Denning)

  • There are options for new secure methods: In 2016 the U.S. National Institute of Standards and Technology evaluated 69 potential new methods for post–quantum cryptography, which has since been reduced to 26. Unfortunately, it will likely be years before any draft standards are published. (Giles)
    • Supersingular isogeny key exchange
    • Lattice-based cryptography is “relatively simple, efficient, and highly parallelizable.” Although the security of lattice-based systems has been proven to be secure in difficult scenarios, it is difficult to say for sure how secure it is. (Chen)
    • Code-based cryptography includes all cryptosystems, symmetric or asymmetric, whose security relies, partially or totally, on the hardness of decoding in a linear error correcting code. (Sendrier)
    • Multivariate polynomial cryptography is “based on the difficulty of solving systems of multivariate polynomials over finite fields.” (Chen)
    • Hash-based signatures use hash functions. Although there are drawbacks, “their security, even against quantum attacks, is well understood.” (Chen)
    • There are many other options being explored (Chen).

This all seems rather dire (and complicated). What should the response be?

What U.S. Governments and Corporations Should Do:

Game Theory shows that allied governments and corporations developing quantum technologies should collaborate. For example, Sara Bjerg Moller, a professor of International Relations, writes that one of NATO’s goals should be countering China (Moller). One good way to achieve this goal would be to work together to make sure China does not develop a sufficiently advanced quantum computer first. Another example of the importance of collaboration is U.S corporations. Although Google, IBM, Microsoft, and others, are all competing, it is in all of the corporations best interest to make sure a malicious group does not get there first, so that customers’ data is not compromised. The idea of collaboration to implement the post-quantum cryptography system is also really important because everyone will benefit from security. Sadly, governments and corporations being what they are, collaboration is unlikely.

This could probably also be modeled with a pareto optimal map. I modeled it with a movement diagram to increase simplicity.
What Researchers Should Do:

Unfortunately, game theory does not show if while picking the best and most efficient post-quantum cryptography technique is important, the highest priority should be implementing a workable system quickly. One of the interesting aspects of game theory is it does not always have an answer.

What You Can Do:

A lot of these ideas aren’t in the public’s conscious yet. Learn more! Talk to people you know! Ask your representatives and governments what they are doing to prepare. If this interests you, both cybersecurity and quantum computing are quickly growing fields that will need more researchers! My works cited page is a great place to find more resources.

I welcome feedback, thoughts, and questions in the comments!

Still Interested? Check out works cited for more info.

Works Consulted and Cited


1 comment

  1. Hi Chloe, great job with this project — the topic is very interesting and you explained it well! The collaboration idea there is not something I have thought of or heard of before, so props for thinking of that too! I think the next question with the collaboration approach is: when should groups begin collaborating? And, it seems like the answer may vary depending on the progress in developing the tech.

Leave a Reply