Mohammad Mahmoody Ghidary will present his research seminar/general exam on Thursday May 24 at 2PM in Room 402. The members of his committee are: Boaz Barak (advisor), Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------- Abstract: ----------------------------------- I will show the first lower-bound on the efficiency of Signature Schemes in the random oracle Model. The lower-bound is tight up to a constant factor for one-time signatures. The current constructions of signatures are considered to be inefficient by practitioners, and the result shows that it is actually inherent. We will see some ideas of the proof. No background is assumed. Reading List: ----------------------------------- The list contains also some papers about another research direction: "Average-case vs Worst-case complexity". General Complexity Theory: The book: "Complexity Theory: A Modern Approach" (by Arora, Bara) Chapters 1 to 9 Advanced Complexity topics: The same book. Chapters: 16: Derandomization, Expanders and Extractors 17: Hardness amplification and error correcting codes 18: PCP and hardness of approximation. General Cryptography: Lecture notes of the Cryptography course by Barak available at: http://www.cs.princeton.edu/courses/archive/fall05/cos433/ Lectures 1-20 Research Papers: --Worst-Case vs Average-Case Complexity: *Feigenbaum, Fortnow. On the random-self-reducibility of complete sets. *Bogdanov, Trevisan. "On worst-case to average-case reductions for NP problems" *Gutfreund, Shaltiel, Ta-Shma. "If NP languages are hard on the worst-case then it is easy to find their hard instances." --The possibility and the efficiency of cryptographic reductions: *R. Impagliazzo and S. Rudich, "Limits on the Provable Consequences of One-Way Permutations" *Reingold, Trevisan, Vadhan "Notions of Reducibility between Cryptographic Primitives" *Katz, Gennaro, Gertner, "Lower Bounds on the Efficiency of Encryption and Digital Signature Schemes" *Gennaro, Trevisan, "Bounds on the Efficiency of Generic Cryptographic Constructions"