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

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:

• Lecture 1: Identification and One-way functions. Weak, strong and distributional one-way functions are equivalent. pps
• Lecture 2: Authentication and Communication Complexity . pps
• Lecture 3: Memory Checking: offline and online variants. The Consecutive Messages Model . pps
• Lecture 4: Learning Adaptively Changing Distributions. Lower bound on Online Memory Checking. . pps

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

• Oded Goldreich, Foundations of Cryptography, Cambridge, 2001.

A good source on communication complexity is:
• E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge 1997.
  

A paper that is always good to read:
• R. Impagliazzo, A Personal View of Average-Case Complexity. Postscript

PAPERS:

• Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor: Checking the Correctness of Memories, Algorithmica 12(2/3): 225-244 (1994), Postscript , gzipped Postscript
• Moni Naor and Guy N. Rothblum, The Complexity of Online Memory Checking, Postscript ,    gzipped Postscript
• Moni Naor and Guy N. Rothblum. Simulating Secret Knowledge: The Learnability of Adaptively Changing Distributions, Postscript , gzipped Postscript