1 Exam Coverage

The final exam will cover the entire course but with greater emphasis on the part of the course not covered by the midterm exam (lectures 12–24 and related material). These topics are presented in several different formats:

1. In-person class lectures.
2. Written lecture notes, available on the course web site.
3. Written handouts, available on the course web site. I draw your attention to the four handouts on the more mathematical aspects of the course:
   • Handout 5: Number theory summary (.pdf).
   • Handout 6: Linear congruence equations (.pdf).
   • Handout 7: The Legendre and Jacobi symbols (.pdf).
   • Handout 17: Pseudorandom sequence generation (.pdf).
4. Textbook (Stinson), relevant sections from chapters 1–5 as covered by the midterm. (See handout 10 (.pdf).)
5. Textbook (Stinson), relevant sections from chapters 4–9, 11, and 13 covered since the midterm. Roughly speaking this is sections 4.1, 4.3, 5.2.2, 5.4, 5.5, 5.7.2, 6.1, 6.2.1, 7.1–7.3, 7.4.2, 8.1–8.5, 9.1–9.3, 11.1, 11.2 (first three pages), 13.1.
6. Other resources available in the library and on the web.
7. Problem sets and solutions.

2 Review Outline

Below I give a list of topics, concepts, definitions, theorems, algorithms, and protocols that we have covered and that I expect you to know. This list is not inclusive, as I’m sure I have missed some things. Please see handout 10 (.pdf) for a review outline of the material before the midterm.

1. Additional number theory.
   1. Chinese remainder theorem.
   2. Prime number theorem.
   3. Primitive roots.
      • Lucas test.
      • Discrete logarithm.
   4. Quadratic residues.
      • Square roots modulo a prime.
      • Square roots modulo a product of two distinct primes.
      • Euler criterion.
      • Finding square roots modulo prime p when p ≡ 3 (mod 4).
      • Shank’s algorithm for finding square roots modulo an odd prime.
      • Legendre symbol.
      • Jacobi symbol.
      • Jacobi symbol identities (don’t memorize, but understand what they are).
      • Computing the Jacobi symbol.
   5. Probabilistic primality testing
      • General framework for tests of compositeness (from lecture notes 10).
      • Fermat test of compositness ζ_a(n).
      • Strassen-Solovay test of compositeness ν_a(n)
      • Miller-Rabin test of compositeness μ_a(n).
2. Cryptographic protocols based on number theory (besides RSA).
   1. Diffie-Hellman key exchange.
   2. ElGamal key agreement.
   3. ElGamal public key cryptosystem.
   4. Goldwasser-Micali (QR) probabilistic cryptosystem.
3. Digital signatures.
   1. Definition of a digital signature.
      • Signature.
      • Authenticated (signed) message.
      • Signature function.
      • Verification predicate.
   2. RSA digital signature scheme.
      • Commutative cryptosystems.
      • Signatures from non-commutative cryptosystems.
   3. Security of digital signatures.
      • Kinds of forgery attacks.
      • Signing random messages.
      • Signing message digests.
      • Differences between conventional and digital signatures.
      • Disavowal.
4. Message digest (hash) functions.
   1. Desired properties.
      • One-way property.
      • Weak collision-free property.
      • Strong collision-free property.
   2. Relations among properties.
5. Combining signatures with encryption.
6. ElGamal signature algorithm.
7. Digital signature algorithm (DSA).
8. Common hash functions.
   1. SHA–1.
   2. MD5.
9. Extending fixed-length hash functions.
   1. Doubling the reduction amount.
   2. A general chaining method.
   3. Hash functions do not always look random.
10. Birthday Attack.
    1. Birthday paradox.
    2. Relevance to hash functions.
11. Hash from cryptosystem.
    1. Techniques for building hash from cryptosystem.
    2. Possible problems with this approach.
12. Authentication using passwords.
    1. Passwords.
       • Insecure when sent in clear.
       • Bob learns Alice’s password during normal use.
    2. Secure password storage.
       • Problems securing storage.
       • Encrypted passwords.
    3. Dictionary attacks.
       • How does it work?
       • Salt.
       • Why does salt help?
13. Authentication while preventing impersonation.
    1. Challenge-response authentication protocols.
       • Basic challenge-response idea.
       • Security problem having Alice sign random strings.
       • Attempts to patch basic protocol.
    2. Simplified Feige-Fiat-Shamir authentication protocol.
       • Relies on difficulty of finding square roots mod n = pq.
       • Alice’s secret is square root of public number.
       • Simple protocol must be repeated.
    3. Cheating Alice.
       • Must fool Bob on each of t rounds.
       • Ability to answer both challenges on some round implies can compute .
       • Otherwise, success probability ≤ 1∕2^t.
    4. Cheating Bob.
       • Restricted query set limits cheating Bob’s power.
       • Cheating Bob only learns random quadratic residue and one square root.
14. Interactive proofs.
    1. Secret cave protocol.
    2. ZKIP for graph isomorphism.
       • Graph isomorphism.
       • Isomorphism problem.
       • Prover (Alice).
       • Verifier (Bob).
       • Why doesn’t Bob learn Alice’s s secret?
    3. Relationship between ZKIP and secret splitting.
    4. Interactive proof of graph non-isomorphism.
       • Non-isomorphism problem is essentially different from isomorphism problem.
       • Form of protocol is quite different.
       • Probably not zero knowledge.
15. Bit commitment.
    1. Definition.
       1. Commitment hides Alice’s bit.
       2. Alice can open her commitment.
       3. Alice can’t reveal incorrect value.
    2. Use of bit-commitment ideas in non-isomorphism protocol.
16. Definition of zero knowledge via simulation.
    1. Zero-knowledge is property of Alice’s protocol only.
    2. Compares power of arbitrary algorithms:
       • That interact with Alice.
       • That do not interact with Alice.
    3. Alice’s protocol is zero knowledge if both kinds of algorithms have same power.
17. Composing Zero-Knowledge Proofs.
    1. Serial execution.
       • Preserves zero knowledge.
       • Many interactions.
    2. Parallel execution.
       • Not provably zero knowledge.
       • More efficient, fewer interactions.
18. Full Feige-Fiat-Shamir authentication protocol.
    1. Combines parallel and serial execution ideas.
    2. Provably zero knowledge when parallelism sufficiently restricted.
    3. Less bandwidth than parallel execution of simple protocol.
19. Non-interactive “interactive” proofs.
    1. Alice simulates interactive proof; sends result to Bob.
    2. Bob needs assurance that Alice can’t “cook” challenge bits.
    3. Allows Bob to impersonate Alice to Carol by replaying proof.
    4. Feige-Fiat-Shamir signatures.
       • Based on non-interactive version of FFS protocol.
       • Uses hash function to generate query bits.
20. Pseudorandom sequence generation.
    1. Concepts:
       • What is a PRSG?
       • Why does the seed need to be random?
       • What does it mean for a string to look random?
    2. Blum-Blum-Shub PRSG
       • Blum integers.
       • BBS algorithm.
21. Notions of randomness.
    1. Indistinguishability.
       • Probabilistic polynomial time Turing machine.
       • Judges.
       • What it means to be a cryptographically strong PRSG.
    2. Next-bit prediction.
    3. Building a judge from a next-bit predictor.
    4. Previous-bit prediction.
    5. Construction of a next-bit predictor from a previous-bit predictor.
    6. Security of BBS PRSG.
22. Secret splitting.
    1. Splitting secret into two shares using XOR.
    2. Splitting secret into multiple shares.
       • Definition of what a (τ,k) threshold scheme is.
       • Lagrange interpolation
       • Shamir’s scheme based on polynomials.
       • Why fewer than τ shares give no information about secret.
    3. Extensions.
       • Verifiable secret sharing.
       • Fault tolerance.
23. Bit-commitment problem.
    1. Terminology and concepts.
       • Commitment, blob, cryptographic envelope.
       • commit(b).
       • open(c).
    2. Commitment using symmetric cryptography.
       • Why one-time pad does not work for bit-commitment.
       • Commitment protocol using suitable symmetric cryptosystem.
       • Commitment protocol using hash functions.
       • Commitment protocol using PRSG.
    3. Abstract bit-commitment schemes.
       • Defining properties.
       • Generic protocol.
24. Coin-flipping problem.
    1. Problem definition.
    2. Solution using blobs.
25. Locked box paradigm.
    1. Coin-flipping using boxes with multiple locks.
    2. Commutative cryptosystems.
       • Definition.
       • RSA variation useful for implementing electronic locked boxes.
       • Security properties of the RSA variation.
    3. Coin-flipping protocol using commutative cryptosystems.
    4. Card dealing using locked boxes.
26. Oblivious transfer.
    1. Oblivious transfer of a secret.
       • The problem.
       • Rabin’s protocol.
       • Potential problem with Rabin’s protocol.
       • Fix using zero-knowledge proof of knowledge of a square root.
    2. One-out-of-two oblivious transfer.
       • The problem.
       • Protocol using two PKS key pairs.