O2MD²: A New Post-Quantum Cryptosystem With One-to-Many Distributed Key Management Based on Prime Modulo Double Encapsulation

Abstract

Polynomial-time attacks designed to run on quantum computers and capable of breaking RSA and AES are already known. It is imperative to develop quantum-resistant algorithms before quantum computers become available. Computationally hard problems defined on lattices have been proposed as the fundamental security bases for a new type of cryptography. The National Institute of Standards and Technology (NIST) recently hosted the Post-Quantum Cryptography Standardization project, aiming to create a roster of innovative post-quantum cryptosystems. These candidates have been publicly available for testing since early 2017. As they are currently under analysis, new proposals are still desirable. As such, we use the ring learning with errors (RLWE) problem combined with arithmetic functions to propose the O2MD2 cryptosystem, which provides a one-to-many private/public key architecture having a distributed key refresh for a network of users while working on multiple polynomial rings over different prime order fields. Our solution has three different frameworks that reach AES-256 equivalent security, and provides message integrity and message authenticity verifications. We compare our solution’s speed against the speed of the twenty-six different implementations from seven popular candidates in the NIST project, and our cryptosystem performs from 2 to 4 orders of magnitude faster than them. We also propose six different implementations that reach the security levels 1, 3 and 5 proposed in the NIST competition. Finally, we used the NIST Statistical Test Suite to verify the indistinguishability of our produced ciphertexts against randomly generated noise.

Keywords

• Abstract algebra
• cryptographic protocols
• quantum cryptography
• lattices
• O2MD²
• post-quantum