Restricted fully private conjunctive database query for protection of user privacy and identity

Abstract

A method of securely accessing a database with sensitive data, such as the clinical information of patients, by a client in a privacy-preserving manner, including: communicating with the server to obtain tags for specific attribute-value pairs when the client is authorized to make a query; imposing a tag quota per client and restricting tag generation to authorized query terms with valid digital signatures from a third-party authority; storing the tags and their associated query terms in confidence for future queries; sending a combination of tags that define the terms of a conjunctive query over a secure channel to a proxy; receiving from the proxy encrypted coefficients of a polynomial whose roots are indices to the query results; decrypting the encrypted coefficients in a first protocol with the server; calculating the roots of the polynomial based upon the decrypted coefficients and discarding any superfluous roots; obtaining the encrypted records associated with the calculated roots from the proxy; and decrypting the encrypted records in a second protocol with the server.