International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Attacking trapdoors from matrix products

Authors:
Thomas Decru , Université Libre de Bruxelles
Tako Boris Fouotsa , EPFL
Paul Frixons , Université Libre de Bruxelles
Valerie Gilchrist , Université Libre de Bruxelles
Christophe Petit , Université Libre de Bruxelles, University of Birmingham
Download:
DOI: 10.62056/avrxrudhdj
URL: https://cic.iacr.org//p/1/3/43
Search ePrint
Search Google
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.

BibTeX
@article{cic-2024-34854,
  title={Attacking trapdoors from matrix products},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/43},
  doi={10.62056/avrxrudhdj},
  author={Thomas Decru and Tako Boris Fouotsa and Paul Frixons and Valerie Gilchrist and Christophe Petit},
  year=2024
}