×

zbMATH — the first resource for mathematics

Squares of matrix-product codes. (English) Zbl 07174346
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.

MSC:
94B05 Linear codes, general
94A62 Authentication, digital signatures and secret sharing
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Software:
McEliece
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi, Completeness theorems for non-cryptographic fault-tolerant distributed computation, (Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC ’88 (1988), ACM), 1-10
[2] Blackmore, Tim; Norton, Graham H., Matrix-product codes over Fq, Appl. Algebra Eng. Commun. Comput., 12, 6, 477-500 (Dec. 2001)
[3] Cascudo, Ignacio, On squares of cyclic codes, IEEE Trans. Inf. Theory, 65, 2, 1034-1047 (Feb. 2019)
[4] Cascudo, Ignacio; Cramer, Ronald; Mirandola, Diego; Zemor, Gilles, Squares of random linear codes, IEEE Trans. Inf. Theory, 61, 1159-1173 (Mar. 2015)
[5] Cascudo, Ignacio; Damgård, Ivan; Machado David, Bernardo; Döttling, Nico; Dowsley, Rafael; Giacomelli, Irene, Efficient UC commitment extension with homomorphism for free (and applications), (Advances in Cryptology - ASIACRYPT 2019 (2019), Springer International Publishing: Springer International Publishing Cham)
[6] Chaum, David; Crépeau, Claude; Damgård, Ivan, Multiparty unconditionally secure protocols, (Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC ’88 (1988), ACM), 11-19
[7] Couvreur, Alain; Márquez-Corbella, Irene; Pellikaan, Ruud, Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes, IEEE Trans. Inf. Theory, 63, 8, 5404-5418 (2017) · Zbl 1372.94418
[8] Couvreur, Alain; Otmani, Ayoub; Tillich, Jean-Pierre, Polynomial time attack on wild McEliece over quadratic extensions, IEEE Trans. Inf. Theory, 63, 1, 404-427 (Jan. 2017)
[9] Cramer, Ronald; Damgård, Ivan; Maurer, Ueli, General secure multi-party computation from any linear secret-sharing scheme, (Advances in Cryptology — EUROCRYPT 2000 (2000), Springer: Springer Berlin Heidelberg), 316-334 · Zbl 1082.94515
[10] Cramer, Ronald; Bjerre Damgård, Ivan; Buus Nielsen, Jesper, Secure Multiparty Computation and Secret Sharing (2015), Cambridge University Press · Zbl 1322.68003
[11] Damgård, Ivan; Buus Nielsen, Jesper; Nielsen, Michael; Ranellucci, Samuel, The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited, (Advances in Cryptology - CRYPTO 2017 (2017), Springer International Publishing: Springer International Publishing Cham), 167-187 · Zbl 1407.94099
[12] Damgård, Ivan; Zakarias, Sarah, Constant-Overhead Secure Computation of Boolean Circuits Using Preprocessing, 621-641 (2013), Heidelberg: Springer: Heidelberg: Springer Berlin · Zbl 1315.94068
[13] Duursma, Iwan M.; Kötter, Ralf, Error-locating pairs for cyclic codes, IEEE Trans. Inf. Theory, 40, 1108-1121 (Aug. 1994)
[14] Frederiksen, Tore K.; Pinkas, Benny; Yanai, Avishay, Committed MPC, (Public-Key Cryptography - PKC 2018 (2018), Springer International Publishing), 587-619 · Zbl 1441.94078
[15] Freij-Hollanti, Ragnar; Gnilke, Oliver W.; Hollanti, Camilla; Karpuk, David A., Private information retrieval from coded databases with colluding servers, SIAM J. Appl. Algebra Geom., 1, 1, 647-664 (2017) · Zbl 1386.68049
[16] Hernando, Fernando; Lally, Kristine; Ruano, Diego, Construction and decoding of matrix-product codes from nested codes, Appl. Algebra Eng. Commun. Comput., 20, 5, 497-507 (Oct. 2009)
[17] Hernando, Fernando; Ruano, Diego, New linear codes from matrix-product codes with polynomial units, Adv. Math. Commun., 4, 363 (2009) · Zbl 1213.94176
[18] Lally, Kristine; Fitzpatrick, Patrick, Algebraic structure of quasicyclic codes, Discrete Appl. Math.Coding and Cryptology, 111, 1, 157-175 (2001) · Zbl 1023.94014
[19] Minder, Lorenz; Shokrollahi, Amin, Cryptanalysis of the Sidelnikov cryptosystem, (Advances in Cryptology - EUROCRYPT 2007 (2007), Springer: Springer Berlin Heidelberg), 347-360 · Zbl 1141.94365
[20] Mirandola, Diego; Zémor, Gilles, Critical pairs for the product singleton bound, IEEE Trans. Inf. Theory, 61, 4928-4937 (June 2015)
[21] Özbudak, Ferruh; Stichtenoth, Henning, Note on Niederreiter-Xing’s propagation rule for linear codes, Appl. Algebra Eng. Commun. Comput., 13, 1, 53-56 (Apr. 2002)
[22] Pellikaan, Ruud, On decoding by error location and dependent sets of error positions, Discrete Math., 106-107, 369-381 (1992) · Zbl 0754.94018
[23] Pellikaan, Ruud; Márquez-Corbella, Irene, Error-correcting pairs for a public-key cryptosystem, J. Phys. Conf. Ser., 855 (June 2017)
[24] Randriambololona, Hugues, An upper bound of singleton type for componentwise products of linear codes, IEEE Trans. Inf. Theory, 59, 7936-7939 (Sept. 2013)
[25] Randriambololona, Hugues, Asymptotically good binary linear codes with asymptotically good self-intersection spans, IEEE Trans. Inf. Theory, 59, 3038-3045 (May 2013)
[26] Randriambololona, Hugues, On products and powers of linear codes under componentwise multiplication, Contemp. Math., 637 (Apr. 2015)
[27] Wieschebrink, Christian, Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes, (Post-Quantum Cryptography (2010), Springer: Springer Berlin Heidelberg), 61-72 · Zbl 1284.94124
[28] Yang, Kyeongcheol; Vijay Kumar, P., On the true minimum distance of Hermitian codes, (Coding Theory and Algebraic Geometry (1992), Springer: Springer Berlin Heidelberg), 99-107 · Zbl 0763.94023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.