Algebraic geometric codes with applications

Abstract

The theory of linear error-correcting codes from algebraic geometric curves (algebraic geometric (AG) codes or geometric Goppa codes) has been well-developed since the work of Goppa and Tsfasman, Vladut, and Zink in 1981–1982. In this paper we introduce to readers some recent progress in algebraic geometric codes and their applications in quantum error-correcting codes, secure multi-party computation and the construction of good binary codes.

Keywords

algebraic geometric (AG) code / algebraic curve / quantum error-correcting codes / multi-party computation (MPC)

References

[1] Shannon C. E. A mathematical theory of communication. Bell Syst Tech J, 1948, 27: 379-423.

[2] Hamming R. W. Error detecting and error correcting codes. Bell Syst Tech J, 1950, 29: 147-160.

[3] MacWilliams F. J., Sloane N. J. A. The Theory of Error-correcting Codes, 1977, Amsterdam: North-Holland.

[4] van Lint J. H. Introduction to Coding Theory, 1999 3rd ed. Berlin: Springer-Verlag.

[5] Wan Z. X. Algebra and Coding, 1977, Beijing: Science Press.

[6] Goppa V. D. Codes on algebraic curves. Soviet Math Dokl, 1981, 24: 170-172.

[7] Hoeholdt T., van Lint J. H., Pellikaan R. Pless V. S., Huffman W. C., Brualdi R. A. Algebraic geometry codes. Handbook of Coding Theory, 1998, Amsterdam: Elsevier Science Publishers.

[8] van Lint J. H. Ray-Chaudhuri D. Algebraic geometric codes. Coding Theory and Design Theory I, 1990, Berlin: Springer-Verlag.

[9] Stichtenoth H. Algebraic Function Fields and Codes, 1993, Berlin: Springer.

[10] Niederreiter H., Xing C. Rational Points on Curves over Finite Fields: Theory and Applications, 2001, Cambridge: Cambridge University Press.

[11] Tsfasman M. A., Vladut S. G. Algebraic-geometric Codes, 1991, Dordrecht: Kluwer.

[12] Gacia A., Stichtenoth H. A tower of Artin-Schreier extension of function fields attaining Drinfeld-Vladut bound. Invent Math, 1995, 121(1): 211-222.

[13] Tsfasman M. A., Vladut S. G., Zink T. Modular curves, Shimura curves and Goppa codes, better than Varshamov-Gilbert bound. Math Nachrichten, 1982, 109: 21-28.

[14] Feng G.-L., Rao T. R. N. Decoding of algebraic geometric codes up to design minimum distances. IEEE Trans Inform Theory, 1993, 39: 37-45.

[15] Chen H. Some good quantum error-correcting codes from algebraic-geometric codes. IEEE Trans Inform Theory, 2001, 47(5): 2059-2061.

[16] Chen H., Ling S., Xing C. Asymptotically good quantum codes exceeding the Ashikhmin-Litsyn-Tsfasman bound. IEEE Trans Inform Theory, 2001, 47(5): 2055-2058.

[17] Feng K. Quantum codes [[6, 2, 3]]_p and [[7, 3, 3]]_p (p ≥ 3) exist. IEEE Trans Inform Theory, 2002, 48(8): 2384-2391.

[18] Feng K., Ling S., Xing C. Asymptotic bounds on quantum codes from algebraic geometry codes. IEEE Trans Inform Theory, 2006, 52(3): 986-991.

[19] Feng K., Ma Z. A finite Gilbert-Varshamov bound for pure stabilizer quantum codes. IEEE Trans Inform Theory, 2004, 50(12): 3323-3325.

[20] Blakle G R. Safeguarding cryptographic keys. Proc NCC AFIPS, 1979, 313–317

[21] Shamir A. How to share a secret. Comm ACM, 1979, 22: 612-613.

[22] Brickell E. F. Some ideal secret sharing schemes. Advances in Cryptology-Eurocrypt’89, 1990, Heidelberg: Springer, 468-475.

[23] Cramer R., Daza V., Cracia I. On codes, matroids and secure multi-party computations from linear secret sharing schems. Advances in Cryptology, Crpto 2005, 2005, Berlin: Springer, 327-343.

[24] Chen H., Cramer R. Algebraic geometric secret sharing schemes and secure multi-party computation over small fields. Crypto2006, 2006, Berlin: Springer, 516-531.

[25] Leung K. H., Ling S., Xing C. New binary linear codes from algebraic curves. IEEE Trans Inform Theory, 2002, 48(1): 285-287.

[26] Stichtenoth H., Xing C. Excellent nonlinear codes from algebraic function fields. IEEE Trans Inform Theory, 2005, 51(11): 4044-4046.

[27] Xing C., Kumar P. V., Ding C. Low-correlation, large linear span sequences from function fields. IEEE Trans Inform Theory, 2003, 49(6): 1439-1446.

[28] Wang H., Xing C., Safavi-Naini R. Linear authentication codes: bounds and constructions. IEEE Trans Inform Theory, 2003, 49(4): 866-872.