Attacking trapdoors from matrix products
Open Access
- 7 October 2024
- journal article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (3)
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.Keywords
Funding Information
- Fund for Scientific Research
- Engineering and Physical Sciences Research Council (EP/V011324/1)
This publication has 6 references indexed in Scilit:
- Security analysis of word problem-based cryptosystemsDesigns, Codes and Cryptography, 2009
- Cryptographic Hash Functions from Expander GraphsJournal of Cryptology, 2007
- On random ±1 matrices: Singularity and determinantRandom Structures & Algorithms, 2005
- Hashing with SL 22001
- A Public-Key Cryptosystem Based on the Word Problem2000
- Parallel Collision Search with Cryptanalytic ApplicationsJournal of Cryptology, 1999