Collaborative Research: EAGER-QIA: High-Genus Code-Based Cryptography

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

Cryptography protects confidential communications: electronic commerce, voter information, diplomatic communication, human-rights interviews, medical records, and much more. However, attackers recording messages today will be able to decrypt those messages with future quantum computers. The most confidence-inspiring response is the McEliece cryptosystem, which has a strong security track record and is a leading contender for standardization of post-quantum cryptography, but this cryptosystem has a key size around a megabyte. Applications that cannot afford megabyte keys are currently forced to use cryptosystems whose security is much less stable. This project aims to build new post-quantum systems that bring McEliece's security stability and confidence to a wider range of applications. The public key in McEliece's cryptosystem is a generator matrix for a subfield subcode of an error-correcting code, specifically a genus-0 Goppa code. Subfield subcodes of higher-genus Goppa codes can correct more errors for the same code length and code dimension, improving the tradeoffs between efficiency and security. Showing that cryptosystems built from these codes can run at reasonable speed will require vertically integrated optimization of cryptosystem design, curve selection, decoding algorithms, algorithms for computer algebra, and vectorized software, with the further challenges of ensuring security against both mathematical and microarchitectural attacks. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.