Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 8/2020

03-07-2020

High dimensional affine codes whose square has a designed minimum distance

Authors: Ignacio García-Marco, Irene Márquez-Corbella, Diego Ruano

Published in: Designs, Codes and Cryptography | Issue 8/2020

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Given a linear code \({\mathcal {C}}\), its square code \({\mathcal {C}}^{(2)}\) is the span of all component-wise products of two elements of \({\mathcal {C}}\). Motivated by applications in multi-party computation, our purpose with this work is to answer the following question: which families of affine variety codes have simultaneously high dimension \(k({\mathcal {C}})\) and high minimum distance of \({\mathcal {C}}^{(2)}\), \(d({\mathcal {C}}^{(2)})\)? More precisely, given a designed minimum distance d we compute an affine variety code \({\mathcal {C}}\) such that \(d({\mathcal {C}}^{(2)})\ge d\) and the dimension of \({\mathcal {C}}\) is high. The best constructions we propose mostly come from hyperbolic codes. Nevertheless, for small values of d, they come from weighted Reed–Muller codes.
previous article Steane-enlargement of quantum codes from the Hermitian function field
next article Monomial-Cartesian codes and their duals, with applications to LCD codes, quantum codes, and locally recoverable codes
Appendix
Available only for authorised users
Literature
1.
Ben-Or M., Goldwasser S., Wigderson A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pp. 1–10, NY, USA (1988).
2.
3.
Cascudo I., Cramer R., Mirandola D., Zémor G.: Squares of random linear codes. IEEE Trans. Inf. Theory 61(3), 1159–1173 (2015).MathSciNetCrossRef
4.
5.
Chaum D., Crépeau C., Damgård I.: Multiparty unconditionally secure protocols. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pp. 11–19, NY, USA (1988).
6.
Cramer R., Damgård I., Maurer U.: General secure multi-party computation from any linear secret-sharing scheme. In: Advances in cryptology EUROCRYPT 2000 (Bruges), volume 1807 of Lecture Notes in Comput. Sci., pp. 316–334. Springer, Berlin (2000).
7.
Cramer R., Damgård I., Nielsen J.B.: Secure Multiparty Computation and Secret Sharing, 1st edn. Cambridge University Press, New York (2015).CrossRef
8.
Damgård I., Zakarias S.: Constant-overhead secure computation of boolean circuits using preprocessing. In: Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC’13, pp. 621–641, Springer, Berlin (2013).
9.
Damgård I., Nielsen J.B., Nielsen M., Ranellucci S.: The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited. In: Advances in cryptology CRYPTO 2017. Part I, volume 10401 of Lecture Notes in Comput. Sci., pp. 167–187. Springer, Cham (2017).
10.
Feng G.-L., Rao T.R.N.: Improved geometric Goppa codes. I. Basic theory. Special issue on algebraic geometry codes. IEEE Trans. Inf. Theory 41(6), 1678–1693 (1995).CrossRef
11.
Fitzgerald J., Lax R.F.: Decoding affine variety codes using Gröbner bases. Des. Codes Cryptogr. 13, 147–158 (1998).MathSciNetCrossRef
12.
Galindo C., Hernando F., Ruano D.: Stabilizer quantum codes from \(J\)-affine variety codes and a new Steane-like enlargement. Quantum Inf. Process. 14(9), 3211–3231 (2015).MathSciNetCrossRef
13.
14.
Geil O., Høholdt T.: Footprints or generalized Bezout’s theorem. IEEE Trans. Inf. Theory 46(2), 635–641 (2000).MathSciNetCrossRef
15.
Geil O., Høholdt T.: On hyperbolic codes. Applied algebra, algebraic algorithms and error-correcting codes (Melbourne, 2001), pp. 159–171, Lecture Notes in Comput. Sci., 2227, Springer, Berlin (2001).
16.
Martínez-Bernal J., Pitones Y., Villarreal R.H.: Minimum distance functions of complete intersections. J. Algebra Appl. 17(11), 1850204 (2018).MathSciNetCrossRef
17.
Pellikaan R.: On decoding by error location and dependent sets of error positions. Discret. Math. 106–107, 369–381 (1992).MathSciNetCrossRef
18.
Randriambololona H.: Asymptotically good binary linear codes with asymptotically good self-intersection spans. IEEE Trans. Inf. Theory 59(5), 3038–3045 (2013).MathSciNetCrossRef
19.
Randriambololona H.: On products and powers of linear codes under component wise multiplication. In: Algorithmic Arithmetic, Geometry and Coding Theory, volume 637 of Contemp. Math., pp. 3-78, Amer. Math. Soc., Providence, RI (2015).
20.
Sørensen A.B.: Weighted Reed-Muller codes and algebraic-geometric codes. IEEE Trans. Inf. Theory 38(6), 1821–1826 (1992).MathSciNetCrossRef
Metadata
Title
High dimensional affine codes whose square has a designed minimum distance
Authors
Ignacio García-Marco
Irene Márquez-Corbella
Diego Ruano
Publication date
03-07-2020
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 8/2020
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-020-00764-5

Other articles of this Issue 8/2020

Designs, Codes and Cryptography 8/2020 Go to the issue

OriginalPaper

Weierstrass semigroup at rational points in maximal curves which cannot be covered by the Hermitian curve

OriginalPaper

Computing sharp recovery structures for locally recoverable codes

OriginalPaper

Steane-enlargement of quantum codes from the Hermitian function field

OriginalPaper

Construction of self-dual matrix codes

OriginalPaper

Hamming and simplex codes for the sum-rank metric

OriginalPaper

Power error locating pairs

Premium Partner

    Image Credits