-
Previous Article
Construction of minimal linear codes from multi-variable functions
- AMC Home
- This Issue
-
Next Article
Encryption scheme based on expanded Reed-Solomon codes
On the dimension of the subfield subcodes of 1-point Hermitian codes
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 |
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.
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. 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. |
[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. 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. |
[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. |
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 |
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 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]