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.

Note: Editorial updates, updated figures, and added Section 6.2.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A minor revision of an IACR publication in CIC 2024
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-09-26: revised; 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}
}