Communications in Cryptology IACR CiC

Attacking trapdoors from matrix products

Authors

Thomas Decru, Tako Boris Fouotsa, Paul Frixons, Valerie Gilchrist, Christophe Petit
Thomas Decru ORCID
Université Libre de Bruxelles, Brussels, Belgium
thomas dot decru at ulb dot be
Tako Boris Fouotsa ORCID
EPFL, Lausanne, Switzerland
tako dot fouotsa at epfl dot ch
Paul Frixons
Université Libre de Bruxelles, Brussels, Belgium
paul dot frixons at gmail dot com
Valerie Gilchrist ORCID
Université Libre de Bruxelles, Brussels, Belgium
valerie dot gilchrist at ulb dot be
Christophe Petit ORCID
Université Libre de Bruxelles, Brussels, Belgium
University of Birmingham, Birmingham, England
christophe dot petit at ulb dot be

Abstract

Recently, Geraud-Stewart and Naccache proposed two trapdoors based on matrix products. In this paper, we answer the call for cryptanalysis. We explore how using the trace and determinant of a matrix can be used to attack their constructions. We fully break their first construction in a polynomial-time attack. We show an information leak in the second construction using characteristic polynomials, and provide two attacks that decrease the bit security by about half.

References

[CLG09]
Denis X Charles, Kristin E Lauter, and Eyal Z Goren. Cryptographic hash functions from expander graphs. Journal of CRYPTOLOGY, 22(1):93–113, 2009. DOI: 10.1007/s00145-007-9002-x
Google Scholar ePrint
[GSN23]
Remi Geraud-Stewart and David Naccache. New Public-Key Cryptosystem Blueprints Using Matrix Products in $\mathbb{F}_p$. Cryptology ePrint Archive, Paper 2023/1745. 2023.
Google Scholar ePrint
[LP10]
Françoise Levy-dit-Vehel and Ludovic Perret. Security analysis of word problem-based cryptosystems. Des. Codes Cryptogr., 54(1):29–41, 2010. DOI: 10.1007/S10623-009-9307-X
Google Scholar ePrint
[OEI24]
OEIS Foundation Inc.. Entry A003433 in The On-Line Encyclopedia of Integer Sequences. Accessed on 26/09/2024.. 2024.
Google Scholar ePrint
[TV06]
Terence Tao and Van Vu. On random $\pm1$ matrices: singularity and determinant. Random Structures Algorithms, 28(1):1–23, 2006. DOI: 10.1002/rsa.20109
Google Scholar ePrint
[TZ94]
Jean-Pierre Tillich and Gilles Zémor. Hashing with SL_2. In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 40–49. 1994. Springer. DOI: 10.1007/3-540-48658-5_5
Google Scholar ePrint
[vOW99]
Paul C. van Oorschot and Michael J. Wiener. Parallel Collision Search with Cryptanalytic Applications. J. Cryptol., 12(1):1–28, 1999. DOI: 10.1007/PL00003816
Google Scholar ePrint
[WM84]
Neal R. Wagner and Marianne R. Magyarik. A Public Key Cryptosystem Based on the Word Problem. In G. R. Blakley and David Chaum, editors, Advances in Cryptology, Proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, volume 196 of Lecture Notes in Computer Science, pages 19–36. 1984. Springer. DOI: 10.1007/3-540-39568-7_3
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/avrxrudhdj
History
Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07
How to cite

Thomas Decru, Tako Boris Fouotsa, Paul Frixons, Valerie Gilchrist, and Christophe Petit, Attacking trapdoors from matrix products. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/avrxrudhdj.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.