Coding & Encrypting: Quantum-Resistant Cryptography with Error-Correcting Codes

While mainstream quantum computing won’t be arriving with the summer weather, there are enormous amounts of cybersecurity infrastructure critical to national security that rely on algorithms vulnerable to attacks by quantum computers. This leads us to ask how we build a robust, quantum-resistant cryptosystem for secure communication. There are many avenues that are being explored for creating quantum-resistant cryptosystems, and this area of research is called post-quantum cryptography.  

Two Six Technologies has been exploring one such avenue known as code-based cryptography. In code-based cryptosystems, error-correcting codes are used as the foundation. An error-correcting code is a tool used in communication to detect and correct errors that may have occurred during transmission on a noisy channel.  

How is this communication tool incorporated into cryptosystems? At a high-level, a code-based cryptosystem encrypts messages by intentionally inserting errors, so that adversaries can’t distinguish the encrypted message from random noise. The secret key the recipient holds consists of parameters from the error-correcting code that allows for the inserted errors to be corrected so the message can be decrypted and read. 

One such code-based cryptosystem is Classic McEliece, and a modern version of this cryptosystem has made it through to the fourth round of the National Institute of Standards and Technology’s (NIST) competition to identify quantum-resistant algorithms for use in safeguarding government systems. 

Two Six wanted to explore the correctness of the NIST reference implementation for Classic McEliece using techniques and tools from formal methods. This type of analysis can provide mathematical proofs that the code is doing what it claims to do in a handwritten specification, and this gives a very high assurance that the software has no bugs. 

The Two Six team is exploring secret key generation for Classic McEliece using formal methods, and we asked the following questions about the NIST reference implementation:  

  • Can we use standard tools in formal methods on this algorithm for this implementation?   
  • How free of bugs is this implementation?
  • If  this implementation is free of bugs, can we use formal methods to improve it?  

In light of recent advancements of attacks against lattice-based cryptosystems, Two Six is striving to open up doors for a number of code-based algorithms to be used where correctness is vital. Reach out to [email protected] for more information.