International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Maithili Narasimha

Publications

Year
Venue
Title
2005
EPRINT
DSAC: An Approach to Ensure Integrity of Outsourced Databases using Signature Aggregation and Chaining
Maithili Narasimha Gene Tsudik
Database outsourcing is an important emerging trend which involves data owners delegating their data management needs to an external service provider. In this model, a service provider hosts clients' databases and offers mechanisms to create, store, update and access (query) outsourced databases. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. A core security requirement is the integrity and authenticity of outsourced databases. Whenever someone queries a hosted database, the results must be demonstrably authentic (with respect to the actual data owner) to ensure that the data has not been tampered with. Furthermore, the results must carry a proof of completeness which will allow the querier to verify that the server has not omitted any valid tuples that match the query predicate. Notable prior research (\cite{DpGmMcSs00, McNgDpGmKwSs02, PanTan04}) focused on so-called \textit{Authenticated Data Structures}. Another prior approach involved the use of special digital signature schemes. In this paper, we extend the state-of-the-art to provide both authenticity and completeness guarantees of query replies. Our work also analyzes the new approach for various base query types and compares the new approach with Authenticated Data Structures.\footnote{We also point out some possible security flaws in the approach suggested in the recent work of \cite{PanTan04}.}
2004
EPRINT
Signature Bouquets: Immutability for Aggregated/Condensed Signatures
Einar Mykletun Maithili Narasimha Gene Tsudik
Database outsourcing is a popular industry trend which involves organizations delegating their data management needs to an external service provider. In this model, a service provider hosts its clients? databases and offers mechanisms for clients to create, store, update and access (query) their databases. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. This paper focuses on integrity and authenticity issues in outsourced databases. Whenever someone queries a hosted database, the returned results must be demonstrably authentic: the querier needs to establish ? in an efficient manner ? that both integrity and authenticity (with respect to the actual data owner) are assured. To this end, some recent work examined two relevant signature schemes: one based on a condensed variant of batch RSA and the other ? on aggregated signature scheme by Boneh, et al. In this paper, we introduce the notion of immutability for aggregated signature schemes. Immutability refers to the difficulty of computing new valid aggregated signatures from a set of other aggregated signatures. This is an important feature, particularly for outsourced databases, as lack thereof would enable a frequent querier to eventually amass enough aggregated signatures to answer other (un-posed) queries, thus becoming a de facto service provider. Since the schemes considered in [19] do not offer immutability, we propose several practical methods to achieve it.

Coauthors

Einar Mykletun (1)
Gene Tsudik (2)