[talks] M Mahmoody Ghidary preFPO

[Melissa Lawson]

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.