[talks] M Mahmoody Ghidary preFPO
mml at CS.Princeton.EDU
Fri Feb 19 09:23:08 EST 2010
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
Security vs Efficiency, NP-hard Primitives, and Unconditional Cryptography.
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
-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.
More information about the talks