SSSDB: Database with Private Information Search

This paper presents searchable secret shares SSS, a novel method to search and collect statistics about private information quickly without retrieving secretly shared data, which is stored in public clouds separately. The new capabilities of SSS serve as a base for a newly defined SSS database SSSDB with reduced communication overhead and better security compared with private information retrieval PIR based databases. Clouds know neither the database stored in their disks nor the searched patterns and the results. Unlike PIR based databases, SSSDB does not need to maintain an access data structure for mapping keys to indexes performing inserts and deletes in the user memory, and therefore avoids possible information leakage. SSSDB is information-theoretically secure and can be implemented using a small integer field which implies high memory and computation efficiencies.