Show The Graduate Center Menu

Cryptographic Protocols

Course description


This graduate-level course covers the theory of cryptographic protocols and
some of its applications. Emphasis will be placed on the methodology of prov-
able security, whereby the security goals of a given communication and/or
computational task are abstracted into an adversarial model amenable to
mathematical treatment.
Topics to be covered include: Commitment schemes, Coin-tossing, Zero-
knowledge, Oblivious transfer, Secret sharing, Secure function evaluation/multi-
party computation, Veriable computation and Cloud computing.
No prior knowledge of cryptography is required. However, general ease
with algorithms and elementary probability theory, and maturity with math-
ematical proofs will be assumed.

Learning Goals

  • Evaluate a given security protocol against the state of the art.

  • Explain, illustrate, and contrast advanced cryptographic concepts, both
    verbally and in writing, at a level suitable for either a technical or non-
    technical audience.

  • Locate salient or innovative ideas in a technical paper, and summarize
    ndings in reports.

  • Assess the work of others against given guidelines and requirements,
    e.g., in the context of a peer review.

  • Research and document a topic as part of a class project.

Syllabus (Tentative)

  • Week 1-2 Introduction. Sample cryptographic protocols. Review of fundamental
    cryptographic primitives.

  • Week 3 Some techniques and methodologies for arguments of provable security.
    The case of ElGamal Encryption Scheme.

  • Week 4 Cramer-Shoup Encryption Scheme.

  • Week 5 Commitment schemes. Hiding and binding properties.correctness of programs.

  • Week 6 Commitments schemes. Constructions from RSA.
  • Week 7 Bit Commitment using pseudo-randomness.

  • Week 8 Intro to Zero-Knowledge. Interactive proofs/arguments, perfect/statistical/computational zero-knowledge.
  • Week 9 More on zero-knowledge. Rewinding and cut-and-choose techniques.

  • Week 10 Zero-knowledge protocols for all NP languages. Zero-knowledge beyond NP: Graph Non-Isomorphism.
  • Week 11 Introduction to multi-party computation. Secret sharing. Security models for multi-party computation and secure function evaluation.

  • Week 12 Secure evaluation of arithmetic circuits: The protocol and its security analysis.
  • Week 13 Proofs of knowledge and knowledge extraction: The Schnorr protocol.

  • Week 14 Secure evaluation of boolean circuits: Oblivious transfer and Yao's garbled circuit protocol.