Signature Bouquets: Immutability for Aggregated/Condensed Signatures.
Einar Mykletun, Maithili Narasimha, Gene Tsudik · 2004
Abstract. Database outsourcing is a popular industry trend which involves organizations delegating their data management needs to an external service provider. 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 [19] examined two relevant signature schemes: a condensed variant of batch RSA [3] and an aggregated signature scheme based on bilinear maps [6] 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, since lack thereof enables a frequent querier to eventually amass enough aggregated signatures to answer other (un-posed) queries, thus becoming a de facto service provider. Since prior work does not offer immutability, we propose several practical techniques to achieve it. 1