**Key Encapsulation Mechanism From Modular Multivariate Linear Equations**

*Muhammad Rezal Kamel Ariffin and Abderrahmane Nitaj and Yanbin Pan and Nur Azman Abu*

**Abstract: **In this article we discuss the modular pentavariate and hexavariate linear equations and its usefulness for asymmetric cryptography. Construction of our key encapsulation mechanism dwells on such modular linear equations whose unknown roots can be interpreted as long vectors within a lattice which surpasses the Gaussian heuristic; hence unable to be identified by the LLL lattice reduction algorithm. By utilizing our specially constructed public key when computing the modular hexavariate linear ciphertext equation, the decapsulation mechanism can correctly output the shared secret parameter.
The scheme has short key length, no decapsulation failure issues, plaintext-to-ciphertext expansion of one-to-one as well as uses ``simple" mathematics in order to achieve maximum simplicity in design, such that even practitioners with limited mathematical background will be able to understand the arithmetic.
Due to inexistence of efficient algorithms running upon a quantum computer to obtain the roots of our modular pentavariate and hexavariate linear equation and also to retrieve the private key from the public key, our key encapsulation mechanism can be a probable candidate for seamless post quantum drop-in replacement for current traditional asymmetric schemes.

**Category / Keywords: **public-key cryptography / Post quantum cryptosystem, LLL algorithm, modular pentavariate linear equation root problem, modular hexavariate linear equation root problem

**Date: **received 29 Jan 2019, last revised 15 Feb 2019

**Contact author: **rezal at upm edu my

**Available format(s): **PDF | BibTeX Citation

**Version: **20190215:093709 (All versions of this report)

**Short URL: **ia.cr/2019/093

[ Cryptology ePrint archive ]