Mohammad Mahmoody Ghidary will present his preFPO on Wednesday February 24 at 10:30AM in Room 402. The members of his committee are: Boaz Barak, advisor; Russell Impagliazzo (IAS/UCSD) and Moses Charikar, readers; Sanjeev Arora and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below ------------------------------------------------------------ Title: Security vs Efficiency, NP-hard Primitives, and Unconditional Cryptography. Abstract: The questions that I have studied in my thesis can be divided into the following three categories: I) How efficient a (public key) cryptographic object can be while achieving a desired quantitative level of security? -We give tight lower-bounds on the efficiency of black-box constructions of two of the main public-key cryptographic objects from "random like functions": (1) public key encryption and (2) public key authentication (i.e. signature schemes). II) Since mathematical conjectures like P<>NP are necessary for the possibility of cryptography in the standard model of computation, can we build cryptographic primitives solely by assuming P <> NP, or do we need stronger assumptions? -For some cryptographic primitives such as collision resistant hash functions we prove that basing them on P<>NP through a black-box reduction has surprising implications about the prover complexity of proving co-NP. Also for the more general question of basing average-case hardness of NP on its worst-case hardness we present a connection to the question of whether SAT has program checkers. III) Which non-standard models offer us unconditional security, while being implementable in real life? -We study the possibility of achieving unconditionally secure protocols for the main cryptographic tasks in the model of stateless tokens of Katz. We present unconditionally secure commitment schemes and efficient zero-knowledge proof systems for NP which use only one token and fall into the much simpler model of "Interactive PCP" by Kalai-Raz. We also prove that unconditionally secure oblivious transfer is not possible in the full general form of the stateless token model.