American Institute of Mathematical Sciences

Advanced
May  2021, 15(2): 219-226. 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  May 2021 Early access  January 2020

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, 2021, 15 (2) : 219-226. 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.

[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. 

[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.

[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.

[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.

[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.

[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.

[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. 
[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.

[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.

[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.

[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.

[13]

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

[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.

[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.

[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.

[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.

[18]

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

[19]

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

[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.

[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.

[22]

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

[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.

[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.

[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.

[26]

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

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.

[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. 

[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.

[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.

[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.

[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.

[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.

[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. 
[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.

[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.

[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.

[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.

[13]

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

[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.

[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.

[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.

[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.

[18]

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

[19]

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

[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.

[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.

[22]

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

[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.

[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.

[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.

[26]

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

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]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[2]

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
[3]

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
[4]

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
[5]

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
[6]

Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022  doi: 10.3934/jdg.2022010
[7]

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
[8]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[9]

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

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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[11]

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

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[20]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (272)
  • HTML views (612)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy