Starting from the problem of d-tensor isomorphism (d-TI), we study the relation between various code equivalence problems in different metrics. In particular, we show a reduction from the sum-rank metric (CEsr) to the rank metric (CErk). To obtain this result, we investigate reductions between tensor problems. We define the monomial isomorphism problem for dtensors (d-TI∗), where, given two d-tensors, we ask if there are d −1 invertible matrices and a monomial matrix sending one tensor into the other. We link this problem to the well-studied d-TI and the TI-completeness of d-TI∗ is shown. Due to this result, we obtain a reduction from CEsr to CErk. In the literature, a similar result was known, but it needs an additional assumption on the automorphisms of matrix codes. Since many constructions based on the hardness of Code Equivalence problems are emerging in cryptography, we analyze how such reductions can be taken into account in the design of cryptosystems based on CEsr.

Monomial isomorphism for tensors and applications to code equivalence problems / D’Alconzo, Giuseppe. - In: DESIGNS, CODES AND CRYPTOGRAPHY. - ISSN 0925-1022. - (2024). [10.1007/s10623-024-01375-0]

Monomial isomorphism for tensors and applications to code equivalence problems

D’Alconzo, Giuseppe
2024

Abstract

Starting from the problem of d-tensor isomorphism (d-TI), we study the relation between various code equivalence problems in different metrics. In particular, we show a reduction from the sum-rank metric (CEsr) to the rank metric (CErk). To obtain this result, we investigate reductions between tensor problems. We define the monomial isomorphism problem for dtensors (d-TI∗), where, given two d-tensors, we ask if there are d −1 invertible matrices and a monomial matrix sending one tensor into the other. We link this problem to the well-studied d-TI and the TI-completeness of d-TI∗ is shown. Due to this result, we obtain a reduction from CEsr to CErk. In the literature, a similar result was known, but it needs an additional assumption on the automorphisms of matrix codes. Since many constructions based on the hardness of Code Equivalence problems are emerging in cryptography, we analyze how such reductions can be taken into account in the design of cryptosystems based on CEsr.
File in questo prodotto:
File Dimensione Formato  
s10623-024-01375-0.pdf

accesso aperto

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Creative commons
Dimensione 430.74 kB
Formato Adobe PDF
430.74 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2986946