Diagonally dominant matrices for cryptography
Authors
Abstract
Diagonally dominant lattices have already been used in cryptography, notably in the GGH and DRS schemes. This paper further studies the possibility of using diagonally dominant matrices in the context of lattice-based cryptography. To this end we study geometrical and algorithmic properties of lattices generated by such matrices. We prove novel bounds for the first minimum and the covering radius with respect to the max norm. Using these new results, we propose DRE (Diagonal Reduction Encryption) as an application example: a decryption failure free encryption scheme using diagonally dominant matrices and provide an experimental implementation to prove its suitability as a research direction. The trapdoor neither uses floating point arithmetic nor polynomial rings, and yet is less than 10 times slower than other optimised unstructured lattice-based standardisation candidates. This work could apply to cryptosystems based on the Lattice Isomorphism Problem as well. As a bonus, we also propose solutions to patch the DRS signature scheme, in particular using parameters leading to the use of sparse matrices.
References
How to cite
Andrea Lesavourey, Kazuhide Fukushima, Thomas Plantard, and Arnaud Sipasseuth, Diagonally dominant matrices for cryptography. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/ab0lmpgxq.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.