Show The Graduate Center Menu

Cryptographic Protocols

Instructor: Assistant Professor Nelly Fazio

Nelly Fazio is an Assistant Professor in the Computer Science Departments at the City College and the Graduate Center of CUNY. Her fields of interest include Cryptography and Information Security, with a focus on foundations (public-key and non-commutative cryptography) and applications (content protection, access control, and security in military scenarios). Her research is funded in part by the National Science Foundation, by the U.S. Army Research Laboratory and the U.K. Ministry of Defence, and by several CUNY research grants.

Dr. Fazio's awards include a 2013 NSF CAREER award, an NYU Sandra Bleistein Prize for "notable achievement by a woman in Applied Mathematics or Computer Science", an EU Marie Curie Fellowship, and an honorable mention for the NYU Janet Fabri Prize for an "outstanding dissertation in Computer Science".

Dr. Fazio received her Ph.D. from New York University, under the supervision of Prof. Yevgeniy Dodis. Her doctoral training also included research visits at Stanford University, at the Ecole Normale Superieure in Paris, France, and at Aarhus Universitet, Denmark. Before joining CUNY, Dr. Fazio was a postdoctoral fellow in the Content Protection group at IBM Almaden Research Center and a visiting researcher in the Cryptography Research group at IBM T.J. Watson Research center.

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 provable 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, Verifiable computation and Cloud computing.


No prior knowledge of cryptography is required. However, general ease with algorithms and elementary probability theory, and maturity with mathematical proofs will be assumed.

Learning Objectives

  • 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 findings 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.


Course Topics

  • Definition of fundamental cryptographic primitives.

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

  • Cramer-Shoup Encryption Scheme.

  • Commitment schemes. Hiding and binding properties.

  • Commitments schemes. Constructions from RSA.

  • Bit Commitment using pseudo-randomness.

  • Introduction to Zero-Knowledge. Interactive proofs/arguments, perfect/statistical/computational zero-knowledge.

  • More on zero-knowledge. Rewinding and cut-and-choose techniques.

  • Zero-knowledge protocols for all NP languages. Zero-knowledge beyond NP: Graph Non-Isomorphism.

  • Introduction to multi-party computation. Secret sharing. Security models for multi- party computation and secure function evaluation.

  • Secure evaluation of arithmetic circuits: The protocol and its security analysis.

  • Proofs of knowledge and knowledge extraction: The Schnorr protocol.

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



Grade will be based on:

  • Class participation: 10%

  • Weekly reading summaries: 40%

  • Term project (presentation and report): 50%