1  Exam Coverage

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 4: Number theory summary.
   • Handout 5: Linear congruence equations.
   • Handout 6: The Legendre and Jacobi symbols.
   • Handout 21: Pseudorandom sequence generation.
4. Textbook (Trappe and Washington), relevant sections from chapters 6-10, 12-14.
5. Other resources available in the library and on the web.
6. Problem sets and solutions.

2  Review Outline

1. Number theory.
   1. Primitive roots.
      • Lucas test.
      • Discrete logarithm.
   2. 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.
      • Legendre symbol.
      • Jacobi symbol.
      • Jacobi symbol identities (don't memorize, but understand what they are).
      • Computing the Jacobi symbol.
   3. Probabilistic primality testing
      • General framework for tests of compositeness (from lecture notes 11).
      • Fermat test of compositeness ζ_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 √{v⁻¹}.
       • 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. 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.
21. 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.
22. Coin-flipping problem.
    1. Problem definition.
    2. Solution using blobs.
23. 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.
24. 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.
25. 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.
26. 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.
27. Kerberos.
    1. Parties involved: Trusted server, Alice, Bob.
    2. Uses symmetric cryptography only.
    3. Simplified protocol (see notes).
       • Nonce.
       • Timestamp.
       • Lifetime.
       • Ticket.
       • Authenticator.
       • Why is authenticator needed? Why isn't a ticket enough?
    4. Security of Kerberos.
       • What kinds of attacks was Kerberos designed to resist?
       • What kinds of attacks is it possibly subject to?
    5. Practical considerations in real protocol.
28. Secure shell (SSH)
    1. Purpose: secure communication between terminal and server.
    2. Asymmetric cryptography used for authentication and key exchange.
    3. Traffic encrypted with randomly-generated session key.
    4. Designed for ease of use.
29. Secure socket layer (SSL)
    1. Encrypts traffic at the ISO transport layer.
    2. Basis for Transport Layer Security (TLS) protocol (compatible with SSLv3).
    3. Operates between peers.
    4. Uses X.503(v3) certificates to obtain public keys.
    5. Performs secure key exchange to establish a session key.
30. Elections
    1. The election problem.
       • Voting systems.
       • Voting system error.
       • Voter intent as a discrete choice.
       • Voter intent as a probability distribution.
       • Statistical voter error.
    2. Shamos's axioms for voting systems.
       • How Shamos's axioms are satisfied with conventional voting systems.
       • Problems with computerized voting terminals.
    3. Internet voting.
       • Challenges to Shamos's axioms.
       • Voting with two partially-trusted central facilities.
       • Peralta's scheme.