We introduce the relationship between incremental cryptography and memory checkers. We present an incemental message authentication scheme based o nthe OXR MACs which supports insertion, deletion and other single block operations. Our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller aluthentication codes than the tree scheme presented in (BGG95). Furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. From this scheme we derive memory chekcers for data structures based on lists. Conversely, we use a lower bound for memory checkers to show that so-called message substitution detcting schemes produce signatures or authentication codes with size proportional to the message length.
展开▼
