Algebra for Coding Theory and Cryptography

Academic year 2022/2023

Introduction

The aim of this course is to introduce some foundational algebraic techniques used in cryptography and coding theory, as well as to present some important and useful protocols. In particular we discuss many modern cryptosystems, including AES, RSA and EC-based protocols, as to understand their properties and limitations.

  1. Programme (in Italian)

Examples

  1. Simple Enigma-like machine
  2. Simple Enigma-like machine - julia
  3. Exponentiation, primality, Zp
  4. Textbook El Gamal and variants
  5. Euclidean algorithms
  6. SVP - Gauss method (jl)
  7. LLL and GCD (jl)
  8. Primality and factoring
  9. RSA
  10. Birthday Paradox
  11. Birthday Paradox (jl)
  12. Shuffles
  13. RC4 (jl)
  14. Finite Fields
  15. AES
  16. Meet in the middle
  17. Elliptic Curves
  18. MQV
  19. ECDSA
  20. Hash Functions
  21. MixNet
  22. Dining Cryptographers
  23. Superposed Sending
  24. DCT

Bibliography

  1. D. Boneh, V. Shoup, A Graduate Course in Applied Cryptography (2023)
  2. N.P. Smart, Cryptography Made Simple, Springer-Verlag (2016)
  3. A.R. Meijer, Algebra for Cryptologists, Springer-Verlag (2016)
  4. J. von zur Gathen, CryptoSchool, Springer-Verlag (2015)
  5. W. Stallings, Cryptography and network security, Sixth Edition, Prentice Hall (2014)
  6. N.P. Smart, Cryptography: an introduction, (2013) pdf file:3.0.1.3
  7. M.W. Baldoni, C. Ciliberto, G.M. Piacentini Cattaneo, Aritmetica, crittografia e codici, Springer-Verlag UNITEXT 24, (2006)
  8. A. Languasco, A. Zaccagnini Manuale di crittografia. Teoria, algoritmi e protocolli. Hoepli (2015)
  9. L. Giuzzi, Codici correttori - un'introduzione Springer-Verlag UNITEXT 25, (2006)
  10. A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of applied cryptography, CRC Press (2001)
  11. C. Swenson, Modern Cryptanalysis, Wiley Publishing, Inc. (2008)
  12. G.V. Bard, Algebraic Cryptanalysis, Springer-Verlag (2009)
  13. A. Joux, Algorithmic cryptanalysis, CRC Press (2009)
  14. R. Wobst, Cryptology Unlocked Wiley (2007)
All lectures shall be offered in a traditional way.

References

Introduction

  1. C. E. Shannon, Communication Theory of Secrecy Systems, in "A mathematical Theory of Cryptography" (1949).

Classical Cryptography

  1. W.F. Friedman, Military Cryptanalysis - Part I: monoalphabetic subsitution systems
  2. W.F. Friedman, Military Cryptanalysis - Part II: simpler varieties of polyalphabetic substitution systems
  3. W.F. Friedman, Military Cryptanalysis - Part III: simpler varieties of aperiodic substitution systems
  4. W.F. Friedman, Military Cryptanalysis - Part IV: transposition and fractionating systems
  5. A. Turing, A treatise on the Enigma
  6. Brevetto US 6175625 (Sigaba)

Diffie-Hellman and STS

  1. W. Diffie, M.E. Hellman, New directions in Cryptography, IEEE Transactions on Information Theory 22: 644-654 (1976), doi:10.1109/TIT.1976.1055638
  2. W. Diffie, P.C. Oorschot and M.J. Wiener, Authentication and Authenticated Key Exchanges, Des. Codes and Cryptography 2: 107-125 (1992), doi:10.1007/BF00124891

ElGamal

  1. T. Elgamal, A public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory IT-31: 469-472 (1985) oppure CRYPTO'84: 10-18, Springer-Verlag.
  2. D. Boneh, A. Joux, P.Q. Nguyen, Why Textbook ElGamal and RSA Encryption are Insecure

Pairing and ID-based cryptography

  1. A. Menezes, An introduction to pairing-based cryptography, Recent trends in cryptography, Contemp. Math. 477: 47-65 (2009).
  2. A. Shamir, Identity-based Cryptosystems and Signature Schemes, Advances in Cryptology, Lecture Notes in Computer Science 7: 47-53 (1984)
  3. D. Boneh, M. Franklin, Identity-based Ecryption from the Weil Pairing, SIAM J. of Computing 32: 586-615 (2003).

RSA

  1. R.L Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21: 120-126 (1978)
  2. R.L. Rivest, R.D. Silverman, Are 'strong' primes needed for RSA? (1999)
  3. D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices of the AMS, 46(2): 203-213 (1999)
  4. M. Bellare, P. Rogaway, Optimal Asymmetric Encryption - How to encrypt with RSA, Extended abstract in Advances in Cryptology - Eurocrypt 94 Proceedings, Lecture Notes in Computer Science 950 (1995)

Primality and Factoring

  1. A. Granville, It is easy to determine whether a given integer is prime, Bull. of the A.M.S. 42(1):3-38 (2004)
  2. M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Ann. of Math. 160(2):781-793 (2004).
  3. A.K. Lenstra, Integer factoring, Des. Codes. Crypto. 19:101-128 (2000)

Birthday paradox

  1. P.J. Cameron, Notes on probability

Polynomial multiplication

  1. J.M. Pollard, The Fast Fourier Transform in a Finite Field, Mathematics of Computation 114(25): 365-374 (1971)
  2. R.T. Moenck, Practical Fast Polynomial Multiplication, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation (1976)
  3. A.A. Karatsuba, The Complexity of Computations, Proceedings of the Steklov Institute of Mathematics 211: 169-183 (1995)

Block ciphers

  1. H. Feistel, Block Cipher Cryptographic System, US Patent 3798359 (1975)
  2. Data Encryption Standard (DES), FIPS-46-3 (1999)
  3. D. Coppersmith, The Data Encryption Standard (DES) and its strenth against attacks, IBM Journal of Research and development, 38(3) 243-250 (1994).
  4. M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology - Eurocrypt'93, 765/1994, 386-397 (1994), doi:10.1007/3-540-48285-7_33 .
  5. E. Biham, A. Shamir, Differential Cryptanalysis of DES-like Cryptosystems, J. Criptol., 4 3-72 (1991).
  6. R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, L. Wingers, The Simon and Speck Families of Lightweight Block Ciphers (2013).
  7. The Advanced Encryption Standard (AES), FIPS-197 (2001)
  8. J. Daemen, V. Rjimen, AES Proposal: Rijndael (1999)
  9. M. Dworkin, Recommendation for Block Cipher Modes of Operation, NIST Special Publication 800-38A (2001)
  10. D.A. McGrew, J. Viega, The Galois/Counter Mode of Operation (GCM)
  11. V. Rjimen, Efficient implementation of the Rijndael S-Box
  12. F.X. Standaert, G. Piret, J.J. Quisquater, Cryptanalysis of Block Ciphers: a survey, UCL Crypto Group Technical Report CG-2003/2
  13. C.Cid, Some algebraic aspects of the Advanced Encryption Standard, Proceedings of the Fourth Conference on the Advanced Encryption Standard (AES4), LNCS 3373: 58-66 (2004)
  14. C.Cid, S. Murphy, M. Robshaw Computational and Algebraic Aspects of the Advanced Encryption Standard, Proceedings of the Seventh International Workshop on Computer Algebra in Scientific Computing CASC' 2004: 93-103 (2004)
  15. C. Burwick, D. Coppersmith, E. D'Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas Jr., L. O'Connor, M. Peyravian, D. Safford, N. Zunic, Mars - a candidate cipher for AES (1999)

Elliptic Curves

  1. S.C. Vo, A survey of Elliptic Curve Cryptosystems, part I: Introductory, NASA Ames Research Center Technical Report NAS-03-012 (2003)
  2. Certicom Research, Standards for Efficient Cryptography 1 (SEC1), 2009
  3. Nippon Telephone and Telegraph Corporation, Standards for Efficient Cryptography SEC X.1: Supplemental Document for Odd Characteristic Extension Fields, Working Draft 2009
  4. H. Krawczyk, HMQV: A High-Performance Secure Diffie-Hellman Protocol, Advances in cryptology - CRYPTO 2005, 3621: 546-566 (2005)
  5. A. Menezes, Another look at HMQV, Journal of Mathematical Cryptology 1: 148-175 (2007)
  6. H. W. Lenstra, Factoring integers with elliptic curves, Annals of Mathematics 1126: 649-673 (1987)
  7. S. Goldwasser, J. Kilian, Primality testing using elliptic curves, Journal of the ACM 46(4): 450-472 (1999)
  8. FIPS 186-4: Digital Signature Standard (DSS) (2013)
  9. ANS X9.62: Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) (1998, draft)

Pseudorandom number generation

  1. E. Barker, J. Kelsey Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST Special Publication 800-90A (2012)
  2. D. J. Bernstein, T. Lange, R. Niederhagen, Dual EC: A Standardized Back Door (2015)

Security models for public key cryptosystems

  1. M. Bellare, A. Desai, D. Pointcheval, P. Rogaway Relations Among Notions of Security for Public Key Encryption Schemes, Extended abstract in Advances in Cryptology - CRYPTO'98, Lecture Notes in Computer Science 1462 (1998)
  2. A. Shamir, R.L. Rivest, L.M. Adleman, Mental Poker in The Mathematical Gardner, ed. D.A. Klarner: 37-43 (1981)
  3. M. Blum, Coin flipping by telephone: a protocol for solving impossible problems, ACM SIGACT News, 15 (1983)

Hash functions

  1. B. Preneel, Analysis and design of cryptographic hash functions, Ph.D. thesis (1993)
  2. FIPS 180-4: Secure Hash Standard (SHS) (2012)
  3. FIPS 198: The Keyed-Hash Message Authentication Code (HMAC) (2002)
  4. P. Gauravaram et al., Grøstl - a SHA-3 candidate (2008)
  5. P. Gauravaram et al., Grøstl Addendum (2009)
  6. E. Biham, O. Dunkelman, A framework for Iterative Hash Functions --- HAIFA Proceedings of the Second NIST Cryptographic Hash Workshop (2006-2007)
  7. G. Bertoni, J. Daemen, M. Peeters, G. Van Assche The Keccak reference, 2011
  8. G. Bertoni, J. Daemen, M. Peeters, G. Van Assche Cryptographic sponge functions, 2011
  9. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, FIPS-202 (2015)

Secret sharing

  1. A. Shamir, How to Share a Secret, Communications of the ACM 22:612-613 (1979)
  2. O. Goldreich, D. Ron, M. Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory 46: 1330-1338 (2000)

Anonimity

  1. D.L. Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, Communications of the ACM 24: 84-88 (1981)
  2. D.L. Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, J. Cryptology 1: 65-75 (1988)
  3. M. Waider, Unconditional Sender and Recipient Untraceability in spite of Active Attacks, Proceedings of EUROCRYPT'89: 302-319 (1989)
  4. M. Waider, B. Pfitzmann, Unconditional sender and recipient untraceability in spite of active attacks - Some remarks, Fakultät für Informatik, Universität Karlshrue, Interner Bericht 5/89 (1989)
  5. M. Waider, B. Pfitzmann, The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability (1989).
  6. P.Golle, A.Juels, Dining Cryptographers Revisited, Advances in Cryptology (EUROCRYPT'04): 456-473 (2004)
  7. C.Park, K. Itoh, K.Kurosawa, Efficient Anonymous Channel and All/Nothing Election Scheme, EUROCRYPT'93 Workshop on the theory and application of cryptographic techniques on Advances in cryptology (1993)
  8. B. Pfitzmann, Breaking an Efficient Anonymous Channel, EUROCRYPT'94: 339-348 (1994)
  9. W.Ogata, K.Kurosawa, K.Sako, K.Takatani, Fault Tolerant Anonymous Channel, ICICS'96 Proceedings of the First International Conference on Information and Communication Security (1997)
  10. D.Chaum, T.P. Pedersen, Wallet Databases with Observers, Proc. of Crypto'92: 89-105 (1993)
  11. D. Boneh, P. Golle, Almost Entirely Correct Mixing With Applications to Voting, CCS'02 Proceedings of the 9th ACM Conference on Computer and communications security (2002)
  12. P.Golle, M.Jakobsson, A.Juels, P.Syverson, Universal Re-encryption for Mixnets, Proceedings of the 2004 RSA Conference: 163-178 (2002)

Homomorphic Encryption

  1. R.L. Rivest, L. Aldeman, M.L. Dertouzos, On Data Banks and Privacy Homomorphisms, in Foundations of Secure Computation, 169-180 (1978)
  2. C. Gentry, Computing Arbitrary Functions of Encrypted Data, Communications of the ACM, 53 (3) 97-105 (2010)
  3. C. Gentry, A fully homomorphic encryption scheme, Stanford University, PHD Thesis (2009)
  4. S.Halevi, V.Shoup, Algorithms in HElib, Advances in Cryptology - CRYPTO 2014, Springer-Verlag, 554-571 (2014)

Oblivious Transfer

  1. A. Rabin, How to exchange secrets with oblivious transfer, Technical Report TR-81, Aiken Computation Lab, Harvard University (1981)
  2. S. Even, O. Goldreich, A. Lempel, A randomized protocol for Signing Contracts, Communications of the ACM 28(6), 637-647 (1985)

Secure multiparty computation

  1. A.C. Yao, Protocols for Secure Computations (1982)
  2. A.C. Yao, How to Generate and Exchange Secrets, Foundations of Computer Science - FOCS 1986, IEEE 16-167 (1986)
  3. Y. Lindell, B. Pinkas, Secure Multiparty Computation for Privacy-Preserving Data Mining, Journal of Privacy and Confidentiality 1, 59-98 (2009)
  4. M. Bellare, V.T. Hoang, P. Rogaway, Foundations of Garbled Circuits, In ACM Computer and Communications Security (CCS'12) ACM (2012).
  5. I.Damgård, M.Geisler, M.Krøigaars, J.B.Nielsen Asynchronous Multiparty Computation: Theory and Implementation, In Public Key Cryptography - PKC 2009, Springer-Verlag, 160-179 (2009)

Blind Signatures

  1. D. Chaum, Blind signatures for untraceable payments, Advances in Cryptology - Proceedings of CRYPTO'82, Springer-Verlag, 199-203 (1983)
  2. J.L.Camenisch, J-M.Piveteau, M.A.Stadler, Blind signatures based on the discrete logarithm problem, Advances in Cryptology - EUROCRYPT'94, Springer-Verlag, 428-432 (1994)

Deniable Encryption

  1. R.Canetti, C.Dwork, M.Naor, R.Ostrovsky, Deniable Encryption, Advances in Cryptology - Crypto'97, Springer-Verlag, 90-104 (1997)
  2. A.Sahai, B.Waters, How to use indistinguishability obfuscation: deniable encryption and more, STOC'14 - Proceedings of the 46 Annual ACM Symposium on Theory of Computing, 475-484 (2014)

Byzantine agreement

  1. L. Lamport, R. Shostak, M. Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems: 382-401 (1982)

E-Voting

  1. L. Fouard, M.Duclos, P.Lafourcade, Survey on Electronic Voting Schemes
  2. A.Fujioka, T.Okamoto, K.Ohta, A practical secret voting scheme for large scale elections, Advances in Cryptology - AUSCRYPT'92, Springer-Verlag, 244-251 (1992)

Error correcting codes

  1. C.E. Shannon, A Mathematical Theory of communication, Bell System Tech. Journal Vol. XXVII: 379-423, 623-656 (1948).
  2. I.S. Reed, G. Solomon, Polynomial codes over certain finite fields, J. Soc. Ind. Appl. Math. Vol. 8: 300-304 (1960).
  3. E. R. Berlekamp Non-binary BCH Decoding, University of North Carolina Institute of Statistics Mimeo Series No. 502 (1966)
  4. L.R. Welch, E.R. Berlekamp, Error Correction for Algebraic Block Codes, US Patent no. 4633470 (1986).