CAS 762: Cryptography
Fall 2010


Assignments and presentations:

List of Projects

Project Nr. Project Title Speaker Date
Material for the following three projects can also be found in "An introduction to mathematical cryptography", Hoffstein, Pipher, Silverman (HPS henceforth). The 3 cryptosystems are mentioned in the first paragraph of page 383, and more detailed citations than here are given.
1 Ajtai-Dwork cryptosystem Read the paper: M. Ajtai & C. Dwork, "A public-key cryptosystem with worst-case / average-case equivalence" in STOC 1998.
2 GGH cryptosystem Read the paper: O. Goldreich, S. Goldwasser, S. Halevi, "Public-key cryptosystems from lattice reduction problems" in Advances in Cryptology, CRYPTO 1997. Also section 6.8 in HPS. Mohamed Sabry Sept 29
3 NTRU cryptosystem Read the paper: J. Hoffstein, J. Pipher, J.H. Silverman, "NTRU: a ring-based public key cryptosystem" in Algorithmic Number Theory 1998. Also section 6.10 in HPS. Xiang Yin Oct 13
The following two projects are based on two papers of Ajtai on hard lattice problems.
4 M. Ajtai, "Generating hard instances of lattice problems", ECCC TR96-007.
5 M. Ajtai, "The shortest vector problem in L_2 is NP-hard for randomized reductions", ECCC TR97-046. In particular, understand why SVP is NP-hard under the "randomized reduction hypothesis" (which from footnote 5, page 371, in HPS seems to say that P is properly contained in ZPP - using standard complexity theoretic terminology). I find this very intriguing. Tim Paterson Nov 3
The following projects have a complexity flavor.
6 Show that CVP is NP-hard (this is related to 5 above).
7 SVP is not harder than CVP O. Goldreich, D. Micciancio, S. Safra, J.P. Seifert, "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors", Information Processing Letters 1999 ([45] in HPS)
8 An overview of the complexity of lattice problems D. Miccancio and S. Goldwasser, "Complexity of Lattice Problems" ([77] in HPS)
The following is really a linear algebra project.
9a LLL algorithm Section 6.12.2; first understand the Gaussian lattice reduction algorithm in 2 dimensions (Ariel & I gave a proof that the Gaussian algorithm runs in polynomial time). Then LLL is easier to understand. This project is really covering section 6.12 & 6.13 in HPS, which have some very beautiful mathematics. Peter Kandolf Oct 13
9b Correctness of the LLL algorithm. This is theorem 6.68, pg 413, in the textbook, but notice that the proof given there is incomplete, in the sense that it assumes that L is a subset of Z^n, whereas in the general case it is a subset of R^n. For a full version, see Factoring polynomials with Rational Coefficients by Lenstra, Lenstra and Lovasz, 1982. Peter Kandolf Nov 10
Assorted projects.
11 Homomorphic encryption, based on an article in the Communications of the ACM "Computing Arbitrary Functions of Encrypted Data" by Craig Gentry, March 2010, vol 53, no 3 Mohamed Sabry Nov 24
12a Enigma machine In the 1920s, the encryption generated by the Enigma machine was believed to be unbreakable---with a theoretical number of ciphering possibilities of 3x10^{114}, that belief was not unjustified. The Enigma machine based its cipher capabilities on a series of wired rotor wheels and a plugboard. Through a web of internal wiring, each of the twenty-six input contacts on the rotor were connected to a different output contact. The wiring connections of one rotor differed from the connections on any other rotor. Yet, the Enigma ciphers were broken during WWII at Bletchley Park. Jason Jaskolka Oct 6
12b Breaking the code of the Enigma machine. Jason Jaskolka Nov 3
13 Hash functions Cryptographic hash functions such as SHA-1 or MD5 are widely used in cryptography. In digital signature schemes, messages m are first hashed and the hash value h(m) is signed in place of m. Hash values are used to check the integrity of public keys. Pseudorandom bit strings are generated by hash functions. When used with a secret key, cryptographic hash functions become message authentication codes (MACs), the preferred tool in protocols like SSL and IPSec to check the integrity of a message and to authenticate the sender. Tim PatersonSept 29
14 The Gnu Privacy Guard, GnuPG, also known as GPG, is a complete and free implementation of the OpenPGP standard---which is the most widely used email encryption standard in the world. The OpenPGP standard was originally derived from PGP (Pretty Good Privacy), first created by Phil Zimmermann in 1991. Guohong Rong Oct 20
15 Holomorphic encryption - pg 97 in ACM Comm. vol 53, no 03 Examples of applications: m1, are k votes, compute c=E(m1,...,mk), compute from c the number of yes votes, c', and send c' without knowing what this number is. OR a search engine might receive an encrypted query; process it, without knowing what it is, and send back the encrypted answer - cloud computing.
16 SVP, CVP vs. GLRAlg (Gaussian Reduction Algorithm), BabAlg (Babai's Algorithm). Ariel Fernandez Oct 6
17 Symmetric key cryptography: DES and AES. Ariel Fernandez Nov 17
18 Active research seminar: Covert Channels.
This will be Jason's 3rd talk; I have asked Jason to repeat his excellent cryptography seminar from Oct 13
Jason Jaskolka Dec 1
19 Digital cash. References: chapter 4.5 (pg 115) in "Introduction to Cryptography" by Delfs & Knebl, as well as Camenisch, Maurer & Stadler, "Digital payment systems with passive anonimity revoking trustees", Lecture Notes in Computer Science, 1996. Xiang Yin Dec 1
20 Bilinear pairings on elliptic curves Guohong Rong Nov 24