CS Theory @ Princeton : Main / Crypto Seminar

Cryptography Seminar / Reading Group

Mondays 4:30-6pm Room 302 in CS building

Organizer: Boaz Barak

We'll have student presentations of papers suggested by me or them. The time and frequency will be determined based on how many students are interested. I prefer that rather than presenting a single paper, 1-2 students will read 2-3 papers relating to one topic, discuss them with me, and then give 1-2 lectures on this topic.

If you are interested in participating:

• Join the crypto-seminar mailing list. You can join this mailing list even if you don't plan on presenting a paper, if you want to be notified about talks in the seminar (or crypto related talks in other nearby seminars).
• Email me to let me know you are interested. Please use crypto-seminar in the subject line. Tell me if you'll be willing to present a paper.

Schedule

• Monday Feb 13th: Witness Indistinguishability and Constant Round Zero Knowledge - Boaz Barak notes
• Monday Feb 20th: Non Interactive Zero Knowledge (NIZK) - Boaz Barak (Goldreich Vol I)
• Monday Feb 27th: Multiple-Proof NIZK. High level overview of themes from TCC 06 - Boaz Barak
• Monday March 6th: no lecture - I recommend everybody go to TCC 2006 in New York. It'll be on Sunday till Tuesday of that week. On Monday Omer Reingold and I will give tutorials on black-box and non-black-box reductions in cryptography.
• Monday March 13th: Construction of Simulation Sound NIZK - Mohammad Mahmoody
• Monday March 27th: Construction of CCA-Secure Puublic Key Encryption - Mohammad Mahmoody
• Monday April 3rd: If you can't prove it, prove that no one can prove it (assuming <insert complexity assumption here>) - Dave Xiao
• Monday April 10th: Dave Xiao (continued from April 3rd)
• Monday April 17th, April 24th: Concurrent Zero Knowledge in O(log n) rounds - Jimin Song
• Monday May 1st, Yao's Scrambled Circuit Protocol for Two Party Secure Computation - Janek Klawe

Possible topics

(very partial list, at the moment only few references. Contains references for newer or possibly better-written sources, rather than to the original papers in each topic.)

You should also try to look for interesting topics yourself. Some places to search are advanced cryptography classes such as the following: Leo Reyzin , Jon Katz, Shafi Goldwasser , Tal Malkin, Silvio Micali , Daniele Micciancio , (2) (list of topics by Eran Tromer )

• Important tools [Goldreich's book]

1. Witness Indistinguishability Feige's thesis , FS90
2. Non-interactive zero knowledge

• Chosen-ciphertext security:

1. CCA2 secure scheme based on TDP (simplest construction is in this paper by Lindell)
2. Cramer-Shoup CCA2-secure crypto system. See also analysis by Elkind and Sahai

• Lattice-based cryptosystems. See Regev05 , Regev04 , RegevMicciancio04
• Basing cryptography on P vs. NP BT03 , AGGM06 (relates also to Lattice-based cryptography)
• Random oracle methodology CGH98 (there are many more open problems than results in this area, see BLV03 for some of these open problems)
• Constant round zero knowledge [Goldreich's book]
• Concurrent zero knowledge Rosen's thesis, CKPR01, PRS03
• Secure function evaluation [Goldreich's book]
• Multiple server private information retrieval CGKS95 , BIKR02
• Privacy-preserving databases. DMSNS06 , CDMSSW05
• Physically observable cryptography MR04 , ISW03
• Cryptography and game theory Silvio Micali's course, HT04, LMS04 , IML05
• Subexponential factoring algorithms, specialized hardware for factoring.
• Formal/Symbolic analysis of cryptographic protocols Daniele Micciancio's course , see also Shai Halevi's suggestion , Shoup04, BR04
• Side channel attacks Manger01, OST06 see also refs in this page
• Statistical zero knowledge Vadhan's thesis ,

(Next two topics will be subject of TCC 2006 tutorials)

• Black-box separations of cryptographic primitives. IR89 , GKMRV00
• Non-black box zero knowledge my thesis