CMSC858K --- Spring 2003 --- Lecture Schedule

• [Lecture 1] Introduction, Private-Key Encryption
  Introduction. Private-key encryption and perfect secrecy. Toward a computational notion of security.
  
  References: [BR, Chapter 7]; [DK, Sections 9.1, 9.2]
  
  
• [Lecture 2] Computational Secrecy for Private-Key Encryption
  Probabilistic polynomial-time (PPT) adversaries and negligible functions. A computational notion of secrecy for private-key encryption. Definition of one-way functions and some examples from number theory.
  
  References: One-way functions are discussed in [DK, Chapters 5, 6] and [GB, Chapter 2]. Various reviews of number theory are available, including: [BR, Chapters 7, 8], [Katz], [Shoup], and [Angluin]. Weak one-way functions (mentioned briefly in class) are covered in more detail in [G, Sections 2.2, 2.3].
  
  
• [Lecture 3] More on One-Way Functions and Permutations
  A one-way permutation based on squaring modulo N, and proof that this is one-way if and only if factoring is hard. Beginning of proof that (non-trivial) private-key encryption implies existence of one-way functions.
  
  References: The squaring permutation was introduced in [Rabin79]. A proof that this is indeed a permutation is given in [GB, Section 2.3.5] and also Lecture 7 from last semester. A proof that this is one-way iff factoring is hard appears in [DK, Proposition A.59], [GB, Section 2.3], and Lectures 7, 8 from last semester.
  
  
• [Lecture 4] Private-Key Encryption Implies One-Way Functions
  Non-trivial private-key encryption implies private-key encryption in which the message is much longer than the key. The "hybrid argument". Continuation of proof that private-key encryption implies one-way functions.
  
  References: The result that private-key encryption implies OWF was first given by [IL89], but the proof given in class is from [GGK03]. The "hybrid" argument is frequently used in cryptography, and examples of its use can be found in [BR, Section 9.3] or [GB, Section 7.4.3]; see also Lecture 32 from last semester.
  
  
• [Lecture 5] A Hard-Core Bit From Any One-Way Function
  Definition of a hard-core bit. The Goldreich-Levin construction and some intuition for the proof.
  
  References: Hard-core bits (called predicates) are discussed in [DK, Section 6.8] and [GB, Section 2.4]. The result of Goldreich and Levin [GL89] is proven in full in [G, Section 2.5]. A much easier proof (for a much weaker result) which gives some intuition for the full proof is given in this handout by Trevisan.
  
  
• [Lecture 6] From Hard-Core Bits to Pseudorandom Generators
  A proof of a simpler version of the Goldreich-Levin result (see the handout by Trevisan, above). Definition of security for cryptographic pseudorandom number generators (PRGs). Constructing a PRG with 1-bit expansion from any one-way permutation.
  
  References: PRGs are covered in [GB, Chapter 3] and [DK, Section 8.1].
  
  
• [Lecture 7] PRGs and Their Applications to Private-Key Encryption
  From PRGs with 1-bit expansion to PRGs with arbitrary (polynomial) expansion. Using PRGs for non-trivial private-key encryption. Is security against ciphertext-only attacks sufficient? Introduction to pseudorandom functions (PRFs).
  
  
• [Lecture 8] PRFs: Definitions and a Construction
  Definition of a PRF. Construction of a PRF from any one-way function, using PRGs. A stronger notion of security for private-key encryption: security against chosen-plaintext attack.
  
  References: PRFs were introduced and first constructed in [GGM84] (see also [G, Section 3.6] and [GB, Chapter 5]). A slightly different (non-asymptotic) approach is given in [BR, Chapter 3].
  
  
• [Lecture 9] Private-Key Encryption Secure against Chosen-Plaintext Attacks
  Construction and proof of security for an encryption schere secure against chosen-plaintext attacks. Extending an encryption scheme for "short" messages to an encryption scheme for longer messages. Pseudorandom permutations and their construction.
  
  References: The encryption scheme given in class was introduced by [GGM84b] and is discussed (briefly) in [G, Section B.1.2.1] and [GB, Section 6.12.1]. More detail appears in [G, vol 2, Section 5.3.3]. The transformation from a PRF to a PRP is based on the "Feistel network" used in the construction of DES. The analysis showing that 3 iterations gives a PRP (and 4 gives a strong PRP) is due to Luby and Rackoff [LR85], and the proof also appears in [G, Section 3.7.2]. There has also been a lot of work since then on improving the efficiency or security of the Luby-Rackoff construction; see me if you are interested in references.
  
  
• [Lecture 10] Private-Key Encryption. Identification Schemes
  Strong PRPs and their construction from PRFs. Block ciphers. The CFB mode of encryption. Introduction to identification schemes: definitions, notions of security, and a private-key construction. A public-key identification scheme.
  
  References: Strong PRPs are defined and constructed in [LR85], and further discussion appears in [G, Section 3.7]. Identification schemes are covered in [DK, Section 4.2]. The private-key scheme presented today is from [GGM84b], and is also discussed in [GB, Section 5.12.4]. The public-key scheme presented today appears in [DK, Section 4.2.2], and is a simplification of the Fiat-Shamir identification scheme [FS86].
  
  
• [Lecture 11] Identification Schemes
  Proof of security for a basic scheme against a "weak" form of attack. Extending this to a proof of security against passive eavesdropping. Reducing the adversary's success probability by parallel repetition. Consideration of active attacks and obtaining a proof of security for this case.
  
  References: [FS86] and [DK, Section 4.2], as before.
  
  
• [Lecture 12] Identification Schemes
  An identification scheme consisting of sequential repititions of the "basic" protocol. A proof of security against weak attacks. Extending this to a proof of security against active attacks. Brief mention of zero-knowledge.
  
  References: [DK, Section 4.2], as before.
  
  
• [Lecture 13] An Identification Scheme Based on the Discrete Logarithm Problem
  An identification scheme based on the discrete logarithm problem which is secure against passive attacks. Extending the scheme to give a 3-round protocol which is provably-secure against active attacks.
  
  References: The ID-scheme secure against passive attacks is due to Schnorr [S89], and is described (in another context) in [DK, Section 4.5.1]. Extending the scheme to be secure against active attacks was done by Okamoto [O92].
  
  
• [Lecture 14] Signature Schemes
  Completion of proof of security for the Okamoto-Schnorr identification scheme against active attacks. Signature schemes and their relation to identification schemes: a 2-round identification scheme from any signature scheme. The Lamport one-time signature scheme.
  
  References: [DK, Section 10.1] has some basic information about signature schemes; other references include [BR, Chapter 9] and [GB, Chapter 9]. Diffie and Hellman mention the concept of digital signatures in their seminal paper [DH76], but the first paper to formally define the desired security properties of signature schemes (and the first to give a provably-secure construction under any assumption) was [GMR84]. The Lamport scheme is covered in detail in Lecture 36 from CMSC 456.
  
  
• [Lecture 15] Signature Schemes
  Trapdoor permutations. The Diffie-Hellman suggestion for secure signatures based on trapdoor permutations and three attacks on this approach. Two methods for extending the Lamport scheme to securely sign multiple messages (larger public key and chain-based approach), their advantages, and their drawbacks. Collision-resistant hash functions.
  
  References: More information about the RSA and Rabin (squaring) trapdoor permutations appears in [DK, Chapter 6] --- in particular, they discuss how to compute square roots modulo N when the factorization of N is known in Section 6.5. Collision-resistant hash functions are covered in [DK, Section 10.2].
  
  
• [Lecture 16] A Signature Scheme Based on Minimal Assumptions
  Improving the signature schemes from last time. Review of collision-resistant hash functions and introduction to universal one-way hash functions. The end result: a stateless scheme for arbitrarily-many messages, with all parameters polylogarithmic in the number of messages signed, and whose security is based on one-way functions! A brief introduction to the random oracle model.
  
  References: For more details regarding the lecture, see Lectures 36, 37, 38 from CMSC 456. The efficiency improvements sketched today are taken from [G86].
  
  As I mentioned in class, signature schemes have an interesting history (and are still an active area of research). For a while, it was believed that constructing a secure signature scheme was impossible! However, [GMR84] showed how they could be constructed based on a specific assumption. The required complexity assumption was improved in a sequence of results: [BM92] base signatures on trapdoor permutations, [NY89] use only one-way permutations, and [R90] shows that one-way functions are necessary and sufficient. The practical signature scheme that I briefly mentioned in class is by [CS99]; we may cover this later in the semester if there is time.
  
  
• [Lecture 17] The Random Oracle Model
  Introduction to the random oracle model; advantages and drawbacks of this model. A signature scheme in the random oracle model. Using the Fiat-Shamir transformation to convert identification schemes to signature schemes.
  
  References: Although the idea of using a "random function" in cryptographic protocols goes back at least to [FS86], it was [BR93] who popularized the random oracle model and were the first to rigorously analyze efficient protocols in this model. The signature scheme covered in class is described and proven secure in [BR93].
  
  
• [Lecture 18] The Fiat-Shamir Transform
  Discussion of the Fiat-Shamir transformation, which constructs signature schemes from certain types of public-key identification schemes. Proof of security for this transformation.
  
  References: The Fiat-Shamir transformation was introduced in [FS86]; the proof of security given in class is based on [AABN02]. The Fiat-Shamir transformation is described (in the context of the Fiat-Shamir identification protocol) in [DK, Section 4.2.5].
  
  
• [Lecture 19] Public-Key Encryption
  Definition of public-key encryption and security. Two definitions of security and their equivalence. A review of some number theory (quadratic residues, Legendre/Jacobi symbols, etc.)
  
  
• [Lecture 20] A Secure Public-Key Encryption Scheme
  A secure public-key encryption scheme based on the hardness of deciding quadratic residuosity. Basing secure public-key encryption on arbitrary trapdoor permutations.
  
  References: The encryption scheme based on the hardness of deciding quadratic residuosity is based on the first secure public-key encryption scheme due to Goldwasser and Micali [GM84].
  
  
• [Lecture 21] Efficient Public-Key Encryption Schemes
  Public-key encryption from any trapdoor permutation. The CDH and DDH assumptions and the El Gamal encryption scheme. Security against chosen-ciphertext attacks, and motivation for the definition.
  
  
• [Lecture 22] Interactive Proofs
  Examples of chosen-ciphertext attacks against the encryption schemes we have seen thus far. Brief review of P, NP, NP-complete, and coNP. Interactive proof systems, and classifying P/NP by the round complexity of their interactive proofs.
  
  References: For more information about chosen-ciphertext attacks, see: the paper describing the only known efficient encryption scheme which is provably-secure against chosen-ciphertext attacks or another paper describing a scheme in the random oracle model (a variant of which is used extensively in practice).
  
  An introduction to interactive proofs is given in [G, Section 4.2]. The rest of [G, Chapter 4] contains extensive discussion of zero-knowledge proofs. Other references for interactive proofs include: the book "Computational Complexity" by Papadimitriou, various notes by Goldreich, and a book on the subject by Goldreich.
  
  
• [Lecture 23] (tentative) Interactive Proofs, Zero-Knowledge Proofs, and Proofs of Knowledge
  An interactive proof for graph non-isomorphism. A zero-knowledge proof of graph isomorphism. ZK proofs for NP in O(k) rounds. Honest-verifier ZK proofs for NP in 3 rounds. Commitment schemes and constant-round ZK proofs for NP. Proofs of knowledge. Non-interactive zero-knowledge proofs for NP.
  
  
• [Lecture 24] (tentative) Introduction to Secure Computation
  Coin-flipping protocols. (Informal) definition of secure computation for honest-but-curious and malicious adversaries. Oblivious transfer. Two-party protocols for secure computation of deterministic functionalities.
  
  
• [Tuesday, May 13] Final exam, in class