On Necessary and Sufficient Cryptographic Assumptions:
            the Case of Memory Checking

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.


BIBLIOGRAPHY: A lot of background and relevant material is available in