Distributed fingerprints and secure information dispersal

Abstract

We present a solution to the problem of information integrity protection in distributed systems which is robust against malicious parties, is space and communication efficient, and uses cryptography in a minimal way. Our solution builds on Rabin's information dispersal algorithm (IDA). While the IDA scheme is able to deal with missing pieces of information, here we solve the more general secure information dispersal problem, in which recovery of information is possible even against modification of information shares by a possibly malicious adversary. Previous solutions to this problem suffer from space and communication blowup, or use costly cryptographic tools that limit the usefulness of the scheme. In contrast, our scheme uses cryptography in a `minimal' way. It gets rid of the need of private and public key systems and, actually, requires no secret keys at all. It permits recovery of the distributed information by any party in the system, and at the same time prevents any modification or loss of information, as long as a honest majority of parties exist. The proposed solution is space optimal and flexible enough to replace the basic IDA algorithm in most applications that contemplate general faults. Our solution introduces a new cryptographic tool called distributed fingerprints, which consists of public fingerprints for data integrity having the `paradoxical' property that everyone in the system can compute them (using the same function and no secrets!) but no one can forge them. Distributed fingerprints may replace some of the (integrity) functions provided by signatures in distributed systems, but at a lower cost.