Certified Information Access

Certified Information Access (CIA) primitive allows a user to obtain answers to database queries in a way that she can verify the correctness of the received information. The database owner answers a query by providing the information matching the query along with a proof that such information are consistent with the actual content of the database. Current solutions to this problem require a computationally intensive setup phase. We describe two secure distributed implementations of a CIA service. In the first one, the database owner distributes the evaluation of a computation intensive function (e.g., exponentiations) among a set of untrusted peers and locally reconstructs the result of such an evaluation. In the second one, we propose a protocol for securely outsourcing the whole computation of the data structures used in the implementations of the CIA primitive. In this case, the main issue to be considered is the need of guaranteeing on the one hand the confidentiality of the database contents and, on the other hand, the correctness and soundness of the answers obtained by the users. We argue that classical cryptographic primitives are not sufficient for our purposes and we introduce a new primitive, the Verifiable Deterministic Envelope, that may be of independent interest.