Communications in Cryptology IACR CiC

Diagonally dominant matrices for cryptography

Authors

Andrea Lesavourey, Kazuhide Fukushima, Thomas Plantard, Arnaud Sipasseuth
Andrea Lesavourey ORCID
XLIM, Limoges, France
andrea dot lesavourey at unilim dot fr
Kazuhide Fukushima ORCID
KDDI Research, Fujimino, Japan
ka-fukushima at kddi dot com
Thomas Plantard ORCID
Nokia Bell Labs, Murray Hill, NJ, USA
thomas dot plantard at nokia-bell-labs dot com
Arnaud Sipasseuth ORCID
University of Tokyo, Tokyo, Japan
sipasseuth at g dot ecc dot u-tokyo dot ac dot jp

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

[ADPS16]
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum Key Exchange - A New Hope. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016: 25th USENIX Security Symposium, pages 327–343, Austin, TX, USA. 2016. USENIX Association.
[AGVW17]
Martin R. Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the Expected Cost of Solving uSVP and Applications to LWE. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part I, volume 10624 of Lecture Notes in Computer Science, pages 297–322, Hong Kong, China. 2017. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-70694-8_11
[Ajt98]
Miklós Ajtai. The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract). In 30th Annual ACM Symposium on Theory of Computing, pages 10–19, Dallas, TX, USA. 1998. ACM Press. DOI: 10.1145/276698.276705
[AKKV05]
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, and Nisheeth K. Vishnoi. Hardness of Approximating the Closest Vector Problem with Pre-Processing. In 46th Annual Symposium on Foundations of Computer Science, pages 216–225, Pittsburgh, PA, USA. 2005. IEEE Computer Society Press. DOI: 10.1109/SFCS.2005.40
[Bab86]
L. Babai. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1-13, March 1986. DOI: 10.1007/BF02579403
[BBdV+17]
Jens Bauch, Daniel J. Bernstein, Henry de Valence, Tanja Lange, and Christine van Vredendaal. Short Generators Without Quantum Computers: The Case of Multiquadratics. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, Part I, volume 10210 of Lecture Notes in Computer Science, pages 27–59, Paris, France. 2017. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-56620-7_2
[BCD+16]
Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security, pages 1006–1018, Vienna, Austria. 2016. ACM Press. DOI: 10.1145/2976749.2978425
[BDK+18]
Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Security and Privacy, pages 353–367, London, United Kingdom. 2018. IEEE Computer Society Press. DOI: 10.1109/EuroSP.2018.00032
[BGPS23]
Huck Bennett, Atul Ganju, Pura Peetathawatchai, and Noah Stephens-Davidowitz. Just How Hard Are Rotations of $\mathbb{{Z}}^n$? Algorithms and Cryptography with the Simplest Lattice. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 252–281, Lyon, France. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-30589-4_9
[BIP04]
Jean-Claude Bajard, Laurent Imbert, and Thomas Plantard. Modular Number Systems: Beyond the Mersenne Family. In Helena Handschuh and Anwar Hasan, editors, SAC 2004: 11th Annual International Workshop on Selected Areas in Cryptography, volume 3357 of Lecture Notes in Computer Science, pages 159–169, Waterloo, Ontario, Canada. 2004. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-540-30564-4_11
[BLNR22]
Olivier Bernard, Andrea Lesavourey, Tuong-Huy Nguyen, and Adeline Roux-Langlois. Log-$S$-unit Lattices Using Explicit Stickelberger Generators to Solve Approx Ideal-SVP. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part III, volume 13793 of Lecture Notes in Computer Science, pages 677–708, Taipei, Taiwan. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-22969-5_23
[BR20]
Olivier Bernard and Adeline Roux-Langlois. Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, Part II, volume 12492 of Lecture Notes in Computer Science, pages 349–380, Daejeon, South Korea. 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-64834-3_12
[Bru82]
Richard A Brualdi. Matrices eigenvalues, and directed graphs. Linear and Multilinear Algebra, 11(2):143–165, 1982. DOI: 10.1080/03081088208817439
[CDPR16]
Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering Short Generators of Principal Ideals in Cyclotomic Rings. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 559–585, Vienna, Austria. 2016. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-662-49896-5_20
[CDW21]
Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time. J. ACM, 68(2), January 2021. DOI: 10.1145/3431725
[CN11]
Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 1–20, Seoul, South Korea. 2011. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-642-25385-0_1
[CPS82]
JH Conway, RA Parker, and NJA Sloane. The Covering Radius of the Leech Lattice. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 1982. DOI: 10.1098/rspa.1982.0042
[dBS15]
Charles F de Barros and L Menasché Schechter. GGH may not be dead after all. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, 3(1), 2015. DOI: 10.5540/03.2015.003.01.0095
[Den03]
Alexander W. Dent. A Designer's Guide to KEMs. In Kenneth G. Paterson, editor, 9th IMA International Conference on Cryptography and Coding, volume 2898 of Lecture Notes in Computer Science, pages 133–151, Cirencester, UK. 2003. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-540-40974-8_12
[DHK+23]
Julien Duman, Kathrin Hövelmanns, Eike Kiltz, Vadim Lyubashevsky, Gregor Seiler, and Dominique Unruh. A Thorough Treatment of Highly-Efficient NTRU Instantiations. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 13940 of Lecture Notes in Computer Science, pages 65–94, Atlanta, GA, USA. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-31368-4_3
[Din00]
Irit Dinur. Approximating $\mathrm{SVP}_\infty$ to within Almost-Polynomial Factors Is $\mathrm{NP}$-Hard. In Giancarlo Bongiovanni, Rossella Petreschi, and Giorgio Gambosi, editors, Algorithms and Complexity, pages 263–276, Berlin, Heidelberg. 2000. Springer Berlin Heidelberg. DOI: 10.1007/3-540-46521-9_22
[DKL+21]
Léo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation. Round-2 submission to the NIST PQC project, 35, 2021.
[DLdW19]
Emmanouil Doulgerakis, Thijs Laarhoven, and Benne de Weger. Finding Closest Lattice Vectors Using Approximate Voronoi Cells. In Jintai Ding and Rainer Steinwandt, editors, Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019, pages 3–22, Chongqing, China. 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-25510-7_1
[DN12]
Léo Ducas and Phong Q. Nguyen. Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology – ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science, pages 433–450, Beijing, China. 2012. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-642-34961-4_27
[DPPvW22]
Léo Ducas, Eamonn W. Postlethwaite, Ludo N. Pulles, and Wessel P. J. van Woerden. Hawk: Module LIP Makes Lattice Signatures Fast, Compact and Simple. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 65–94, Taipei, Taiwan. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-22972-5_3
[DvW22]
Léo Ducas and Wessel P. J. van Woerden. On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part III, volume 13277 of Lecture Notes in Computer Science, pages 643–673, Trondheim, Norway. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-07082-2_23
[DY21]
Léo Ducas and Yang Yu. Learning Strikes Again: The Case of the DRS Signature Scheme. Journal of Cryptology, 34(1):1, January 2021. DOI: 10.1007/s00145-020-09366-9
[ENST23]
Thomas Espitau, Guilhem Niot, Chao Sun, and Medhi Tibouchi. Squirrels: Square Unstructured Integer Euclidean Lattice Signature. 2023.
[FKPY22]
Pierre-Alain Fouque, Paul Kirchner, Thomas Pornin, and Yang Yu. BAT: Small and Fast KEM over NTRU Lattices. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(2):240–265, 2022. DOI: 10.46586/tches.v2022.i2.240-265
[FO99]
Eiichiro Fujisaki and Tatsuaki Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Michael J. Wiener, editor, Advances in Cryptology – CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 537–554, Santa Barbara, CA, USA. 1999. Springer Berlin Heidelberg, Germany. DOI: 10.1007/3-540-48405-1_34
[Ger31]
Semyon Aronovich Gerschgorin. Uber die Abgrenzung der Eigenwerte Einer Matrix. Bulletin de l'Academie des Sciences de l'URSS. Classe des Sciences Mathematiques et na, 6:749–754, 1931.
[GGH97]
Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-Key Cryptosystems from Lattice Reduction Problems. In Burton S. Kaliski Jr., editor, Advances in Cryptology – CRYPTO'97, volume 1294 of Lecture Notes in Computer Science, pages 112–131, Santa Barbara, CA, USA. 1997. Springer Berlin Heidelberg, Germany. DOI: 10.1007/BFb0052231
[GINX16]
Nicolas Gama, Malika Izabachène, Phong Q. Nguyen, and Xiang Xie. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 528–558, Vienna, Austria. 2016. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-662-49896-5_19
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing, pages 197–206, Victoria, BC, Canada. 2008. ACM Press. DOI: 10.1145/1374376.1374407
[HPS98]
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A Ring-Based Public Key Cryptosystem. In Third Algorithmic Number Theory Symposium (ANTS), volume 1423 of Lecture Notes in Computer Science, pages 267–288. June 1998. Springer. DOI: 10.1007/BFb0054868
[Kan87]
Ravi Kannan. Minkowski's convex body theorem and integer programming. Mathematics of operations research, 12(3):415–440, 1987. DOI: 10.1287/moor.12.3.415
[Kle00]
Philip N. Klein. Finding the closest lattice vector when it's unusually close. In David B. Shmoys, editor, 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 937–941, San Francisco, CA, USA. 2000. ACM-SIAM. DOI: 10.5555/338219.338661
[Lim82]
David JN Limebeer. The application of generalized diagonal dominance to linear system stability theory. International Journal of Control, 36(2):185–212, 1982. DOI: 10.1080/00207178208932886
[LLL82]
Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. DOI: 10.1007/BF01457454
[LPS20]
Andrea Lesavourey, Thomas Plantard, and Willy Susilo. Short Principal Ideal Problem in multicubic fields. Journal of Mathematical Cryptology, 14(1):359–392, 2020. DOI: doi:10.1515/jmc-2019-0028
[LSZ+24]
Xiuhan Lin, Moeto Suzuki, Shiduo Zhang, Thomas Espitau, Yang Yu, Mehdi Tibouchi, and Masayuki Abe. Cryptanalysis of the Peregrine Lattice-Based Signature Scheme. In Qiang Tang and Vanessa Teague, editors, PKC 2024: 27th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 14601 of Lecture Notes in Computer Science, pages 387–412, Sydney, NSW, Australia. 2024. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-57718-5_13
[{McE}78]
Robert J. McEliece. A public-key cryptosystem based on algebraic coding theory. Technical report, Jet Propulsion Laboratory, California Institute of Technology. https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF. 1978.
[MG12]
Daniele Micciancio and Shafi Goldwasser. Complexity of lattice problems: a cryptographic perspective, volume 671. Springer Science & Business Media 2012. DOI: 10.1007/978-1-4615-0897-7
[MH78]
Ralph Merkle and Martin Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE transactions on Information Theory, 24(5):525–530, 1978. DOI: 10.1109/TIT.1978.1055927
[Mic01]
Daniele Micciancio. Improving lattice based cryptosystems using the Hermite normal form. In International Cryptography and Lattices Conference, pages 126–145. 2001. Springer. DOI: 10.1007/3-540-44670-2_11
[Min96]
Hermann Minkowski. Geometrie der Zahlen. B.G. Teubner, Leipzig 1896.
[MR09]
Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-quantum cryptography, pages 147–191. Springer 2009. DOI: 10.1007/978-3-540-88702-7_5
[MW01]
Daniele Micciancio and Bogdan Warinschi. A linear space algorithm for computing the Hermite normal form. In Proceedings of the 2001 international symposium on Symbolic and algebraic computation, pages 231–236. 2001. ACM. DOI: 10.1145/384101.384133
[Ngu99]
Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto'97. In Michael J. Wiener, editor, Advances in Cryptology – CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 288–304, Santa Barbara, CA, USA. 1999. Springer Berlin Heidelberg, Germany. DOI: 10.1007/3-540-48405-1_18
[NR06]
Phong Q. Nguyen and Oded Regev. Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. In Serge Vaudenay, editor, Advances in Cryptology – EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 271–288, St. Petersburg, Russia. 2006. Springer Berlin Heidelberg, Germany. DOI: 10.1007/11761679_17
[NS16]
Phong Q. Nguyen and Igor E. Shparlinski. Counting Co-Cyclic Lattices. SIAM Journal on Discrete Mathematics, 30(3):1358-1370, 2016. DOI: 10.1137/15M103950X
[PHS19]
Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé. Approx-SVP in Ideal Lattices with Pre-processing. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 685–716, Darmstadt, Germany. 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-17656-3_24
[PSDS18]
Thomas Plantard, Arnaud Sipasseuth, Cédric Dumondelle, and Willy Susilo. DRS : Diagonal dominant Reduction for lattice-based Signature. PQC Standardization Conference, Round 1 submissions. 2018.
[PSW08]
Thomas Plantard, Willy Susilo, and Khin Than Win. A Digital Signature Scheme Based on CVP$_{infinity}$. In Ronald Cramer, editor, PKC 2008: 11th International Workshop on Theory and Practice in Public Key Cryptography, volume 4939 of Lecture Notes in Computer Science, pages 288–307, Barcelona, Spain. 2008. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-540-78440-1_17
[Reg03]
Oded Regev. New lattice based cryptographic constructions. In 35th Annual ACM Symposium on Theory of Computing, pages 407–416, San Diego, CA, USA. 2003. ACM Press. DOI: 10.1145/780542.780603
[Rum18]
Siegfried M Rump. Estimates of the determinant of a perturbed identity matrix. Linear algebra and its applications, 558:101–107, 2018. DOI: 10.1016/j.laa.2018.08.009
[SKLJS22]
Eun-Young Seo, Young-Sik Kim, Joon-Woo Lee, and No Jong-Seon. Peregrine: Submission to the Korea post-quantum cryptography competition. 2022.
[SPS19a]
Arnaud Sipasseuth, Thomas Plantard, and Willy Susilo. Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices. Journal of Mathematical Cryptology, 13(3-4):169–196, 2019. DOI: 10.1515/jmc-2016-0066
[SPS19b]
Arnaud Sipasseuth, Thomas Plantard, and Willy Susilo. Improving the Security of the DRS Scheme with Uniformly Chosen Random Noise. In Julian Jang-Jaccard and Fuchun Guo, editors, ACISP 19: 24th Australasian Conference on Information Security and Privacy, volume 11547 of Lecture Notes in Computer Science, pages 119–137, Christchurch, New Zealand. 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-21548-4_7
[SPS20]
Arnaud Sipasseuth, Thomas Plantard, and Willy Susilo. A Noise Study of the PSW Signature Family: Patching DRS with Uniform Distribution. Information, 11(3), 2020. DOI: 10.3390/info11030133
[Tau49]
Olga Taussky. A recurring theorem on determinants. The American Mathematical Monthly, 56(10P1):672–676, 1949. DOI: 10.1080/00029890.1949.11990209
[YD18]
Yang Yu and Léo Ducas. Learning Strikes Again: The Case of the DRS Signature Scheme. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, Part II, volume 11273 of Lecture Notes in Computer Science, pages 525–543, Brisbane, Queensland, Australia. 2018. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-03329-3_18
[YJW23]
Yang Yu, Huiwen Jia, and Xiaoyun Wang. Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part V, volume 14085 of Lecture Notes in Computer Science, pages 390–420, Santa Barbara, CA, USA. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-38554-4_13

PDFPDF Open access

History
Submitted: 2025-04-08
Accepted: 2025-06-02
Published: 2025-07-07
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.