Database Authentication Revisited

Database authentication via cryptographic checksums represents an important approach to achieving an affordable safeguard of the integriry of data in publicly accessible database systems against illegal manipulations. This paper revisits the issue of database integrity and offers a new method of safeguarding the authenticity of data in database systems. The method is based on the recent development of pseudo-random function families and sibling intractable function families, rather than on the traditional use of cryptosystems. The database authentication scheme can be applied to records or fields. The advantage of the scheme lies in the fact that each record can be associated with one checksum, while each data element in the record can be verified using the checksum independently of the other data elements in the record. The security of the scheme depends on the difficulty of predicting the outputs of pseudo-random functions and on inverting the sibling intractable function family. The same approach can also be applied to the generation of encipherment keys for databases.