Lecturer: Moni Naor
When: Monday 9:30--11:00 DESCRIPTION:
This is the home page
for a series of lectures to be given
at the Ecole normale supérieure
April-May 2005.
One-way functions are easy to compute one-way but given an image
it is computationally hard to find a corresponding pre-image. Key
results over the last twenty years have shown that the existence
of one-way functions is equivalent to many other primitives such
as pseudo-random generators. In this series of lectures I plan to
consider the question of which tasks require the assumption that
one-way functions exist.
In particular I plan to deal with the problem of memory checking
where a small and secret memory should be used to check a large
and unreliable one. For this problem good schemes based on
the existence of one-way functions are known. In recent work with
Guy Rothblum
we showed a lower bound for memory checking when
the adversary is not computationally bounded. If the large
memory size is n, the small memory size is s and each operation
involves reading t bits, then s x t= Omega(n). This bound can
be circumvented if and only if one-way functions exist.
The lower bound uses some results on communication complexity and
computational learning, which I plan to cover as well.
SLIDES:
BIBLIOGRAPHY:
A lot of background and
relevant
material is available in PAPERS:
A good source on communication
complexity is:
A paper that is always good to read: