Code-based cryptography: past, present, future

Abstract: Public key cryptography protects the privacy and security of our global digital communication infrastructure. All widely-deployed public key cryptographic systems are based on the difficulty in solving variations of the integer factorization and discrete logarithm problems. In 1991, Peter Shor presented quantum algorithms that could solve these problems significantly faster than classical computers. Consequently, a full-scale quantum computer would upend the security and privacy of our digital world. The National Institute of Standards and Technology (NIST) initiated a process to update current public-key standards to schemes believed to be quantum-resistant. NIST made a worldwide call for quantum-resistant public-key cryptographic algorithms and, in response, received over 80 submissions to be considered for standardization. NIST is currently in the 3rd round of analysis and 3 of the remaining 15 algorithms are based on error-correcting codes. Error correcting codes were originally designed to improve communication across noisy channels, enabling the correction of errors introduced in transit. Messages are encoded by adding some redundancy in such a way that errors introduced by the channel can be removed from the received information, and then the receiver can decode (remove redundancy) to recover the original message. In the 1970’s it was discovered that cryptosystems could be designed based on error-correcting codes if errors were strategically introduced by the sender so that only the intended receiver could decode. Due to the inefficiency of early schemes, these results were not actively pursued by cryptographers until decades later. In this talk, we will explore the foundations of code-based cryptography, the history of securing code-based cryptosystems, and role code-based cryptosystems could play in securing our digital world.

Back to Search Research Symposium Abstracts