Show The Graduate Center Menu

Algebraic Cryptography


Professor Delaram Kahrobaei

Course description

The course is targeted at graduate students with interest in algorithmic problems in algebra or group theory and applications to cryptography. At the beginning of the course all notions related to group theory will be covered. The pre-requisite of the course is basic knowledge of cryptography and algorithms.

List of topics

  • Combinatorial group theory (groups presented as finite presentations, Algorithmic problems in group theory: Decision problems, Search Problems, Some poplular groups: braid groups, Thompson’s group, Baumslag-Solitar groups, polycyclic and metabelian groups, Normal forms.)

  • Computational Group Theory (Some computations with Groups, mention about the related software, GAP, Magnus)

  • Computability and Complexity of algorithms in group theory used in cryptography as well as generic case complexity.

  • Cryptographic problems : Commutative and non-Commutative (public key exchange problems, digital signatures, authentication)

  • Quantum Algorithms in group theory and applications in cryptography

  • Semidirect product of groups and application to key exchange problem

  • Using group presentation and word problem in Secret Sharing

  • Complexity of finding square roots in groups and application to public key

  • Non-commutative Digital Signatures

  • Fully Homomorphic Encryption

  • Open interesting problems

  • Project Presentation


The grading is mainly based on a final exam (50%) and a project (50%).


A. G. Myasnikov, V. Shpilrain, and A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, Amer. Math. Soc. Surveys and Monographs, 2011.