PhD Oral Exam - Nan Yang, Computer Science
Non-Local Contamination in Cryptography
This event is free
School of Graduate Studies
When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.
Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.
Non-locality is the phenomenon that two parties are correlated in such a way that cannot be ex- plained by shared randomness, in the absence of communication. In this work, we both attempt to characterize this phenomenon, and explore its consequences, within the context of cryptography. We discover a foundational issue with multi-prover interactive proofs which we call non-local contamination, and we address it. A new characterization of zero-knowledge naturally follows. We construct a practical protocol for NP using spatial separation to instantiate the no-communication requirement of multi-prover interactive proofs. We show that there is a connection between distributed trust and a kind of commitment used in multi-prover protocols. Finally, we analyze a class of neural networks as pseudorandom generators.