{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T16:54:05Z","timestamp":1785430445165,"version":"3.56.0"},"reference-count":8,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002661","name":"Fund for Scientific Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V011324\/1"],"award-info":[{"award-number":["EP\/V011324\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.62056\/avrxrudhdj","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T11:13:33Z","timestamp":1728299613000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Attacking trapdoors from matrix products"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0253-4180","authenticated-orcid":false,"given":"Thomas","family":"Decru","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01r9htc13","id-type":"ROR","asserted-by":"publisher"}],"name":"Universit\u00e9 Libre de Bruxelles","place":["Brussels, Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1821-8406","authenticated-orcid":false,"given":"Tako","family":"Fouotsa","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02s376052","id-type":"ROR","asserted-by":"publisher"}],"name":"EPFL","place":["Lausanne, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Frixons","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01r9htc13","id-type":"ROR","asserted-by":"publisher"}],"name":"Universit\u00e9 Libre de Bruxelles","place":["Brussels, Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0159-6495","authenticated-orcid":false,"given":"Valerie","family":"Gilchrist","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01r9htc13","id-type":"ROR","asserted-by":"publisher"}],"name":"Universit\u00e9 Libre de Bruxelles","place":["Brussels, Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3482-6743","authenticated-orcid":false,"given":"Christophe","family":"Petit","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01r9htc13","id-type":"ROR","asserted-by":"publisher"}],"name":"Universit\u00e9 Libre de Bruxelles","place":["Brussels, Belgium"]},{"id":[{"id":"https:\/\/ror.org\/03angcq70","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Birmingham","place":["Birmingham, England"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:target","volume-title":"New Public-Key Cryptosystem Blueprints Using Matrix Products\n  in $\\mathbb{F}_p$","author":"Remi Geraud-Stewart","year":"2023"},{"key":"ref2:ref:wagner1984public","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-39568-7_3","article-title":"A Public Key Cryptosystem Based on the Word Problem","volume":"196","author":"Neal R. Wagner","year":"1984"},{"key":"ref3:ref:levy2010security","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/S10623-009-9307-X","article-title":"Security analysis of word problem-based cryptosystems","volume":"54","author":"Fran\u00e7oise Levy-dit-Vehel","year":"2010","journal-title":"Des. Codes Cryptogr."},{"key":"ref4:ref:tillich1994hashing","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-48658-5_5","article-title":"Hashing with SL_2","volume":"839","author":"Jean-Pierre Tillich","year":"1994"},{"key":"ref5:ref:charles2009cryptographic","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic hash functions from expander graphs","volume":"22","author":"Denis X Charles","year":"2009","journal-title":"Journal of CRYPTOLOGY"},{"key":"ref6:det-distrib","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20109","article-title":"On random $\\pm1$ matrices: singularity and determinant","volume":"28","author":"Terence Tao","year":"2006","journal-title":"Random Structures Algorithms"},{"key":"ref7:OEIS","volume-title":"OEIS Foundation Inc.","year":"2024"},{"key":"ref8:vOW","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","article-title":"Parallel Collision Search with Cryptanalytic Applications","volume":"12","author":"Paul C. van Oorschot","year":"1999","journal-title":"J. Cryptol."}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T16:28:44Z","timestamp":1733848124000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":8,"URL":"https:\/\/doi.org\/10.62056\/avrxrudhdj","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-118"}}