Attacking trapdoors from matrix products

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

Paper 2024/1332

Attacking trapdoors from matrix products

Thomas Decru, Université Libre de Bruxelles

Tako Boris Fouotsa, École Polytechnique Fédérale de Lausanne

Paul Frixons, Université Libre de Bruxelles

Valerie Gilchrist, Université Libre de Bruxelles

Christophe Petit, Université Libre de Bruxelles, University of Birmingham

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 an attack using traces that decreases the bit security by about half.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: matrix cryptanalysis
Contact author(s): thomas decru @ ulb be
fouotsabcrb @ gmail com
paul frixons @ gmail com
valerie gilchrist @ ulb be
christophe petit @ ulb be
History: 2024-08-30: approved; 2024-08-26: received; See all versions
Short URL: https://ia.cr/2024/1332
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1332,
      author = {Thomas Decru and Tako Boris Fouotsa and Paul Frixons and Valerie Gilchrist and Christophe Petit},
      title = {Attacking trapdoors from matrix products},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1332},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1332}
}