Monomial Isomorphism for Tensors and Applications to Code Equivalence Problems

Giuseppe D'Alconzo

Paper 2023/396

Monomial Isomorphism for Tensors and Applications to Code Equivalence Problems

Giuseppe D'Alconzo

, Polytechnic University of Turin

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 (CE $_{s r}$ ) to the rank metric (CE $_{r k}$ ). To obtain this result, we investigate reductions between tensor problems. We define the Monomial Isomorphism problem for $d$ -tensors ( $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 CE $_{s r}$ to CE $_{r k}$ . 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 CE.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Designs, Codes and Cryptography
DOI: 10.1007/s10623-024-01375-0
Keywords: Code Equivalence Sum-Rank Metric Rank Metric Tensor Isomorphism Matrix Code Equivalence
Contact author(s): giuseppe dalconzo @ polito it
History: 2024-09-19: last of 2 revisions; 2023-03-20: received; See all versions
Short URL: https://ia.cr/2023/396
License: CC BY

BibTeX

@misc{cryptoeprint:2023/396,
      author = {Giuseppe D'Alconzo},
      title = {Monomial Isomorphism for Tensors and Applications to Code Equivalence Problems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/396},
      year = {2023},
      doi = {10.1007/s10623-024-01375-0},
      url = {https://eprint.iacr.org/2023/396}
}