A New Matrix Algebra for LWE Encryption

Public key cryptography is an extremely active research area. New protocols, primitives and attacks are often proposed. Some public key cryptographic primitives tend to be extremely prolific in terms of flexibility, efficiency and security. One of the most flexible cryptographic class of primitives is the lattice-based cryptography. Among the main challenges of this class is to reduce the key and ciphertext sizes. This challenge has been many times addressed by adopting a structured matrix for represent the lattices. The most common types of structured matrix are the circulant and negacyclic matrices. In this paper, we propose a new parameterization for building compact lattices, in the form of the so-called discrete Rojo algebras. This parameterization may be as compact as the circulant and negacyclic matrix rings found in the literature, but with the advantage of having a completely different nature. Thereby, contributing with the biodiversity of primitives, avoid patents, or certain possible attacks for the literature parameters.