Lectures

• Lecture 1
  • Legal basis for privacy, introduction
  • Discussion: New Directions in Cryptography, Whitfield Diffie and Martin E. Hellman.
  • Current events: Passport, P3P, DMCA
  • Introduction to ciphers: symmetric, asymmetric
  • Unconditionally secure, the One Time Pad
  • Computationally secure, introduction to NP (Travelling Salesman Problem)
• Lecture 2
  • Finite fields and the Diffie-Hellman Problem.
  • Pohlig Hellman algorithm.
    • Explanation of algorithm.
    • A Java program for the case of Z/17Z. The program's output.
    • Another example.
  • Example of GF(9)
  • Notes on Warren and Brandeis.
• Lecture 3
  • Discussion of current events, Privacy versus Law Enforcement.
  • From Diffie Hellman problem to public key systems:
    • Key Agreement Systems: Diffie Hellman, Okamoto
    • Published Public Key System: El Gamal
  • Another Published Public Key System: RSA
  • Signatures, Blind Signatures
  • Untracable Electronic Cash, David Chaum, et al.
  • Discussion: The Death of Privacy by M. Froomkin
  • Discussion: Security without identification by D. Chaum.
• Lecture 4
  • Current Events: WSJ article on the Electronic Freedom Foundation
  • Finite Automata, Regular Expressions
  • Turing Machines, Halting Problem
  • Complexity Classes P, NP, RP, co-RP, BPP and ZPP.
  • Discussion: Introduction to Complexity Theory, Lecture 7: Randomized Computations, Oded Goldreich.
  • Discussion: Randomness, Interactive Proofs and Zero-Knowledge, Oded Goldreich.
  • Example: A co-RP test for primality: Solovay-Strassen
• Lecture 5
  • Zero-knowledge. Read Goldwasser, Micali and Rackoff, "The knowledge complexity of interactive proof systems".
  • Read: Lecture 18 from Pseudorandomness and Cryptographic Applications, by Michael Luby. Handout from class.
  • Read: Flood Control on the Information Ocean: Living With Anonymity, Digital Cash, and Distributed Database, M. Froomkin.
• Lecture 6
  • One-way functions (Brands 2.2.1, 2.2.2)
  • collision-intractability (Brands 2.3.1, 2.3.2)
  • Proofs of knowledge (Brands 2.4.1-3)
  • Digital signatures (Brands 2.5.1-3)
  • Restrivite Blind Issuing Protocols (Brands 4.1, 4.2 DLREP scheme I)
  • Read the Family Educational Right to Privacy Act.
  • Read Childs Online Privacy Protection Act of 1998

  Exercises

  • Exercises for Lecture 2
    • Give examples of the calculations of GF(q) for some various prime power q's. Show the multiplication table, find the irreducible polynomials.
    • Write a program implementing Pohlig-Hellman. For simplicity, write the program for fields Z/pZ for prime p, and assume that the list of all prime factors of (p-1) will be given as input.
  • Midterm paper: Individual essay on Privacy. Due Thursday 18, October.
  • Exercise for Lecture 4
    • Prove that 2 is a quadratic residue mod p, p a prime, according to whether (-1)^{p^2-1}/4 is 1 or -1.
  • Exercise for Lecture 5:
    • Ex. 72 from Luby's book. Show that the Graph Non-Isomorphism problem has perfect Zero Knowledge Interactive Protocol.
    • Ex. 73 from Luby's book. Show that the Hidden bit commitment protocol (page 182) hides b if g is pseudo-random. Prove the protocol 2^n-secure committed, whether or not g is pseudo-random.
  • Final: read Diffie and Landau's Privacy on the Line.

  Readings

  • Technical
    • New Directions in Cryptography,, Whitfield Diffie and Martin E. Hellman.
    • Randomness, Interactive Proofs and Zero-Knowledge, Oded Goldreich.
    • Security Without Identification..., David Chaum.
    • Introduction to Complexity Theory, Lecture 7: Randomized Computations, Oded Goldreich.
    • The knowledge complexity of interactive proof systems, Shafi Goldwasser, Silvio Micali, Charles Rackoff. SIAM J Comp, Vol. 18, No. 1, pp. 186-208. February 1989.
    • Pseudorandomness and Cryptographic Applications, by Michael Luby. Princeton University Press, 1996.
    • Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, Stefan A. Brands. MIT Press 2000.
  • Legal and Policy
    • The Right to Privacy, Samuel D. Warren, Louis D. Brandeis.
    • The Death of Privacy by M. Froomkin
    • Flood Control on the Information Ocean: Living With Anonymity, Digital Cash, and Distributed Databases" by M. Froomkin
    • Privacy Act of 1974, Department of Justice.
    • Freedom Of Information Act (FOIA, 1966), Department of Justice.
    • Family Educational Right to Privacy Act (Buckley Amendment)
    • Florida Statutes Title XVIII, 257.261, concerning library records of public institutions.
    • Privacy on the Line: The Politics of Wiretapping and Encryption, Whitfield Diffie and Susan Landau. MIT Press, 1999.
    • Childs Online Privacy Protection Act of 1998

  Resources

  • Electronic Privacy Information Center
  • Electronic Freedom Foundation
  • NEC Research Index
  • Cryptography regulation in France

(c) 2001 Burton Rosenberg. All rights reserved.