Abstract
For a subspace W of a vector space V of dimension n, the Schur-product space \(W^{\left\langle k \right\rangle }\) for \(k \in {\mathbb {N}}\) is defined to be the span of all vectors formed by the component-wise multiplication of k vectors in W. It is well known that repeated applications of the Schur product to the subspace W creates subspaces \(W, W^{\left\langle 2 \right\rangle }, W^{\left\langle 3 \right\rangle }, \ldots \) whose dimensions are monotonically non-decreasing. However, quantifying the structure and growth of such spaces remains an important open problem with applications to cryptography and coding theory. This paper characterizes how increasing powers of constacyclic codes grow under the Schur product and gives necessary and sufficient criteria for when powers of the code and/or the dimension of the code are invariant under the Schur product.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aguilar-Melchor C., Blazy O., Deneuville J., Gaborit P., Zémor G.: Efficient encryption from random quasi-cyclic codes. IEEE Trans. Inf. Theory 64(5), 3927–3943 (2018).
Aydin N., Halilovi A.: A generalization of quasi-twisted codes: multi-twisted codes. Finite Fields Appl. 45, 96–106 (2017).
Aydin N., Siap I., Ray-Chaudhuri D.K.: The structure of 1-generator quasi-twisted codes and new linear codes. Des. Codes Cryptogr. 24(3), 313–326 (2001).
Aydin N., Siap I., Ray-Chaudhuri D.K.: The structure of 1-generator quasi-twisted codes and new linear codes. Des. Codes Cryptogr. 24, 313–326 (2001).
Aydin N., Asamov T., Gulliver T.A.: Some open problems on quasi-twisted and related code constructions and good quaternary codes. In: Proceedings of IEEE ISIT’ 2007, Nice, France (2007).
Banegas G., Barreto P.S.L.M., Boidje B.O., Cayrel P.L., Dione G.N., Gaj K., Gueye C.T., Haeussler R., Klamti J.B., N’diaye O., Nguyen D.T., Persichetti E., Ricardini J.E.: DAGS: Key encapsulation using dyadic GS codes. Cryptology ePrint Archive. Report 2017/1037 (2017).
Barelli E., Couvreur A.: An efficient structural attack on NIST submission DAGS. CoRR. arXiv:1805.05429 (2018).
Berger T.P., Loidreau P.: How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr. 35(1), 63–79 (2005).
Berger T.P., Cayrel P.L., Gaborit P., Otmani A.: Reducing key length of the McEliece cryptosystem. In: AFRICACRYPT, pp. 77–97. Springer, Berlin (2009).
Berlekamp E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968).
Cascudo I.: On squares of cyclic codes. IEEE Trans. Inf. Theory 65(2), 1034–1047 (2018).
Cascudo I., Chen H., Cramer R., Xing C.: Asymptotically good ideal linear secret sharing with strong multiplication over any fixed finite field. In: Halevi S. (ed.) CRYPTO, pp. 1–21. Springer, Heidelberg (2009).
Cascudo I., Cramer R., Mirandola D., Zémor G.: Squares of random linear codes. IEEE Trans. Inf. Theory 61(3), 1159–1173 (2015).
Cascudo I., Gundersen J.S., Ruano D.: Squares of matrix-product codes. CoRR. arXiv:1903.05494 (2019).
Couvreur A., Gaborit P., Gauthier-Umaña V., Otmani A., Tillich J.P.: Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes. Des. Codes Cryptogr. 74, 641–666 (2014).
Couvreur A., Otmani A., Tillich J.P.: Polynomial time attack on wild McEliece over quadratic extensions. IEEE Trans. Inf. Theory 63(1), 404–427 (2017).
Couvreur A., Lequesne M., Tillich J.: Recovering short secret keys of RLCE in polynomial time. arXiv:1805.11489 (2018).
Cramer R., Damgård I., Maurer U.: General secure multi-party computation from any linear secret-sharing scheme. In: EUROCRYPT, pp. 316–334. Springer, Heidelberg (2000).
Cramer R., Damgård I., Nielsen J.B.: Secure Multiparty Computation and Secret Sharing—An Information Theoretic Appoach. Cambridge University Press, Cambridge (2015).
Faugère J.C., Otmani A., Perret L., Tillich J.P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert H. (ed.) EUROCRYPT, pp. 279–298. Springer, Berlin (2010).
Faugère J.C., Gauthier-Umaña V., Otmani A., Perret L., Tillich J.P.: A distinguisher for high-rate McEliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830–6844 (2013).
Faure C., Minder L.: Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes. In: Proceedings of the 11th international workshop on Algebraic and Combinatorial Coding Theory, ACCT, vol. 2008, pp. 99–107 (2008).
Jia Y.: On quasi-twisted codes over finite fields. Finite Fields Appl. 18, 237–257 (2012).
Lim C.J.: Quasi-cyclic codes with cyclic constituent codes. Finite Fields Appl. 13(3), 516–534 (2007).
Ling S., Solé P.: On the algebraic structure of quasi-cyclic codes. I. Finite fields. IEEE Trans. Inf. Theory 47(7), 2751–2760 (2001).
Lyubashevsky V., Peikert C., Regev O.: A toolkit for ring-LWE cryptography. In: EUROCRYPT, pp. 35–54. Springer, Heidelberg (2013).
McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42–44, 114–116 (1978).
Micciancio D., Regev O.: Lattice-Based Cryptography, pp. 147–191. Springer, Berlin (2009).
Minder L., Shokrollahi A.: Cryptanalysis of the Sidelnikov cryptosystem. In: EUROCRYPT, pp. 347–360. Springer, Heidelberg (2007).
Mirandola D.: Schur products of linear codes: a study of parameters. PhD Thesis, Universite de Bordeaux 1 (2012).
Niederreiter H.: Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theory 15(2), 159–166 (1986).
Otmani A., Tillich J.P., Dallot L.: Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes. Math. Comput. Sci. 3(2), 129–140 (2010).
Pellikaan R., Márquez-Corbella I.: Error-correcting pairs for a public-key cryptosystem. J. Phys. Conf. Ser. 855(1), 012–032 (2017).
Radkova D., Bojilov A., Zanten A.J.V.: Cyclic codes and quasi-twisted codes: an algebraic approach. Sofia University, Tech. Rep. (2007).
Randriambololona H.: On Products and Powers of Linear Codes Under Componentwise Multiplication. Contemporary Mathematics, vol. 637. American Mathematical Society, Providence (2015).
Sidelnikov V.M.: A public-key cryptosystem based on binary Reed–Muller codes. Discret. Math. Appl. 4(3), 191–208 (1994).
Wang Y.: Quantum resistant random linear code based public key encryption scheme rlce. In: ISIT, pp. 2519–2523 (2016).
Wieschebrink C.: Two NP-complete problems in coding theory with an application in code based cryptography. In: ISIT, pp. 1733–1737 (2006).
Wieschebrink C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: Post-Quantum Cryptography, pp. 61–72 (2010).
Acknowledgements
This work was supported by the National Science Foundation under grants no. CNS-1651344 and CNS-1513671. Heninger and Rudow carried out this research while at the University of Pennsylvania.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by V. A. Zinoviev.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Falk, B.H., Heninger, N. & Rudow, M. Properties of constacyclic codes under the Schur product. Des. Codes Cryptogr. 88, 993–1021 (2020). https://doi.org/10.1007/s10623-020-00720-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00720-3