[talks] M Mahmoody Ghidary general exam

[Melissa M Lawson]

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"