Attacking trapdoors from matrix products

Authors

Thomas Decru, Tako Boris Fouotsa, Paul Frixons, Valerie Gilchrist, Christophe Petit

Thomas Decru

Université Libre de Bruxelles, Brussels, Belgium
thomas dot decru at ulb dot be

Tako Boris Fouotsa

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

Université Libre de Bruxelles, Brussels, Belgium
valerie dot gilchrist at ulb dot be

Christophe Petit

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

PDF 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

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

What a lovely hat

Is it made out of tin foil?