## 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.