Anonymous and verifiable databases: towards a practical solution

In this paper we describe a practical solution towards anonymous and verifiable databases based on the use of the recent Improved Leighton- Micali protocol for the distribution of keys. The scheme is addressed particularly to public data held in separate government databases with the aim of preventing unauthorized government agents from gathering and merging private data concerning individuals from these separate containers. The solution can be realized through the recent Clipper Chip and smartcard technology, and its security relies on the strength of these technologies. The scheme is also extendible mobile information systems.