| 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 Paterson | Sept
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,...mk 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
|
