I&C Journal 2007 Journal Article
- Noga Alon
- Haim Kaplan
- Michael Krivelevich
- Dahlia Malkhi
- Julien Stern
Introduction. We consider the following problem. A file of size s bits is to be stored on n disks. Our failure model assumes that a potentially malicious adversary may choose after the file is stored less than half of the disks, and arbitrarily alter the data they store. The adversary is constrained in its computation power, which is assumed to be polynomial. Note that this disk-corruption model is different from the classical fault model for error correcting codes, in which individual bits experience faults independently. The goal is to store the file on the disks in such as way that recovery of the file is possible despite the corruption with high probability, where probability is over the choices of data alterations made by the adversary. With guaranteed correct recovery, standard methods from coding theory indicate a lower bound of sn total storage bits (on all disks together). However, if we allow negligible probability of error, more compact schemes are possible (see a survey of known approaches in [1]). More concretely, the probabilistic relaxation of recovery guarantee allows the use of a cryptographically secure hash function, such as the conjectured collision-resistant hash function SHA-1 [7], in order to probabilistically fingerprint data. This works as follows: During storage time, digests of certain data values are stored, such that a polynomially bounded adversary has negligible probability of consistently modifying the data without mismatching its digest. The probability of false-match is typically very small, e.g., 2−160 with SHA-1, and is not dependent on other system parameters like n. Therefore, from here on, we neglect this probability of error in our exposition, and simply say that if a certain data matches an (unaltered) pre-stored digest, then w.h.p. the data is unaltered. The scheme we previously suggested in [1] 1 requires holding for the fingerprinting information a total storage of O(n log n) bits. Our scheme employs expander graphs for redundant cross-checking of fingerprint values. Some of the techniques in [1] may have other applications. In particular, Theorem [1] [4.1] demonstrates the robustness of an LPS expander [3] against deletion of half of the vertices, improving on the numerical constants of a similar result by Upfal in [8]. In this addendum, we demonstrate a simple solution, which is an application of Merkle hashtrees [4, 5]. The solution is asymptotically as efficient as the method in [1], works even for small n, and has much smaller (and no hidden) constants. In the remainder of this exposition, we describe the building blocks of the solution and combine them together to obtain the full scheme.