American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020054

On the dimension of the subfield subcodes of 1-point Hermitian codes

Sabira El Khalfaoui 1,2, and  Gábor P. Nagy 1,2,

1. 

Bolyai Institute of the University of Szeged, Aradi vértanúk tere 1, H-6720 Szeged, Hungary
2. 

Department of Algebra of the Budapest University of Technology and Economics, Egry József utca 1, H-1111 Budapest, Hungary

Received  June 2019 Revised  September 2019 Published  January 2020

Fund Project: Support provided from the National Research, Development and Innovation Fund of Hungary, financed under the 2018-1.2.1-NKP funding scheme, within the SETIT Project (2018-1.2.1-NKP-2018-00004). Partially supported by NKFIH-OTKA Grants 119687 and 115288

Subfield subcodes of algebraic-geometric codes are good candidates for the use in post-quantum cryptosystems, provided their true parameters such as dimension and minimum distance can be determined. In this paper we present new values of the true dimension of subfield subcodes of $ 1 $–point Hermitian codes, including the case when the subfield is not binary.

Keywords: AG code, Hermitian code, subfield subcode.
Mathematics Subject Classification: Primary: 11T71, 14G50; Secondary: 94B27.
Citation: Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, doi: 10.3934/amc.2020054
References:
[1]

D. Augot, M. Barbier and A. Couvreur, List-decoding of binary Goppa codes up to the binary Johnson bound, 2011 IEEE Information Theory Workshop, (2011), 229–233. doi: 10.1109/ITW.2011.6089384.  Google Scholar

[2]

M. Baldi, LDPC codes in the McEliece cryptosystem: Attacks and countermeasures, Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., IOS, Amsterdam, 23 (2009), 160-174.   Google Scholar

[3]

D. J. Bernstein, List decoding for binary Goppa codes, Coding and Cryptology, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6639 (2011), 62-80.  doi: 10.1007/978-3-642-20901-7_4.  Google Scholar

[4]

D. J. Bernstein, T. Lange and C. Peters, Attacking and defending the McEliece cryptosystem, Post-quantum cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5299 (2008), 31-46.  doi: 10.1007/978-3-540-88403-3_3.  Google Scholar

[5]

N. T. Courtois, M. Finiasz and N. Sendrier, How to achieve a McEliece-based digital signature scheme, Advances in Cryptology–ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., Springer, Berlin, 2248 (2001), 157–174. doi: 10.1007/3-540-45682-1_10.  Google Scholar

[6]

P. Delsarte, On subfield subcodes of modified Reed-Solomon codes, IEEE Trans. Information Theory, IT-21 (1975), 575-576.  doi: 10.1109/tit.1975.1055435.  Google Scholar

[7]

M. Elia, E. Viterbo and G. Bertinetti, Decoding of binary separable Goppa codes using Berlekamp-Massey algorithm, Electronics Letters, 35 (1999), 1720-1721.  doi: 10.1049/el:19991190.  Google Scholar

[8] J. W. P. Hirschfeld, G. Korchmáros and F. Torres, Algebraic Curves Over a Finite Field, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2008.   Google Scholar
[9]

T. Hoholdt and R. Pellikaan, On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory, 41 (1995), 1589-1614.  doi: 10.1109/18.476214.  Google Scholar

[10]

Y. X. Li, R. H. Deng and X. M. Wang, On the equivalence of McEliece's and Niederreiter's public-key cryptosystems, IEEE Transactions on Information Theory, 40 (1994), 271-273.  doi: 10.1109/18.272496.  Google Scholar

[11]

P. Loidreau and N. Sendrier, Weak keys in the McEliece public-key cryptosystem, IEEE Trans. Inform. Theory, 47 (2001), 1207-1211.  doi: 10.1109/18.915687.  Google Scholar

[12]

A. J. Menezes, I. F. Blake, X. H. Gao, R. C. Mullin, S. A. Vanstone and T. Yaghoobian, Applications of Finite Fields, The Kluwer International Series in Engineering and Computer Science, 199. Kluwer Academic Publishers, Boston, MA, 1993. doi: 10.1007/978-1-4757-2226-0.  Google Scholar

[13]

R. Misoczki and P. S. Barreto, Compact McEliece keys from Goppa codes, International Workshop on Selected Areas in Cryptography, (2009), 376–392. Google Scholar

[14]

G. P. Nagy and S. El Khalfaoui, HERmitian, Computing with divisors, Riemann-Roch spaces and AG-odes of Hermitian curves, Version 0.1, (2019), GAP package, URL https://github.com/nagygp/Hermitian. Google Scholar

[15]

R. Pellikaan, On the efficient decoding of algebraic-geometric codes, Eurocode'92, CISM Courses and Lect., Springer, Vienna, 339 (1993), 231-253.  doi: 10.1007/978-3-7091-2786-5_20.  Google Scholar

[16]

F. Piñero and H. Janwa, On the subfield subcodes of Hermitian codes, Designs, Codes and Cryptography, 70 (2014), 157-173.  doi: 10.1007/s10623-012-9736-9.  Google Scholar

[17]

S. Sakata, H. E. Jensen and T. Hoholdt, Generalized Berlekamp-Massey decoding of algebraic-geometric codes up to half the Feng-Rao bound, IEEE Transactions on Information Theory, 41 (1995), 1762-1768.  doi: 10.1109/18.476248.  Google Scholar

[18]

S. A. Stepanov, Codes on Algebraic Curves, Kluwer Academic/Plenum Publishers, New York, 1999. doi: 10.1007/978-1-4615-4785-3.  Google Scholar

[19]

H. Stichtenoth, Algebraic Function Fields and Codes, Second edition. Graduate Texts in Mathematics, 254. Springer-Verlag, Berlin, 2009.  Google Scholar

[20]

M. van der Vlugt, The true dimension of certain binary Goppa codes, IEEE Transactions on Information Theory, 36 (1990), 397-398.  doi: 10.1109/18.52487.  Google Scholar

[21]

M. van der Vlugt, On the dimension of trace codes, IEEE Transactions on Information Theory, 37 (1991), 196-199.  doi: 10.1109/18.61140.  Google Scholar

[22]

P. Véron, Goppa codes and trace operator, IEEE Trans. Inform. Theory, 44 (1998), 290-294.  doi: 10.1109/18.651048.  Google Scholar

[23]

P. Véron, True dimension of some binary quadratic trace Goppa codes, Des. Codes Cryptogr., 24 (2001), 81-97.  doi: 10.1023/A:1011281431366.  Google Scholar

[24]

P. Véron, Proof of conjectures on the true dimension of some binary Goppa codes, Des. Codes Cryptogr., 36 (2005), 317-325.  doi: 10.1007/s10623-004-1722-4.  Google Scholar

[25]

C. Wieschebrink, Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 61-72.  doi: 10.1007/978-3-642-12929-2_5.  Google Scholar

[26]

S. Y. Yan, Quantum Attacks on Public-Key Cryptosystems, Springer, 2013. doi: 10.1007/978-1-4419-7722-9.  Google Scholar

show all references

References:
[1]

D. Augot, M. Barbier and A. Couvreur, List-decoding of binary Goppa codes up to the binary Johnson bound, 2011 IEEE Information Theory Workshop, (2011), 229–233. doi: 10.1109/ITW.2011.6089384.  Google Scholar

[2]

M. Baldi, LDPC codes in the McEliece cryptosystem: Attacks and countermeasures, Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., IOS, Amsterdam, 23 (2009), 160-174.   Google Scholar

[3]

D. J. Bernstein, List decoding for binary Goppa codes, Coding and Cryptology, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6639 (2011), 62-80.  doi: 10.1007/978-3-642-20901-7_4.  Google Scholar

[4]

D. J. Bernstein, T. Lange and C. Peters, Attacking and defending the McEliece cryptosystem, Post-quantum cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 5299 (2008), 31-46.  doi: 10.1007/978-3-540-88403-3_3.  Google Scholar

[5]

N. T. Courtois, M. Finiasz and N. Sendrier, How to achieve a McEliece-based digital signature scheme, Advances in Cryptology–ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., Springer, Berlin, 2248 (2001), 157–174. doi: 10.1007/3-540-45682-1_10.  Google Scholar

[6]

P. Delsarte, On subfield subcodes of modified Reed-Solomon codes, IEEE Trans. Information Theory, IT-21 (1975), 575-576.  doi: 10.1109/tit.1975.1055435.  Google Scholar

[7]

M. Elia, E. Viterbo and G. Bertinetti, Decoding of binary separable Goppa codes using Berlekamp-Massey algorithm, Electronics Letters, 35 (1999), 1720-1721.  doi: 10.1049/el:19991190.  Google Scholar

[8] J. W. P. Hirschfeld, G. Korchmáros and F. Torres, Algebraic Curves Over a Finite Field, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2008.   Google Scholar
[9]

T. Hoholdt and R. Pellikaan, On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory, 41 (1995), 1589-1614.  doi: 10.1109/18.476214.  Google Scholar

[10]

Y. X. Li, R. H. Deng and X. M. Wang, On the equivalence of McEliece's and Niederreiter's public-key cryptosystems, IEEE Transactions on Information Theory, 40 (1994), 271-273.  doi: 10.1109/18.272496.  Google Scholar

[11]

P. Loidreau and N. Sendrier, Weak keys in the McEliece public-key cryptosystem, IEEE Trans. Inform. Theory, 47 (2001), 1207-1211.  doi: 10.1109/18.915687.  Google Scholar

[12]

A. J. Menezes, I. F. Blake, X. H. Gao, R. C. Mullin, S. A. Vanstone and T. Yaghoobian, Applications of Finite Fields, The Kluwer International Series in Engineering and Computer Science, 199. Kluwer Academic Publishers, Boston, MA, 1993. doi: 10.1007/978-1-4757-2226-0.  Google Scholar

[13]

R. Misoczki and P. S. Barreto, Compact McEliece keys from Goppa codes, International Workshop on Selected Areas in Cryptography, (2009), 376–392. Google Scholar

[14]

G. P. Nagy and S. El Khalfaoui, HERmitian, Computing with divisors, Riemann-Roch spaces and AG-odes of Hermitian curves, Version 0.1, (2019), GAP package, URL https://github.com/nagygp/Hermitian. Google Scholar

[15]

R. Pellikaan, On the efficient decoding of algebraic-geometric codes, Eurocode'92, CISM Courses and Lect., Springer, Vienna, 339 (1993), 231-253.  doi: 10.1007/978-3-7091-2786-5_20.  Google Scholar

[16]

F. Piñero and H. Janwa, On the subfield subcodes of Hermitian codes, Designs, Codes and Cryptography, 70 (2014), 157-173.  doi: 10.1007/s10623-012-9736-9.  Google Scholar

[17]

S. Sakata, H. E. Jensen and T. Hoholdt, Generalized Berlekamp-Massey decoding of algebraic-geometric codes up to half the Feng-Rao bound, IEEE Transactions on Information Theory, 41 (1995), 1762-1768.  doi: 10.1109/18.476248.  Google Scholar

[18]

S. A. Stepanov, Codes on Algebraic Curves, Kluwer Academic/Plenum Publishers, New York, 1999. doi: 10.1007/978-1-4615-4785-3.  Google Scholar

[19]

H. Stichtenoth, Algebraic Function Fields and Codes, Second edition. Graduate Texts in Mathematics, 254. Springer-Verlag, Berlin, 2009.  Google Scholar

[20]

M. van der Vlugt, The true dimension of certain binary Goppa codes, IEEE Transactions on Information Theory, 36 (1990), 397-398.  doi: 10.1109/18.52487.  Google Scholar

[21]

M. van der Vlugt, On the dimension of trace codes, IEEE Transactions on Information Theory, 37 (1991), 196-199.  doi: 10.1109/18.61140.  Google Scholar

[22]

P. Véron, Goppa codes and trace operator, IEEE Trans. Inform. Theory, 44 (1998), 290-294.  doi: 10.1109/18.651048.  Google Scholar

[23]

P. Véron, True dimension of some binary quadratic trace Goppa codes, Des. Codes Cryptogr., 24 (2001), 81-97.  doi: 10.1023/A:1011281431366.  Google Scholar

[24]

P. Véron, Proof of conjectures on the true dimension of some binary Goppa codes, Des. Codes Cryptogr., 36 (2005), 317-325.  doi: 10.1007/s10623-004-1722-4.  Google Scholar

[25]

C. Wieschebrink, Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 61-72.  doi: 10.1007/978-3-642-12929-2_5.  Google Scholar

[26]

S. Y. Yan, Quantum Attacks on Public-Key Cryptosystems, Springer, 2013. doi: 10.1007/978-1-4419-7722-9.  Google Scholar

Table 1.  Parameters of $ C_{8,2}(s) $ for $ s\in\{256,\ldots,511\} $
$ s $ $ \dim C_{8,2}(s) $ $ \dim \mathcal{H}(64,s) $ $ s $ $ \dim C_{8,2}(s) $ $ \dim \mathcal{H}(64,s) $
256 7 229 456 206 429
288 13 261 457 212 430
292 19 265 458 218 431
320 25 293 460 224 433
324 28 297 462 226 435
328 34 301 464 232 437
336 36 309 466 238 439
352 42 325 468 244 441
356 48 329 470 250 443
360 54 333 472 256 445
364 60 337 473 262 446
368 66 341 474 268 447
376 72 349 475 274 448
378 74 351 480 280 453
384 80 357 482 286 455
392 86 365 484 292 457
400 92 373 486 295 459
402 98 375 488 301 461
408 104 381 489 307 462
410 110 383 490 313 463
416 116 389 491 319 464
418 122 391 492 325 465
420 128 393 493 331 466
424 134 397 496 337 469
428 140 401 498 343 471
432 146 405 500 349 473
434 152 407 502 355 475
436 158 409 504 361 477
438 164 411 505 367 478
440 170 413 506 373 479
442 176 415 507 379 480
444 182 417 508 385 481
448 188 421 509 391 482
450 194 423 510 397 483
452 200 425 511 403 484
Table Options

Download as excel

$ s $ $ \dim C_{8,2}(s) $ $ \dim \mathcal{H}(64,s) $ $ s $ $ \dim C_{8,2}(s) $ $ \dim \mathcal{H}(64,s) $
256 7 229 456 206 429
288 13 261 457 212 430
292 19 265 458 218 431
320 25 293 460 224 433
324 28 297 462 226 435
328 34 301 464 232 437
336 36 309 466 238 439
352 42 325 468 244 441
356 48 329 470 250 443
360 54 333 472 256 445
364 60 337 473 262 446
368 66 341 474 268 447
376 72 349 475 274 448
378 74 351 480 280 453
384 80 357 482 286 455
392 86 365 484 292 457
400 92 373 486 295 459
402 98 375 488 301 461
408 104 381 489 307 462
410 110 383 490 313 463
416 116 389 491 319 464
418 122 391 492 325 465
420 128 393 493 331 466
424 134 397 496 337 469
428 140 401 498 343 471
432 146 405 500 349 473
434 152 407 502 355 475
436 158 409 504 361 477
438 164 411 505 367 478
440 170 413 506 373 479
442 176 415 507 379 480
444 182 417 508 385 481
448 188 421 509 391 482
450 194 423 510 397 483
452 200 425 511 403 484
[1]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281
[2]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[3]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[4]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[5]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[6]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[7]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[8]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[9]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261
[10]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[11]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020058
[12]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[13]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027
[14]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[15]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[16]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013
[17]

Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z4. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017
[18]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046
[19]

Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029
[20]

Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (9)
  • HTML views (30)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences