Noam Livne

Abstract of PhD Thesis (Weizmann Inst., 2010)

Title: From Computational Complexity to Cryptography and to Game Theory

Available: the thesis (in PDF).

The works in this thesis are spanned over the historical development in the approach to cryptography: from information-theoretic cryptography, to computational cryptography, and up to the new approach of rational cryptography.

In the first chapter we prove lower bounds on the size of shares in perfect secret sharing schemes. We do so for matroidial access structures, using non-Shannon inequalities, by this circumventing impossibility results regarding Shannon-inequalities. Our work sheds some light on the problem of proving stronger lower bounds for perfect secret sharing schemes, which is open for a long time.

In the second chapter we contribute to the theory of average-case complexity initiated by Levin in 1984, by proving that all natural NP-complete decision problems have average-case complete versions. While this widens the class of average-case complete distributional problems, the resulted problems do not seem as natural as one might have expected.

In the third chapter we consider the possibility of basing one-way functions on average-case hardness. We consider constructing samplers that yield one-way functions from samplers that output hard-on-average instances. We show limitations on this approach.

Finally, in the last chapter we propose a new solution concept for the modeling of cryptographic protocols as extensive games. Our solution concept is the first that is both sequential and computational. As an application of our new definition we revisit the problem of removing the mediator from a correlated equilibrium. We show a new protocol that works for a non-trivial class of correlated equilibria, that achieves sequential rationality.

Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, August 2010.

Available: the thesis (in PDF).

Back to Oded Goldreich's homepage.