International Association for Cryptologic Research

International Association
for Cryptologic Research


Einar Mykletun


On Security of Sovereign Joins
Einar Mykletun Gene Tsudik
The goal of a sovereign join operation is to compute a query across independent database relations such that nothing beyond the join results is revealed. Each relation involved in a sovereign join is owned by a distinct entity and the party posing the query is distinct from the relation owners; it is not permitted to access the original relations. One notable recent research result proposed a secure technique for executing sovereign joins. It entails data owners sending their relations to an independent database service provider which executes a sovereign join with the aid of a tamper-resistant secure coprocessor. This achieves the goal of preventing information leakage during query execution. However, as we show in this paper, the proposed technique is actually insecure as it fails to prevent an attacker from learning the query results. We also suggest some measures to remedy the security problems.
Signature Bouquets: Immutability for Aggregated/Condensed Signatures
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.


Maithili Narasimha (1)
Gene Tsudik (2)