All reports by Author Phong Nguyen:

__
TR05-017
| 28th January 2005
__

Phong Nguyen#### Two-Sorted Theories for L, SL, NL and P

__
TR98-010
| 22nd January 1998
__

Phong Nguyen, Jacques Stern#### A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1

Phong Nguyen

We introduce ``minimal'' two--sorted first--order theories VL, VSL, VNL and VP

that characterize the classes L, SL, NL and P in the same

way that Buss's $S^i_2$ hierarchy characterizes the polynomial time hierarchy.

Our theories arise from natural combinatorial problems, namely the st-Connectivity

Problem and the Circuit Value Problem.

It ...
more >>>

Phong Nguyen, Jacques Stern

Recently, Ajtai discovered a fascinating connection

between the worst-case complexity and the average-case

complexity of some well-known lattice problems.

Later, Ajtai and Dwork proposed a cryptosystem inspired

by Ajtai's work, provably secure if a particular lattice

problem is difficult. We show that there is a converse

to the ...
more >>>