** **
CPSC 467b Study Guide for the Final Exam
[Course home page] [Course handouts]
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 467b: Cryptography and Computer Security
 
Professor M. J. Fischer
Handout #22
April 30, 2005
Study Guide for the Final Exam

1  Exam Coverage

The final exam will cover the entire course but with greater emphasis on the topics of the last seven weeks of the course that were not covered by the midterm exam. The course content is 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.
  4. Textbook (Wenbo Mao), relevant sections from chapters 1-3, 5-8, 10-12, 14, 18, 19.
  5. Other resources available in the library and on the web.

2  Review Outline

Below I give a list of topics, concepts, definitions, theorems, algorithms, and protocols that we have covered since the midterm that I expect you to know. This list is not inclusive, as I'm sure I have missed some things. Please refer to the study guide for midterm examination for the topics covered in the first part of the course.
  1. Number theory.
    1. Quadratic residues.
      • Goldwasser-Micali (QR) probabilistic cryptosystem.
      • Legendre symbol.
      • Jacobi symbol.
      • Jacobi symbol identities (don't memorize, but understand what they are).
      • Computing the Jacobi symbol.
    2. Probabilistic primality testing
      • General framework for tests of compositeness (from lecture notes week 5).
      • Fermat test of compositeness ζa(n).
      • Strassen-Solovay test of compositeness νa(n)
      • Miller-Rabin test of compositeness μa(n).
  2. 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.
      • Differences between conventional and digital signatures.
      • Disavowal.
  3. Message digest (hash) functions.
    1. Desired properties.
      • One-way property.
      • Weak collision-free property.
      • Strong collision-free property.
    2. Relations among properties.
  4. Combining signatures with encryption.
  5. ElGamal signature algorithm.
  6. Digital signature algorithm (DSA).
  7. Common hash functions.
    1. SHA-1.
    2. MD5.
  8. Extending fixed-length hash functions.
    1. Doubling the reduction amount.
    2. A general chaining method.
  9. Birthday Attack.
    1. Birthday paradox.
    2. Relevance to hash functions.
  10. Hash from cryptosystem.
    1. Techniques for building hash from cryptosystem.
    2. Possible problems with this approach.
  11. Authentication Problem.
    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?
    4. Challenge-response authentication protocols.
      • Basic challenge-response idea.
      • Security problem having Alice sign random strings.
      • Attempts to patch basic protocol.
    5. 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.
    6. Cheating Alice.
      • Must fool Bob on each of t rounds.
      • Ability to answer both challenges on some round implies can compute √{v−1}.
      • Otherwise, success probability ≤ 1/2t.
    7. Cheating Bob.
      • Restricted query set limits cheating Bob's power.
      • Cheating Bob only learns random quadratic residue and one square root.
  12. Zero knowledge 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?
  13. Relationship between ZKIP and secret splitting.
  14. Interactive proof of graph non-isomorphism.
    1. Non-isomorphism problem is essentially different from isomorphism problem.
    2. Form of protocol is quite different.
    3. Probably not zero knowledge.
    4. Bit commitment.
      • Commitment hides Alice's bit.
      • Alice can open her commitment.
      • Alice can't reveal incorrect value.
    5. Use of bit-commitment ideas in non-isomorphism protocol.
  15. 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.
  16. Composing Zero-Knowledge Proofs.
    1. Serial execution.
      • Preserves zero knowledge.
      • Many interactions.
    2. Parallel execution.
      • Not provably zero knowledge.
      • More efficient, fewer interactions.
  17. 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.
  18. 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.
  19. Secret splitting.
    1. Splitting secret into two shares using XOR.
    2. Splitting secret into multiple shares.
      • Definition of what a (τ, k) threshold scheme is.
      • Shamir's scheme based on polynomials.
      • Why fewer than τ shares give no information about secret.
  20. 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.
  21. Coin-flipping problem.
    1. Problem definition.
    2. Solution using blobs.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. 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.


File translated from TEX by TTH, version 3.66.
On 30 Apr 2005, 12:51.