Squares of matrix-product codes

DOI10.1016/J.FFA.2019.101606MaRDI QIDQ2302565zbMATH OpenOpenAlexFDO

Authors Ignacio Cascudo, Jaron Skovsted Gundersen, Diego Ruano

Publication date 26 February 2020

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.05494

zbMATH Keywords

component-wise productlinear codesmatrix-product codesSchur productsquare of codes

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Authentication, digital signatures and secret sharing (94A62) Linear codes (general theory) (94B05)

Abstract: The component-wise or Schur product $C\ast C^{\prime }$ of two linear error correcting codes $C$ and $C^{\prime }$ over certain finite field is the linear code spanned by all component-wise products of a codeword in $C$ with a codeword in $C^{\prime }$. When $C=C^{\prime }$, we call the product the square of $C$ and denote it $C^{\ast 2}$. Motivated by several applications of squares of linear codes in the area of cryptography, in this paper we study squares of so-called matrix-product codes, a general construction that allows to obtain new longer codes from several "constituent" codes. We show that in many cases we can relate the square of a matrix-product code to the squares and products of their constituent codes, which allow us to give bounds or even determine its minimum distance. We consider the well-known $(u,u+v)$-construction, or Plotkin sum (which is a special case of a matrix-product code) and determine which parameters we can obtain when the constituent codes are certain cyclic codes. In addition, we use the same techniques to study the squares of other matrix-product codes, for example when the defining matrix is Vandermonde (where the minimum distance is in a certain maximal with respect to matrix-product codes).

Review text

Given two linear codes \(C\) and \(C'\) the Schur product is defined by \[ C*C'=\left\langle\{c*c'\mid c\in C, c' \in C'\}\right\rangle, \] where \(c*c'=(c_1c_1',\ldots,c_nc_n')\). It is well know that for some cryptographic applications, private information retrieval or multiparty computations among others, the knowledge of \(C*C'\) is of particular interest. In certain protocols for multiparty computations, both a large minimum distance for \(C^{*2}=C*C\) and a large dimension for \(C\) are required. Depending on the protocol, sometimes a large minimum distance for \(C^{\perp}\) is also demanded. According to previous motivations, they study the structure of \(C^{*2}\) when the code \(C\) is a matrix product code. In the particular case of the \((u,u+v)\)-construction, they provide a lower bound for the minimum distance which is sharp in case that the codes used in the \((u,u+v)\)-construction are nested. Furthermore, when the constituent codes of the \((u,u+v)\)-construction are binary cyclic codes they use the cyclotomic coset to control at the same time the dimension of \(C\) and a lower bound of the minimum distance of \(C\) and \(C^{*2}\), actually they notice that considering large cyclotomic cosets one can obtain the desired codes. They are able to obtain new codes with large dimension of \(C\) and large minimum distance of \(C^{*2}\) simultaneously. Finally they study matrix-product codes where the defining matrix \(A\) is a Vandermonde matrix. Thanks to it, they can provide a better algebraic structure for \(C^{*2}\), i.e., \(C^{*2}\) is also a matrix-product code and a formula for the dimension and a lower bound for the minimum distance are given. In the particular case where the constituent codes of the matrix-product code are AG-codes, then more precise parameters are given.

Recommendations

• Construction and bound on the performance of matrix-product codes
• Matrix product codes over finite commutative Frobenius rings
• High dimensional affine codes whose square has a designed minimum distance
• Matrix product codes over \(\mathbb{F}_p\)
• Matrix-product codes over finite chain rings

Cites work

• Algebraic structure of quasicyclic codes
• An Upper Bound of Singleton Type for Componentwise Products of Linear Codes
• Asymptotically Good Binary Linear Codes With Asymptotically Good Self-Intersection Spans
• Committed MPC -- maliciously secure multiparty computation from homomorphic commitments
• Constant-overhead secure computation of Boolean circuits using preprocessing
• Construction and decoding of matrix-product codes from nested codes
• Critical Pairs for the Product Singleton Bound
• Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• Cryptanalysis of the Sidelnikov Cryptosystem
• Efficient UC commitment extension with homomorphism for free (and applications)
• Error-locating pairs for cyclic codes
• General secure multi-party computation from any linear secret-sharing scheme
• scientific article; zbMATH DE number 125903 (Why is no real title available?)
• Matrix-product codes over \(\mathbb{F}_q\)
• New linear codes from matrix-product codes with polynomial units
• Note on Niederreiter-Xing's propagation rule for linear codes
• On decoding by error location and dependent sets of error positions
• On products and powers of linear codes under componentwise multiplication
• On Squares of Cyclic Codes
• Polynomial Time Attack on Wild McEliece Over Quadratic Extensions
• Private information retrieval from coded databases with colluding servers
• Secure multiparty computation and secret sharing
• Squares of Random Linear Codes
• The TinyTable protocol for 2-party secure computation, or: Gate-scrambling revisited

Cited in

(13)

• A coding theory bound and zero-sum square matrices
• Properties of constacyclic codes under the Schur product
• Construction and bound on the performance of matrix-product codes
• DECODING OF MATRIX-PRODUCT CODES
• Evaluation codes associated to some matrices
• scientific article; zbMATH DE number 7727673 (Why is no real title available?)
• On dual-containing, almost dual-containing matrix-product codes and related quantum codes
• An algebraic characterization of binary CSS-T codes and cyclic CSS-T codes for quantum fault tolerance
• Four families of squares of BCH codes and their complements
• Constructions of LCD codes from their Schur products
• Some results on Schur powers and cubes of primitive narrow-sense BCH codes
• The Schur products of some binary LCD BCH codes
• High dimensional affine codes whose square has a designed minimum distance

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: Squares of matrix-product codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302565)