[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Gröbner Bases, Coding, and Cryptography: a Guide to the State-of-Art

  • Chapter
  • First Online:
Gröbner Bases, Coding, and Cryptography
  • 2110 Accesses

Abstract

Last century saw a number of landmark scientific contributions, solving long-standing problems and opening the path to entirely new subjects. We are interested in three (here listed in chronological order) of these:

  1. 1.

    Claude Shannon’s (Bell System Tech. J. 27:379–423, 623–656, 1948),

  2. 2.

    Claude Shannon’s (Bell System Tech. J. 28:656–715, 1949),

  3. 3.

    Bruno Buchberger’s (Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck, 1965)

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  • F. Armknecht and G. Ars, Algebraic attacks on stream ciphers with Gröbner bases, this volume, 2009, pp. 329–348.

    Google Scholar 

  • D. Augot and M. Stepanov, A note on the generalisation of the Guruswami–Sudan list decoding algorithm to Reed–Muller codes, this volume, 2009, pp. 395–398.

    Google Scholar 

  • D. Augot, E. Betti and E. Orsini, An introduction to linear and cyclic codes, this volume, 2009, pp. 47–68.

    Google Scholar 

  • P. Beelen and K. Brander, Decoding folded Reed–Solomon codes using Hensel lifting, this volume, 2009, pp. 389–394.

    Google Scholar 

  • O. Billet and J. Ding, Overview of cryptanalysis techniques in multivariate public key cryptography, this volume, 2009, pp. 263–283.

    Google Scholar 

  • M. Borges-Quintana, M. A. Borges-Trenard and E. Martinez-Moro, An application of Möller’s algorithm to coding theory, this volume, 2009, pp. 379–384.

    Google Scholar 

  • B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck, 1965.

    Google Scholar 

  • B. Buchberger, Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, J. Symb. Comput. 41 (2006), no. 3-4, 475–511.

    Article  MathSciNet  MATH  Google Scholar 

  • S. Bulygin and R. Pellikaan, Decoding linear error-correcting codes up to half the minimum distance with Gröbner bases, this volume, 2009, pp. 361–365.

    Google Scholar 

  • E. Byrne and T. Mora, Gröbner bases over commutative rings and applications to coding theory, this volume, 2009, pp. 239–261.

    Google Scholar 

  • C. Cid and R. P. Weinmann, Block ciphers: algebraic cryptanalysis and Gröbner bases, this volume, 2009, pp. 307–327.

    Google Scholar 

  • W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans. on Inf. Th. 22 (1976), no. 6, 644–654.

    Article  MathSciNet  MATH  Google Scholar 

  • O. Geil, Algebraic geometry codes from order domains, this volume, 2009, pp. 121–141.

    Google Scholar 

  • M. Giorgetti, About the nth-root codes: a Gröbner basis approach to the weight computation, this volume, 2009, pp. 357–360.

    Google Scholar 

  • D. Gligoroski, V. Dimitrova and S. Markovski, Quasigroups as Boolean functions, their equation systems and Gröbner bases, this volume, 2009a, pp. 415–420.

    Google Scholar 

  • D. Gligoroski, S. Markovski and S. J. Knapskog, A new measure to estimate pseudo-randomness of Boolean functions and relations with Gröbner bases, this volume, 2009b, pp. 421–425.

    Google Scholar 

  • H. Gluesing-Luerssen, B. Langfeld and W. Schmale, A short introduction to cyclic convolutional codes, this volume, 2009, pp. 403–408.

    Google Scholar 

  • V. D. Goppa, Codes on algebraic curves, Soviet Math. Dokl. 24 (1981), no. 1, 170–172.

    MATH  Google Scholar 

  • M. Greferath, An introduction to ring-linear coding theory, this volume, 2009, pp. 219–238.

    Google Scholar 

  • E. Guerrini and A. Rimoldi, FGLM-like decoding: from Fitzpatrick’s approach to recent developments, this volume, 2009, pp. 197–218.

    Google Scholar 

  • E. Guerrini, E. Orsini and I. Simonetti, Gröbner bases for the distance distribution of systematic codes, this volume, 2009, pp. 367–372.

    Google Scholar 

  • R. W. Hamming, Error detecting and error correcting codes, Bell Systems Technical Journal 29 (1950), 147–160.

    MathSciNet  Google Scholar 

  • J. L. Kim, A prize problem in coding theory, this volume, 2009, pp. 373–377.

    Google Scholar 

  • K. Lally, Canonical representation of quasicyclic codes using Gröbner basis theory, this volume, 2009, pp. 351–355.

    Google Scholar 

  • D. A. Leonard, A tutorial on AG code construction from a Gröbner basis perspective, this volume, 2009a, pp. 93–106.

    Google Scholar 

  • D. A. Leonard, A tutorial on AG code decoding from a Gröbner basis perspective, this volume, 2009b, pp. 187–196.

    Google Scholar 

  • F. Levy-dit-Vehel, M. G. Marinari, L. Perret and C. Traverso, A survey on Polly Cracker systems, this volume, 2009, pp. 285–305.

    Google Scholar 

  • J. B. Little, Automorphisms and encoding of AG and order domain codes, this volume, 2009, pp. 107–120.

    Google Scholar 

  • E. Martinez-Moro and D. Ruano, Mattson Solomon transform and algebra codes, this volume, 2009, pp. 385–388.

    Google Scholar 

  • R. Matsumoto, Radical computation for small characteristics, this volume, 2009, pp. 427–430.

    Google Scholar 

  • G. L. Matthews, Viewing multipoint codes as subcodes of one-point codes, this volume, 2009, pp. 399–402.

    Google Scholar 

  • R. J. McEliece, A public key cryptosystem based on algebraic coding theory, JPL DSN 42–44 (1978), 114–116.

    Google Scholar 

  • T. Mora, The FGLM problem and Moeller’s algorithm on zero-dimensional ideals, this volume, 2009a, pp. 27–45.

    Google Scholar 

  • T. Mora, Gröbner technology, this volume, 2009b, pp. 11–25.

    Google Scholar 

  • T. Mora and E. Orsini, Decoding cyclic codes: the Cooper philosophy, this volume, 2009, pp. 69–91.

    Google Scholar 

  • P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Trudy Mat. Inst. im. Steklov. no. 44, Izdat. Akad. Nauk SSSR, 1955.

    Google Scholar 

  • P. S. Novikov, On the algorithmic insolvability of the word problem in group theory, AMS Translations, Ser. 2, Vol. 9, AMS, Providence, 1958, pp. 1–122.

    Google Scholar 

  • R. L. Rivest, A. Shamir and L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (1978), no. 2, 120–126.

    Article  MathSciNet  MATH  Google Scholar 

  • S. Sakata, The BMS algorithm, this volume, 2009a, pp. 143–163.

    Google Scholar 

  • S. Sakata, The BMS algorithm and decoding of AG codes, this volume, 2009b, pp. 165–185.

    Google Scholar 

  • C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423, 623–656.

    MathSciNet  MATH  Google Scholar 

  • C. E. Shannon, Communication theory of secrecy systems, Bell System Tech. J. 28 (1949), 656–715.

    MathSciNet  MATH  Google Scholar 

  • C. E. Shannon and W. Weaver, The mathematical theory of communication, University of Illinois Press, Urbana, 1949.

    MATH  Google Scholar 

  • I. Simonetti, On the non-linearity of Boolean functions, this volume, 2009, pp. 409–413.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Massimiliano Sala .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Sala, M. (2009). Gröbner Bases, Coding, and Cryptography: a Guide to the State-of-Art. In: Sala, M., Sakata, S., Mora, T., Traverso, C., Perret, L. (eds) Gröbner Bases, Coding, and Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-93806-4_1

Download citation

Publish with us

Policies and ethics