Authenticated hierarchical set operations and applications

摘要

Methods and apparatus are provided for authenticated hierarchical set operations. A third party server processes a query (possibly from a client) on data sets outsourced by a source of the data. The query comprises a hierarchical set operation between at least two of the data sets. Authenticated Set Operation techniques for flat set operations can be iteratively applied for hierarchical set operations. In addition, bilinear accumulators are extended to provide an extractable accumulation scheme comprising a primary bilinear accumulator and a secondary bilinear accumulator. The client receives (i) an encoding of an answer to the query, (ii) a verification comprising, for example, one or more of subset witnesses, completeness witnesses, and/or accumulation values, and (iii) at least one argument for at least one intersection operation, union operation and/or set difference operation.

主权项

1. A method performed by a third party server for processing a query on a plurality of data sets, wherein said data sets are stored in a memory and outsourced from a source of said data sets, wherein said query comprises a hierarchical set operation between at least two of said data sets, said method comprising:
obtaining, from said source, said data sets, corresponding encoded versions of said data sets, and a verification of said encoded versions; generating an answer to said query using said data sets, wherein at least one level of a hierarchy of said hierarchical set operation of said query comprises at least a first one of an intersection operation, a union operation and a set difference operation, and wherein at least a second level different from the first level of said hierarchy comprises at least a second distinct one of said intersection operation, said union operation and said set difference operation; parsing said query as a tree, wherein leaf nodes in said tree correspond to at least two of said data sets associated with said query and non-leaf nodes in said tree correspond to at least one of said intersection operation, said union operation and said set difference operation; for each leaf node in said tree corresponding to a given data set, computing a verification for an encoded version of said given data set that is based on said obtained encoded versions of said data sets and said obtained verification of said encoded versions; for each non-leaf node in said tree, computing at least one argument for a corresponding at least one of said intersection operation, said union operation and said set difference operation; and providing an encoded version of said answer and a proof-of-correctness to said client, wherein said proof-of-correctness comprises said computed verification for each leaf node encoding, and said at least one argument for each non-leaf node set operation, wherein said provided encoded version of said answer and said provided proof-of-correctness are used by said client to authenticate said hierarchical set operation.