Abstract:
A system and method for cryptographically checking the correctness of outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned (and updated) by a trusted source is disclosed. The system and method provides new authentication mechanisms that allow any entity to publicly verify a proof attesting the correctness of primitive set operations such as intersection, union, subset and set difference. Based on a novel extension of the security properties of bilinear-map accumulators as well as on a primitive called accumulation tree, the system and method achieves optimal verification and proof complexity, as well as optimal update complexity, while incurring no extra asymptotic space overhead. The method provides an efficient proof construction, adding a logarithmic overhead to the computation of the answer of a set-operation query. Applications of interest include efficient verification of keyword search and database queries.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority to earlier file U.S. Provisional Application Ser. No. 61/368,913, file Jul. 29, 2010, the contents of which are incorporated herein by reference. 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    This invention was made with government support under grants CNS-1012060 and CNS-1012798 awarded by the U.S. National Science Foundation. The government has certain rights in the invention. 
     
    
     BACKGROUND OF THE INVENTION 
       [0003]    1. Field of the Invention 
         [0004]    The present patent document relates generally to verificatio of data returned in a search query and more particularly to a method of system for verifying the results of a search query performed on a finite set of data stored on an untrusted server. 
         [0005]    2. Background of the Related Art 
         [0006]    Providing integrity guarantees in third-party data management settings is an active area of research, especially in view of the growth in usage of cloud computing. In such settings, verifying the correctness of outsourced computations performed over remotely stored data becomes a crucial property for the trustworthiness of cloud services. Such a verificatio process should incur minimal overheads to the clients or otherwise the benefit of computation outsourcing are dismissed; ideally, computations should be verifie without having to locally rerun them or to utilize too much extra cloud storage. 
         [0007]    In this paper, we study the verificatio of outsourced operations on general sets and consider the following problem. Assuming that a dynamic collection of m sets S 1 , S 2 , . . . , S m  is remotely stored at an untrusted server, we wish to publicly verify basic operations on these sets, such as intersection, union and set difference. For example, for an intersection query of t sets specifie by indices 1≦i 1 , i 2 , . . . , i t ≦m, we aim at designing techniques that allow any client to cryptographically check the correctness of the returned answer I=S i     1   ∩S i     2   ∩ . . . ∩S i     t   . Moreover, we wish the verificatio of any set operation to be operation-sensitive, meaning that the resulting complexity depends only on the (description and outcome of the) operation, and not on the sizes of the involved sets. That is, if δ=|I| is the answer size then we would like the verificatio cost to be proportional to t+δ, and independent of m or Σ i |S i |; note that work at least proportional to t+δ is needed to verify any such query&#39;s answer. Applications of interest include keyword search and database queries, which boil down to set operations. 
         [0008]    Relation to verifiable computing. Recent works on verifiable computing [1, 12, 16] achieve operation-sensitive verificatio of general functionalities, thus covering set operations as a special case. Although such approaches clearly meet our goal with respect to optimal verifiabilit, they are inherently inadequate to meet our other goals with respect to public verifiability and dynamic updates, both important properties in the context of outsourced data querying. Indeed, to outsource the computation as an encrypted circuit, the works in [1, 12, 16] make use of some secret information which is also used by the verificatio algorithm, thus effectively supporting only one verifier instead, we seek for schemes that allow any client (knowing only a public key) to query the set collection and verify the returned results. Also, the description of the circuit in these works is fi ed at the initialization of the scheme, thus effectively supporting no updates in the outsourced data; instead, we seek for schemes that are dynamic. In other scenarios, but still in the secret-key setting, protocols for general functionalities and polynomial evaluation have recently been proposed in [11] and [6] respectively. 
         [0009]    Aiming at both publicly verifiabl and dynamic solutions, we study set-operation verificatio in the model of authenticated data structures (ADSs). A typical setting in this model, usually referred to as the three-party model [36], involves protocols executed by three participating entities. A trusted party, called source, owns a data structure (here, a collection of sets) that is replicated along with some cryptographic information to one or more untrusted parties, called servers. Accordingly, clients issue data-structure queries to the servers and are able to verify the correctness of the returned answers, based only on knowledge of public information which includes a public key and a digest produced by the source (e.g., the root hash of a Merkle tree, see FIG.  10 ). 1  Updates on the data structure are performed by the source and appropriately propagated by the servers. Variations of this model include: (i) a two-party variant (e.g., [30]), where the source keeps only a small state (i.e., only a digest) and performs both the updates/queries and the verifications this model is directly comparable to the model of verifiabl computing; (ii) the memory checking model [7], where read/write operations on an array of memory cells is verified—h wever, the absence of the notion of proof computation in memory checking (the server is just a storage device) as well as the feature of public verifiabilit in authenticated data structures make the two models fundamentally different 2 .  1  Conveying the trust clients have in the source, the authentic digest is assumed to be publicly available; in practice, a time-stamped and digitally signed digest is outsourced to the server. 2  Indeed, memory checking might require secret memory, e.g., as in the PRF construction in [7]. 
         [0010]    Achieving operation-sensitive verification. In this work, we design authenticated data structures for the verificatio of set operations in an operation-sensitive manner, where the proof and verificatio complexity depends only on the description and outcome of the operation and not on the size of the involved sets. Conceptually, this property is similar to the property of super-efficient verification that has been studied in certifying algorithms [21] and certificatio data structures [19, 37], which is achieved as well as in the context of verifiabl computing [1, 12, 16], where an answer can be verifie with complexity asymptotically less than the complexity required to produce it. Whether the above optimality property is achievable for set operations (while keeping storage linear) was posed as an open problem in [23]. We close this problem in the affirmat ve. 
         [0011]    All existing schemes for set-operation verificatio fall into the following two rather straightforward and highly inefficien solutions. Either short proofs for the answer of every possible set-operation query are precomputed allowing for optimal verificatio at the client at the cost of exponential storage and update overheads at the source and the server—an undesirable trade-off, as it is against storage outsourcing. Or integrity proofs for all the elements of the sets involved in the query are given to the client who locally verifie the query result: in this case the verificatio complexity can be linear in the problem size—an undesirable feature, as it is against computation outsourcing. 
       SUMMARY OF THE INVENTION 
       [0012]    We achieve optimal verificatio by departing from the above approaches as follows. We firs reduce the problem of verifying set operations to the problem of verifying the validity of some more primitive relations on sets, namely subset containment and set disjointness. Then for each such primitive relation we employ a corresponding cryptographic primitive to optimally verify its validity. In particular, we extend the bilinear-map accumulator to optimally verify subset containment (Lemmas 1 and 4), inspired by [32]. We then employ the extended Euclidean algorithm over polynomials (Lemma5) in combination with subset containment proofs to provide a novel optimal verificatio test for set disjointness. The intuition behind our technique is that disjoint sets can be represented by polynomials mutually indivisible, therefore there exist other polynomials so that the sum of their pairwise products equals to one—this is the test to be used in the proof. Still, transmitting (and processing) these polynomials is bandwidth (and time) prohibitive and does not lead to operation-sensitive verification Bilinearity properties, however, allow us to compress their coefficient in the exponent and, yet, use them meaningfully, i.e., compute an internal product. This is why although a conceptually simpler RSA accumulator [5] would yield a mathematically sound solution, a bilinear-map accumulator [28] is essential for achieving the desired complexity goal. 
         [0013]    We formally describe our protocols using an authenticated data structure scheme or ADS scheme (Definition 1). An ADS scheme consists of algorithms {genkey, setup, update, refresh, query, verify} such that: (i) genkey produces the secret and public key of the system; (ii) on input a plain data structure D, setup initializes the authenticated data structure auth(D); (iii) having access to the secret key, update computes the updated digest of auth(D); (iv) without having access to the secret key, refresh updates auth(D); (ν) query computes cryptographic proofs ø(q) for answers α(q) to data structure queries q; (vi) verify processes a proof Π and an answer α and either accepts or rejects. Note that neither query nor verify have access to the secret key, thus modeling computation outsourcing and public verifiabilit. An ADS scheme must satisfy certain correctness and security properties (Definition 2 and 3). We note that protocols in both the three-party and the two-party models can be realized via an ADS scheme. 
         [0014]    Our main result, Theorem 1, presents the firs ADS scheme to achieve optimal verification of the set operations intersection, union, subset and set difference, as well as optimal updates on the underlying collection of sets. Our scheme is proved secure under the bilinear extension of the q-strong Diffie-Hellma assumption (see, e.g., [8]). 
         [0015]    Complexity model. To explicitly measure complexity of various algorithms with respect to number of primitive cryptographic operations, without considering the dependency on the security parameter, we adopt the complexity model used in memory checking [7, 14], which has been only implicitly used in ADS literature. The access complexity of an algorithm is define as the number of memory accesses performed during its execution on the authenticated data structure that is stored in an indexed memory of n cells 3  E.g., a Merkle tree [24] has O(log n) update access complexity since the update algorithm needs to read and write O(log n) memory cells of the authenticated data structure, each cell storing exactly one hash value. The group complexity of a data collection (e.g., proof or ADS group complexity) is define as the number of elementary data objects (e.g., hash values or elements in          ) contained in this collection. Note that although the access and group complexities are respectively related to the time and space complexities, the former are in principle smaller than the latter. This is because time and space complexities are counting number of bits and are always functions of the security parameter which, in turn, is always Ω(log n). Therefore time and space complexities are always Ω(log n), whereas access and group complexities can be O(1). Finally, whenever it is clear from the context, we omit the terms “access” and “group”.  3  We use the term “access complexity” instead of the “query complexity” used in memory checking [7, 14] to avoid ambiguity when referring to algorithm query of the ADS scheme. We also require that each memory cell can store up to O(poly(log n)) bits, a word size used in [7, 14]. 
         [0016]    Related work. The great majority of authenticated data structures involve the use of cryptographic hashing [2, 7, 18, 20, 39, 23, 27] or other primitives [17, 31, 32] to hierarchically compute over the outsourced data one or more digests. Most of these schemes incur verificatio costs that are proportional to the time spent to produce the query answer, thus they are not operation sensitive. Some bandwidth-optimal and 
         [0000]                                                                        TABLE 1                   Asymptotic access and group complexities of various ADS schemes for       intersection queries on t = O(1) sets in a collection of m sets with       answer size δ.                    update,                       setup   refresh   query   verify, |π|   assumption                        [23, 38]   m + M   log n +   n + log m   n + log m   Generic CR               log m       [26]   m + M   m + M   n   n   Strong RSA       [29]   m t  + M       m t     1   δ   Discrete Log       this work   m + M   1   n log 3  n +   δ   Bilinear                   m ε  log m       q-Strong DH               Here, M is the sum of sizes of all the sets and 0 &lt; ε &lt; 1 is a constant.       Also, all sizes of the intersected or updated sets are ⊖(n), |π| denotes the size of the proof, and       CR stands from “collision resistance”.            
operation-sensitive solutions for verificatio of various (e.g., range search) queries appear in [ 2 ,  19 ].
 
         [0017]    Despite the fact that privacy-related problems for set operations have been extensively studied in the cryptographic literature (e.g., [9, 15]), existing work on the integrity dimension of set operations appears mostly in the database literature. In [23], the importance of coming up with an operation-sensitive scheme is identified In [26], possibly the closest in context work to ours, set intersection, union and difference are authenticated with linear costs. Similar bounds appear in [38]. In [29], a different approach is taken: In order to achieve operation-sensitivity, expensive pre-processing and exponential space are required (answers to all possible queries are signed). Finally, related to our work are non-membership proofs, both for the RSA [22] and the bilinear-map [3, 13] accumulators. A comparison of our work with existing schemes appears in Table 1. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0018]    These and other features, aspects, and advantages of the present invention will become better understood with reference to the following description, appended claims, and accompanying drawings where: 
           [0019]      FIG. 1  shows a f ow chart of a two-party implementation of the method and system of the present invention where the client is also the trusted source; 
           [0020]      FIG. 2  shows a f ow chart of a three-party implementation of the method and system of the present invention where the trusted source is distinct from the client; 
           [0021]      FIG. 3  shows a f ow chart of a multi-party implementation of the method and system of the present invention where there are multiple trusted sources and multiple clients; 
           [0022]      FIG. 4  shows a f ow chart of an implementation where timestamps may be transformed into an intersection of keyword queries; 
           [0023]      FIG. 5  shows a step where the trusted source owns sets collections; 
           [0024]      FIG. 6  shows a step where the trusted source authenticates the sets collections and create a digest and signature; 
           [0025]      FIG. 7  shows a step where the trusted source performs setup and updates the authenticated sets collection, digest and signature on an untrusted server; 
           [0026]      FIG. 8  shows a step where a client, Bob, queries the untrusted server and receives an answer and a proof; 
           [0027]      FIG. 9  shows a step where a client, Alice, queries the untrusted server and receives an answer and a proof 
           [0028]      FIG. 10  shows a two level tree structure created to contain the digest and proof; 
           [0029]      FIG. 11  shows a step in building a digest of the collection of sets by calculating an accumulation value for every set; 
           [0030]      FIG. 12  shows a step in building a digest of the collection of sets by building an accumulation tree containing the accumulation value of every set in the collection of sets that was previously calculated; 
           [0031]      FIG. 13  shows a firs step in the proof of findin the answer in the digest; 
           [0032]      FIG. 14  shows a second step in the proof of findin the answer in the digest; 
           [0033]      FIG. 15  shows a third step in the proof of findin the answer in the digest; 
           [0034]      FIG. 16  shows a fourth step in the proof of findin the answer in the digest; and 
           [0035]      FIG. 17  shows a fift step in the proof of findin the answer in the digest. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Preliminaries 
       [0036]    We denote with k the security parameter and with neg(k) a negligible function 4 .  4  Function ƒ:          →          is neg(k) if and only if for any nonzero polynomial p(k) there exits N such that for all k&gt;N it is ƒ(k)&lt;1/p(k). 
         [0037]    The bilinear-map accumulator. Let           be a cyclic multiplicative group of prime order p, generated by element gε         . Let also           be a cyclic multiplicative group of the same order p, such that there exists a pairing e:          ×         →          with the following properties: (i) Bilinearity: e(P α , Q b )=e(P, Q) ab  for all P, Qε          and a, b ε         ; (ii) Non-degeneracy: e(g, g)≠1; (iii) Computability: For all P, Q ε         , e(P, Q) is efficientl computable. We call (p,          ,          , e, g) a tuple of bilinear pairing parameters, produced as the output of a probabilistic polynomial-time algorithm that runs on input I k . 
         [0038]    In this setting, the bilinear-map accumulator [28] is an efficien way to provide short proofs of membership for elements that belong to a set. Let sε          be a randomly chosen value that constitutes the trapdoor in the scheme. The accumulator primitive accumulates elements in          −{s}, outputting a value that is an element in          . For a set of elements χ in          −{s} the accumulation value acc(χ) of χ is define as 
         [0000]      acc(χ)= g   Π     χεχ     (χ+s) . 5  
 
         [0000]      5  Πχεs i (χ+s) is called characteristic polynomial of set S i  in the literature (e.g., see [25]).
 
Value acc(χ) can be constructed using χ and g, g s , g s     2   , . . . , g s     q    (through polynomial interpolation), where q≧|χ|. Subject to acc(χ) each element in χ has a succinct membership proof. More generally, the proof of subset containment of a set S ⊂ χ—for |S|=1, this becomes a membership proof—is the witness (S, W s,χ ) where
 
         [0000]        W   s,χ   =g   Πχεχ−s     (χ+s).     (1)
 
         [0000]    Subset containment of S in χ can be checked through relation e(W s,χ,    g   Π     χεs       (χ+s)   )          e (acc(χ), g) by any verifie with access only to public information. The security property of the bilinear-map accumulator, namely that computing fake but verifiabl subset containment proofs is hard, can be proved using the bilinear q-strong Diffie-Hellma assumption, which is slightly stronger than the q-strong Diffie-Hellma assumption [8] 6    6  However, the plain q-strong Diffie-Hellma assumption [28] suffice to prove just the collision resistance of the bilinear-map accumulator. 
         [0039]    Assumption 1 (Bilinear q-strong Diffie-Hellman assumption) Let k be the security parameter and (p,          ,          , g) be a tuple of bilinear pairing parameters. Given the elements g, g s , . . . , g s     q    ε          for some s chosen at random from          , where q=poly(k) no probabilistic polynomial-time algorithm can output a pair (a, e(g, g) 1/(a+s) ) ε         ×         , except with negligible probability neg(k). 
         [0040]    We next prove the security of subset witnesses by generalizing the proof in [28]. Subset witnesses also appeared (independent of our work but without a proof) in [10]. 
         [0041]    Lemma 1 (Subset containment) Let k be the security parameter and (p,          ,          , g) be a tuple of bilinear pairing parameters. Given the elements g, g s , . . . , g s     q    ε          for some s chosen at random from           and a set of elements χ in          −{s} with q≧|χ|, suppose there is a probabilistic polynomial-time algorithm that finds S and W such that S ⊂ χ and e(W, g Πχεs     (χ+s)   )=e(acc(χ), g). Then there is a probabilistic polynomial-time algorithm that breaks the bilinear q-strong Diffie-Hellman assumption. 
         [0042]    Proof: Suppose there is a probabilistic polynomial-time algorithm that computes such a set S={y 1 , y 2 , . . . , y l } and a fake witness W. Let χ={χ 1 , χ 2 , . . . , χ n } and y j   ⊂ χ for some 1≦j≦l. This means that 
         [0000]        e ( W,g ) Π     ν     εs     (y+s)     =e ( g,g ) (1+s)(χ     2     +s) . . . (χ     n     +s) . 
         [0000]    Note that (y j +s) does not divide (χ 1 +s)(χ 2 +s) . . . (χ n +s). Therefore there exist polynomial Q(s) (computable in polynomial time) of degree n−1 and constant λ≠0, such that (χ 1 +s)(χ 2 +s) . . . (χ n +s)=Q(s)(y j +s)+λ. Thus we have 
         [0000]    
       
         
           
             
               
                 e 
                  
                 
                   ( 
                   
                     W 
                     , 
                     g 
                   
                   ) 
                 
               
               
                 
                   ( 
                   
                     
                       y 
                       j 
                     
                     + 
                     s 
                   
                   ) 
                 
                  
                 
                   
                     Π 
                     
                       1 
                       ≤ 
                       i 
                       ≠ 
                       j 
                       ≤ 
                       l 
                     
                   
                    
                   
                     ( 
                     
                       
                         y 
                         i 
                       
                       + 
                       s 
                     
                     ) 
                   
                 
               
             
             = 
             
               
                 
                   
                     e 
                      
                     
                       ( 
                       
                         g 
                         , 
                         g 
                       
                       ) 
                     
                   
                   
                     
                       
                         Q 
                          
                         
                           ( 
                           s 
                           ) 
                         
                       
                        
                       
                         ( 
                         
                           
                             y 
                             j 
                           
                           + 
                           s 
                         
                         ) 
                       
                     
                     + 
                     λ 
                   
                 
                 ⇒ 
                 
                   
 
                 
                  
                 
                   
                     e 
                      
                     
                       ( 
                       
                         g 
                         , 
                         g 
                       
                       ) 
                     
                   
                   
                     1 
                     
                       
                         y 
                         j 
                       
                       + 
                       s 
                     
                   
                 
               
               = 
               
                 
                   
                     [ 
                     
                       
                         
                           e 
                            
                           
                             ( 
                             
                               W 
                               , 
                               g 
                             
                             ) 
                           
                         
                         
                           
                             Π 
                             
                               1 
                               ≤ 
                               i 
                               ≠ 
                               j 
                               ≤ 
                               l 
                             
                           
                            
                           
                             ( 
                             
                               
                                 y 
                                 i 
                               
                               + 
                               s 
                             
                             ) 
                           
                         
                       
                        
                       
                         
                           e 
                            
                           
                             ( 
                             
                               g 
                               , 
                               g 
                             
                             ) 
                           
                         
                         
                           - 
                           
                             Q 
                              
                             
                               ( 
                               s 
                               ) 
                             
                           
                         
                       
                     
                     ] 
                   
                   
                     λ 
                     
                       - 
                       1 
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    Thus, this algorithm can break the bilinear q-strong Diffie-Hellma assumption. □ 
         [0043]    Tools for polynomial arithmetic. Our solutions use (modulo p) polynomial arithmetic. We next present two results that are extensively used in our techniques, contributing to achieve the desired complexity goals. The firs result on polynomial interpolation is derived using an FFT algorithm (see Preparata and Sarwate [34]) that computes the DFT in a finit fiel (e.g.,          ) for arbitrary n and performing O(n log n) fiel operations. We note that an n-th root of unity is not required to exist in           for this algorithm to work. 
         [0044]    Lemma 2 (Polynomial interpolation with FFT [34]) Let Π i=1   n (χ i +s)=Σ i=0   n b i s i  be a degree-n polynomial. The coefficients b n =0, b n-1 , . . . b 0  of the polynomial can be computed with O(n log n) complexity, given χ 1 , χ 2  . . . χ n . 
         [0045]    Lemma 2 refers to an efficien process for computing the coefficient of a polynomial, given its roots χ 1 , χ 2 , . . . , χ n . In our construction, we make use of this process a numbers of times, in particular, when, given some values χ 1 , χ 2 , . . . , χ n  to be accumulated, an untrusted party needs to compute g (χ     1     +s)(χ     2     +s) . . . (χ     n     +s)  without having access to s. However, access to g, g s , . . . , g s     n    (part of the public key) is allowed, and therefore computing the accumulation value boils down to a polynomial interpolation. 
         [0046]    We next present a second result that will be used in our verificatio algorithms. Related to certifying algorithms [21], this result states that if the vector of coefficient b=[b n , b n-1 , . . . , b 0 ] is claimed to be correct, then, given the vector of roots x=[χ 1 , χ 2 , . . . , χ n ], with high probability, vector b can be certifie to be correct with complexity asymptotically less than O(n log n), i.e., without an FFT computation from scratch. This is achieved with the following algorithm: Algorithm {accept, reject}←certify(b, x, pk): The algorithm picks a random κε         . If Σ i=0   n b i κ i =Σ i=1   n (χ i +κ), then the algorithm accepts, else it rejects. 
         [0047]    Lemma 3 (Polynomial coefficients verification) Let b=[b n , b n-1 , . . . , b 0 ] and x=[χ 1 , χ 2 , . . . , χ n ]. Algorithm certify(b, x, pk) has O(n) complexity. Also, if accept←certify(b, x, pk), then b n , b n-1 , . . . , b 0  are the coefficients of the polynomial Π i=1   n (χ i +s) with probability Ω(1−neg(k)). 
         [0048]    Authenticated data structure scheme. We now defin our authenticated data structure scheme (ADS scheme), as well as the correctness and security properties it must satisfy. 
         [0049]    Definition 1 (ADS scheme) Let D be any data structure that supports queries q and updates u. Let auth(D) denote the resulting authenticated data structure and d the digest of the authenticated data structure, i.e., a constant-size description of D. An ADS scheme A is a collection of the following six probabilistic polynomial-time algorithms:
       1. {sk, pk}←genkey(1 k ): On input the security parameter k, it outputs a secret key sk and a public key pk;   2. {auth(D 0 ), d 0 }←setup(D 0 , sk, pk): On input a (plain) data structure D 0  and the secret and public keys, it computes the authenticated data structure auth(D 0 ) and the respective digest do of it;   3. {D h+1 , auth(D h+1 ), d h+1 , upd}←update(u, D h , auth(D h ), d h , sk, pk): On input an update u on data structure D h , the authenticated data structure auth(D h ), the digest d h , and the secret and public keys, it outputs the updated data structure D h+1  along with the updated authenticated data structure auth(D +1 ), the updated digest d h+1  and some relative information upd;   4. {D +1 , auth(D +1 ), d h+1 }←refresh(u, D h , auth(D h ), d h , upd, pk): On input an update u on data structure D h , the authenticated data structure auth(D h ), the digest d h , relative information upd (output by update), and the public key, it outputs the updated data structure D h+1  along with the updated authenticated data structure auth(D h+1 ) and the updated digest d h+1 ;   5. {Π(q), α(q)}←query(q, D h , auth(D h ), pk): On input a query q on data structure D h , the authenticated data structure auth(D h ) and the public key, it returns the answer α(q) to the query, along with a proof Π(q);   6. {accept, reject}←verify(q, α, H, d h , pk): On input a query q, an answer α, a proof H, a digest d h  and the public key, it outputs either accept or reject.       
 
         [0056]    Let {accept, reject}←check(q, α, D h ) be an algorithm that decides whether α is a correct answer for query q on data structure D h  (check is not part of the definitio of an ADS scheme). There are two properties that an ADS scheme should satisfy, namely correctness and security (intuition follows from signature schemes definitions) 
         [0057]    Definition 2 (Correctness) Let           be an ADS scheme {genkey, setup, update, refresh, query, verify}. We say that the ADS scheme           is correct if for all kε          for all {sk, pk}output by algorithm genkey, for all D h , auth(D h ), d h  output by one invocation of setup followed by polynomially-many invocations of refresh, where h≧0, for all queries q and for all ø(q), α(q) output by query(q, D h , auth(D h ), pk), with all but negligible probability, whenever algorithm check(q, α(q), D h ) outputs accept, so does algorithm verify(q, ø(q), α(q), d h , pk). 
         [0058]    Definition 3 (Security) Let           be an ADS scheme {genkey, setup, update, refresh, query, verify}, k be the security parameter ν(k) be a negligible function and {sk, pk}←genkey(1 k ). Let also Adv be a probabilistic polynomial-time adversary that is only given pk. The adversary has unlimited access to all algorithms of           except for algorithms setup and update to which he has only oracle access. The adversary picks an initial state of the data structure D 0  and computes D 0 , auth(D 0 ), d 0  through oracle access to algorithm setup. Then, for i=0, . . . , h=poly(k), Adv issues an update μ i  in the data structure D i  and computes D i+1 , auth(D i+i ) and d i+1  through oracle access to algorithm update. Finally the adversary picks an index 0≦t≦h+1, and computes a query q, an answer α and a proof ø. We say that the ADS scheme           is secure if for all kε          for all {sk, pk}output by algorithm genkey, and for any probabilistic polynomial-time adversary Adv it holds that 
         [0000]    
       
         
           
             
               
                 
                   
                     Pe 
                      
                     
                       [ 
                       
                         
                           
                             
                               
                                 
                                   { 
                                   
                                     q 
                                     , 
                                     Π 
                                     , 
                                     α 
                                     , 
                                     t 
                                   
                                   } 
                                 
                                 ← 
                                 
                                   Adv 
                                    
                                   
                                     ( 
                                     
                                       
                                         1 
                                         k 
                                       
                                       , 
                                       pk 
                                     
                                     ) 
                                   
                                 
                               
                               ; 
                             
                           
                           
                             
                               
                                 accept 
                                 ← 
                                 
                                   verify 
                                    
                                   
                                     ( 
                                     
                                       q 
                                       , 
                                       α 
                                       , 
                                       Π 
                                       , 
                                       
                                         d 
                                         t 
                                       
                                       , 
                                       pk 
                                     
                                     ) 
                                   
                                 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                               reject 
                               ← 
                               
                                 
                                   check 
                                    
                                   
                                     ( 
                                     
                                       q 
                                       , 
                                       α 
                                       , 
                                       
                                         D 
                                         t 
                                       
                                     
                                     ) 
                                   
                                 
                                 . 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                   ≤ 
                   
                     
                       v 
                        
                       
                         ( 
                         k 
                         ) 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
       Construction and Algorithms 
       [0059]    In this section we present an ADS scheme for set-operation verification The underlying data structure for which we design our ADS scheme is called sets collection, and can be viewed as a generalization of the inverted index [4] data structure. 
         [0060]    Sets collection. Referring now to  FIGS. 5 ,  6 ,  11  and  12 , the sets collection data structure consists of m sets, denoted with S 1 , S 2 , . . . , S m , each containing elements from a universe μ. Without loss of generality we assume that the universe           is the set of nonnegative integers in the interval [m+1, p−1]−{s} 7  where p is k-bit prime, m is the number of the sets in our collection that has bit size O(log k), k is the security parameter and s is the trapdoor of the scheme (see algorithm genkey). A set S i  does not contain duplicate elements, however an element χε          can appear in more than one set. Each set is sorted and the total space needed is O(m+M), where M is the sum of the sizes of the sets.  7  This choice simplifie the exposition; however, by using some collision-resistant hash function, universe           can be set to          −{s}. 
         [0061]    In order to get some intuition, we can view the sets collection as an inverted index. In this view, the elements are pointers to documents and each set S i  corresponds to a term w i  in the dictionary, containing the pointers to documents where term w i  appears. In this case, m is the number of terms being indexed, which is typically in the hundreds of thousands, while M, bounded from below by the number of documents being indexed, is typically in the billions. Thus, the more general terms “elements” and “sets” in a sets collection can be instantiated to the more specifi “documents” and “terms”. 
         [0062]    The operations supported by the sets collection data structure consist of updates and queries. An update is either an insertion of an element into a set or a deletion of an element from a set. An update on a set of size n takes O(log n) time. For simplicity, we assume that the number m of sets does not change after updates. A query is one of the following standard set operations: (i) Intersection. Given indices i 1 , i 2 , . . . , i t , return set I=S i     1   ∩S i     2   ∩ . . . S i     t   ; (ii) Union: Given indices i l , i 2 , . . . , i t , return set U=S i     1   ∪S i     2   ∪ . . . ∪S it ; (iii) Subset query: Given indices i and j, return true if S i   ⊂ S j  and false otherwise; (iv) Set difference: Given indices i and j, return set D=S i −S j . For the rest of the paper, we denote with δ the size of the answer to a query operation, i.e., δ is equal to the size of I, U, or D. For a subset query, δ is O(1). 
         [0063]    We next detail the design of an ADS scheme           for the sets collection data structure. This scheme provides protocols for verifying the integrity of the answers to set operations in a dynamic setting where sets evolve over time through updates. The goal is to achieve optimality in the communication and verificatio complexity: a query with t parameters and answer size δ should be verifie with O(t+δ) complexity, and at the same time query and update algorithms should be efficien as well. 
       Setup and Updates 
       [0064]    Referring to  FIGS. 7-9 ,  14  and  15 , we describe an ADS scheme          ={genkey, setup, update, refresh, query, verify} for the sets collection data structure and we prove that its algorithms satisfy the complexities of Table 1. We begin with the algorithms that are related to the setup and the updates of the authenticated data structure. 
         [0065]    Algorithm {sk, pk}←genkey(1 k ): Bilinear pairing parameters (p,          ,          , e, g) are picked and an element ε          is chosen at random. Subsequently, an one-to-one function h(•):         →          is used. This function simply outputs the bit description of the elements of           according to some canonical representation of          . Finally the algorithm outputs sk=s and pk={h(•), p,          ,          , g, g}, where vector g contains values 
         [0000]    
       
      
       g={g 
       s 
       ,g 
       s 
       
         2 
       
       , . . . , g 
       s 
       
         q},  
       
      
     
         [0000]    where q≧max{m, max i= 1, . . . , m{|S i |}}. The algorithm has O(1) access complexity. 
         [0066]    Algorithm {D 0 , auth(D 0 ), d 0 }←setup(D 0 , sk, pk): Let D 0  be our initial data structure, i.e., the one representing sets S 1 , S 2 , . . . , S m . The authenticated data structure auth(D) is built as follows. First, for each set S i  its accumulation value acc(S i )=g Πχεs     i     (χ+s)  is computed (see Section 6.1). Subsequently, the algorithm picks a constant 0≦ε≦1. Let T be a tree that has l=[1/e] levels and m leaves, numbered 1, 2, . . . , m, where m is the number of the sets of our sets collection data structure. Since T is a constant-height tree, the degree of any internal node of it is O(m ε ). We call such a tree an accumulation tree, which was originally introduced (combined with different cryptography) in [32]. For each node of the tree ν, the algorithm recursively computes the digest d(ν) of ν as follows. If ν is a leaf corresponding to set S i  where 1≦i≦m, the algorithm sets d(ν)=acc(S i ) (i+   s) ; here, raising value acc(S i ) to exponent i+s, under the constraint that i≦m, is done to also accumulate the index i of set S i  (and thus prove that acc(S i ) refers to S i ). If node ν is not a leaf, then 
         [0000]        d (ν)= g   øwεN(ν)     (h(d(w)+(s)),     (3)
 
         [0000]    where          (ν) denotes the set of children of node ν. The algorithm outputs all the sets $ as the data structure D 0 , and all the accumulation values acc(S i ) for 1≦i≦m, the tree T and all the digests d(ν) for all νεT as the authenticated data structure auth(D 0 ). Finally, the algorithm sets d 0 =d(r) where r is the root of T, i.e., d 0  is the digest of the authenticated data structure (define similarly as in a Merkle tree). 8  The access complexity of the algorithm is O(m+M) (for postorder traversal of T and computation of acc(S i )), where M=Σ i=1   m |S i |. The group complexity of auth(D 0 ) is also O(m+M) since the algorithm stores one digest per node of T, T has O(m) nodes and there are M elements contained in the sets, as part of auth(D 0 ). 
         [0067]    Algorithm {D h+1 , auth(D h+1 ), d h+1 , upd}←update(u, D h , auth(D h ), d h , sk, pk): We consider the update date “insert element χε          into set S i ” (note that the same algorithm could be used for element deletions). Let ν 0  be the leaf node of T corresponding to set S i . Let ν 0 , ν 1 , . . . , ν l  be the path in T from node ν 0  to the root of the tree, where l=┌1/ε┐. The algorithm initially sets d(ν 0 )=acc(S i ) (χ+s) , i.e., it updates the accumulation value that corresponds to the updated set (note that in the case where χ is deleted from S i  the algorithm sets d′(ν 0 )=acc(S i ) (χ+s)-1 ). Then the algorithm sets  8  Digest d(r) is a “secure” succinct description of the set collection data structure. Namely, the accumulation tree protects the integrity of values acc(S i ), 1≦i≦m, and each accumulation value acc(S i ) protects the integrity of the elements contained in set S i . 
         [0000]        d ′(ν j )= d (ν j ) (h(d′(ν     j-1     ))+s)(h(d(ν     j-1))+s)       -1    for  j= 1 , . . . , l,   (4)
 
         [0000]    where d(ν j-1 ) is the current digest of ν j-1  and d′(ν j-1 ) is the updated digest of ν j-1 . 9  All these newly computed values (i.e., the new digests) are stored by the algorithm. The algorithm then outputs the new digests d′(ν j-1 ), j=1, . . . , l, along the path from the updated set to the root of the tree, as part of information upd. Information upd also includes χ and d(ν l ). The algorithm also sets d h+1 =d′(ν l ), i.e., the updated digest is the newly computed digest of the root of T. Finally the new authenticated data structure auth(D h+1 ) is computed as follows: in the current authenticated data structure auth(D h ) that is input of the algorithm, the values d(ν j-1 ) are overwritten with the new values d(ν j-1 ) (j=1, . . . , l), and the resulting structure is included in the output of the algorithm. The number of operations performed is proportional to 1/ε, therefore the complexity of the algorithm is O(1).  9  Note that these update computations are efficien because update has access to secret key s. 
         [0068]    Algorithm {D h+1 , auth(D h+1 ), d h+1 }←refresh(u, D h , auth(D h ), d h , upd, pk): We consider the update “insert element χε          into set S i ”. Let ν 0  be the node of T corresponding to set S i . Let ν 0 , ν 1 , . . . , ν l  be the path in T from node ν 0  to the root of the tree. Using the information upd, the algorithm sets d(ν j )=d′(ν j ) for j=0, . . . , l, i.e., it updates the digests that correspond to the updated path. Finally, it outputs the updated sets collection as D h+1 , the updated digests d(ν j ) (along with the ones that belong to the nodes that are not updated) as auth(D h+1 ) and d′(ν l ) (contained in upd) as d h+1 . 10  The algorithm has O(1) complexity as the number of performed operations is O(1/e).  10  Note that information upd is not required for the execution of refresh, but is rather used for efficien y. Without access to upd, algorithm refresh could compute the updated values d(ν j ) using polynomial interpolation, which would have O(m ε  log m) complexity (see Lemma 2). 
       Authenticity of Accumulation Values 
       [0069]    Referring to  FIG. 15 , so far we have described the authenticated data structure auth(D h ) that our ADS scheme           will use for set-operation verifications Overall, auth(D h ) comprises a set of m accumulation values acc(S i ), one for each set S i , i=1, . . . , m, and a set of O(m) digests d(ν), one for each internal node ν of the accumulation tree T. Our proof construction and verificatio protocols for set operations (described in Section 6.2.3) make use of the accumulation values acc(S i ) (subject to which subset-containment witnesses can be defined) and therefore it is required that the authenticity of each such value can be verified Tree T serves this exact role by providing short correctness proofs for each value acc(S i ) stored at leaf i of T, this time subject to the (global) digest d h  stored at the root of T. We next provide the details related to proving the authenticity of acc(S i ). 
         [0070]    The correctness proof ø i  of accumulation value acc(S i ), 1≦i≦m, is a collection of O(1) bilinear-map accumulator witnesses (as define in Section 6.1). In particular, ø i  is set to be the ordered sequence ø=(π 1 , π 2 , . . . , π l ), where π j  is the pair of the digest of node ν j-1  and a witness that authenticates ν j-1 , subject to node νj, in the path ν 0 , ν 1 , . . . , ν l  define by leaf ν 0  storing accumulation value acc(S i ) and the root ν l  of T. Conveniently, π j  is define as π j =(β j , γ j ), where 
         [0000]      β j   =d(ν   j-1 ) and γ j   =W   ν     j-1     (ν     j     )   =g   øwεN(ν     j     )−{ν     j-1     }     (h(d(w)+(s)).     (5)
 
         [0071]    Note that π j  is the witness for a subset of one element, namely h(d(ν j-1 )) (recall, d(ν 0 )=acc(S i ) (i+s) ). Clearly, pair π j  has group complexity O(1) and can be constructed using polynomial interpolation with O(m ε  log m) complexity, by Lemma 2 and since ν j  has degree O(m ε ). Since ø i  consists of O(1) such pairs, we conclude that the proof ø i  for an accumulation value acc(S i ) can be constructed with O(m ε  log m) complexity and has O(1) group complexity. The following algorithms queryTree and verifyTree are used to formally describe the construction and respectively the verificatio of such correctness proofs. Similar methods have been described in [32]. 
         [0072]    Algorithm {ø i , α i }←queryTree(i, D h , auth(D h ), pk): Let ν 0 , ν 1 , . . . , ν l  be the path of T from the node storing acc(S i ) to the root of T. The algorithm computes ø i  by setting ø i =(π 1 , π 2 , . . . , π l ), where π j =(d(ν j-1 ), W ν     j-1     (ν     j     ) ) and W ν     j-1     (ν     j     )  is given in Equation 5 and computed by Lemma 2. Finally, the algorithm sets α i =acc(S i ). 
         [0073]    Algorithm {accept, reject}←verifyTree(i, α i , ø i , d h , pk): Let the proof be ø i =(π 1 , π 2 , . . . , π l ), where π j =(β j , γ j ). The algorithm outputs reject if one of the following is true: (i) e(β 1 , g)≠e(α i , g i g s ); or (ii) e (β j , g)≠e(γ j-1 , g h(β     j-1     ) g s ) for some 2≦j≦1; or (iii) e(d h , g)≠e(γ l , g h(β     l     ) g s ). Otherwise, it outputs accept. 
         [0074]    We finall provide some complexity and security properties that hold for the correctness proofs of the accumulated values. The following result is used as a building block to derive the complexity of our scheme and prove its security (Theorem 1). 
         [0075]    Lemma 4 Algorithm queryTree runs with O(m ε  log m) access complexity and outputs a proof of O(1) group complexity. Moreover algorithm verifyTree has O(1) access complexity. Finally, for any adversarially chosen proof ø i  (1≦i≦m), if accept←verifyTree(i, α i , ø i , d h , pk), then α i =acc(S i ) with probability Ω(1−neg(k)). 
       Queries and Verification 
       [0076]    Referring to  FIGS. 16 and 17 , with the correctness proofs of accumulation values at hand, we complete the description of our scheme           by presenting the algorithms that are related to the construction and verificatio of proofs attesting the correctness of set operations. These proofs are efficientl constructed using the authenticated data structure presented earlier, and they have optimal size O(t+δ), where t and δ are the sizes of the query parameters and the answer. In the rest of the section, we focus on the detailed description of the algorithms for an intersection and a union query, but due to space limitations, we omit the details of the subset and the set difference query. We note, however, that the treatment of the subset and set difference queries is analogous to that of the intersection and union queries. 
         [0077]    The parameters of an intersection or a union query are t indices i 1 , i 2 , . . . , i t , with 1≦t≦m. To simplify the notation, we assume without loss of generality that these indices are 1, 2, . . . , t. Let n i  denote the size of set S i  (1≦i≦t) and let N=Σ i=1   t n i . Note that the size δ of the intersection or union is always O(N) and that operations can be performed with O(N) complexity, by using a generalized merge. 
         [0078]    Intersection query. Let I=S 1 ∩S 2 ∩ . . . ∩S t ={y 1 , y 2 , . . . , y δ}. We express the correctness of the set intersection operation by means of the following two conditions:    
         [0079]    Subset Condition: 
         [0000]        I ⊂ S   1             I ⊂ S   2              . . .              I ⊂ S   t ;  (6)
 
         [0080]    Completeness Condition: 
         [0000]      ( S   1   −I )∩( S   2   −I )∩ . . . ∩( S   t   −I )=Ø.  (7)
 
         [0081]    The completeness condition in Equation 7 is necessary since set I must contain all the common elements. Given an intersection I, and for every set S j , 1≦i≦t, we defin the degree-n j  polynomial 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                       j 
                     
                      
                     
                       ( 
                       s 
                       ) 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         x 
                         ∈ 
                         
                           
                             S 
                             j 
                           
                           - 
                           1 
                         
                       
                     
                      
                     
                       
                         ( 
                         
                           x 
                           + 
                           s 
                         
                         ) 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0082]    The following result is based on the extended Euclidean algorithm over polynomials and provides our core verificatio test for checking the correctness of set intersection. 
         [0083]    Lemma 5 Set 1 is the intersection of sets S 1 , S 2 , . . . , S t  if and only if there exist polynomials q 1 (s), q 2 (s), . . . , q t (s) such that q 1 (s)P 1 (s)+q 2 (s)P 2 (s)+ . . . +q t (s)P t (s)=1, where P j (s), j=1, . . . , t, are defined in Equation 8. Moreover the polynomials q 1 (s), q 2 (s), . . . , q t (s) can be computed with O(N log 2  N log log N) complexity. 
         [0084]    Using Lemmas 2 and 5 we next construct efficien proofs for both conditions in Equations 6 and 7. In turn, the proofs are directly used to defin the algorithms query and verify of our ADS scheme           for intersection queries.            
         [0085]    Proof of subset condition. For each set S j , 1≦j≦t, the subset witnesses W I,j =g P     j     (s) =g øχεS     j-1       (z+s)    are computed, each with O(n j  log n j ) complexity, by Lemma 2. (Recall, W I,j  serves as a proof that I is a subset of set S j ) Thus, the total complexity for computing all t required subset witnesses is O(N log N), where N=Σ i=1   t n i . 11    11  This is because Σn j  log n j ≦log NΣn j =N log N. 
         [0086]    Proof of completeness condition. For each q j (s), 1≦j≦t, as in Lemma 5 satisfying q 1 (s)P 1 (s)+q 2 (s)P 2 (s)+ . . . +q t (s)P t (s)=1, the completeness witnesses F I,j =g q     j     (s)  are computed, by Lemma 5 with O(N log 2  N log log N) complexity. 
         [0087]    Algorithm {Π(q), α(q)}←query(q, D h , auth(D h ), pk) (Intersection): Query q consists of t indices {1, 2, . . . , t}, asking for the intersection I of S 1 , S 2 , . . . , S t . Let I={y 1 , y 2 , . . . , y δ }. Then α(q)=I, and the proof Π(q) consists of the following parts.
       1. Coefficients b δ , b δ-1 , . . . , b 0  of polynomial (y 1 +s)(y 2 +s) . . . (y δ +s) that is associated with the intersection I={y 1 , y 2 , . . . , y δ }. These are computed with O(δ log δ) complexity (Lemma 2) and they have O(δ) group complexity.   2. Accumulation values acc(S j ), j=1, . . . , t, which are associated with sets S j , along with their respective correctness proofs Π j . These are computed by calling algorithm queryTree(j, D h , auth(D h ), pk), for j=1, . . . , t, with O(tm ε  log m) total complexity and they have O(t) total group complexity (Lemma 4).   3. Subset witnesses W 1,j , j=1, . . . , t, which are associated with sets S j  and intersection I (see proof of subset condition). These are computed with O(N log N) complexity and have O(t) total group complexity (Lemma 2).   4. Completeness witnesses F I,j , j=1, . . . , t, which are associated with polynomials q j (s) of Lemma 5 (see proof of completeness condition). These are computed with O(N log 2  N log log N) complexity and have O(t) group complexity (Lemma 5).       
 
         [0092]    Algorithm {accept, reject}←verify(q, α, Π, d h , pk) (Intersection): Verifying the result of an intersection query includes the following steps.
       1. First, the algorithm uses the coefficient b=[b δ , b δ-1 , . . . , b 0 ] and the answer α(q)={y 1 , y 2 , . . . , y δ } as an input to algorithm certify(b, α(q), pk), in order to certify the validity of b δ , b δ-1 , . . . , b 0 . If certify outputs reject, the algorithm also outputs reject. 12  This step has O(δ) complexity (Lemma 3).  12  Algorithm certify is used to achieve optimal verificatio and avoid an O(δ log δ) FFT computation from scratch.   2. Subsequently, the algorithm uses the proof Π j  to verify the correctness of acc(S j ), by running algorithm verifyTree(j, acc(S j ), Π j , d h , pk) for j=1, . . . , t. If, for some j, verifyTree running on acc(S j ) outputs reject, the algorithm also outputs reject. This step has O(t) complexity (Lemma4).   3. Next, the algorithm checks the subset condition: 13    13  Group element Π i=0   δ g s     i     b     i   =g (y     1     +s)(y     2     +s) . . . (y     δ     +s)  is computed once with O(δ) complexity.       
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       e 
                       ( 
                       
                         
                           
                             ∏ 
                             
                               i 
                               = 
                               0 
                             
                             δ 
                           
                            
                           
                             
                               ( 
                               
                                 g 
                                 
                                   s 
                                   i 
                                 
                               
                               ) 
                             
                             
                               b 
                               i 
                             
                           
                         
                         , 
                         
                           W 
                           
                             1 
                             , 
                             j 
                           
                         
                       
                       ) 
                     
                      
                     
                       = 
                       ? 
                     
                      
                     
                       e 
                        
                       
                         ( 
                         
                           
                             acc 
                              
                             
                               ( 
                               
                                 S 
                                 j 
                               
                               ) 
                             
                           
                           , 
                           g 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
                       for 
                        
                       
                           
                       
                        
                       j 
                     
                     = 
                     1 
                   
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     t 
                     . 
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    If, for some j, the above check on subset witness W I,j  fails, the algorithm outputs reject. This step has O(t+δ) complexity.
       4. Finally, the algorithm checks the completeness condition:       
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       t 
                     
                      
                     
                       e 
                        
                       
                         ( 
                         
                           
                             W 
                             
                               1 
                               , 
                               j 
                             
                           
                           , 
                           
                             F 
                             
                               1 
                               , 
                               j 
                             
                           
                         
                         ) 
                       
                     
                   
                    
                   
                     = 
                     ? 
                   
                    
                   
                     
                       e 
                        
                       
                         ( 
                         
                           g 
                           , 
                           g 
                         
                         ) 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0000]    If the above check on the completeness witnesses F I,j =1≦j≦t, fails, the algorithm outputs reject. Or, if this relation holds, the algorithm outputs accept, i.e., it accepts α(q) as the correct intersection. This step has O(t) complexity. 
         [0097]    Note that for Equation 10, it holds Π j=1   t e(W I,j , F I,j )=e(g, g) Σ     j=1       r     q     j     (s)P     j     (s) =e(g, g) when all the subset witnesses W I,j , all the completeness witnesses F I,j  and all the sets accumulation values acc(S j ) have been computed honestly, since q 1 (s)P 1 (s)+q 2 (s)P 2 (s)+ . . . +q t (s)P t (s)=1. This is a required condition for proving the correctness of our ADS scheme, as define in Definitio 2. We continue with the description of algorithms query and verify for the union query. 
         [0098]    Union query. Let U=S 1 ∪S 2 ∪ . . . ∪S t ={y 1 , y 2 , . . . , y δ }. We express the correctness of the set union operation by means of the following two conditions: 
         [0099]    Membership Condition: 
         [0000]      ∀y i ε∪∃jε{1,2, . . . , t}: y i εS j ;  (11)
 
         [0100]    Superset Condition: 
         [0000]      (∪ ⊃ S 1 )         (∪ ⊃ S 2 ) . . .          (∪ ⊃ S t ).  (12)
 
         [0101]    The superset condition in Equation 12 is necessary since set U must exclude none of the elements in sets S 1 , S 2 , . . . , S t . We formally describe algorithms query and verify of our ADS scheme           for union queries. 
         [0102]    Algorithm {Π(q), α(q)}←query(q, D h , auth(D h ), pk) (Union): Query q asks for the union ∪ of t sets S 1 , S 2 , . . . , S t . Let ∪={y 1 , y 2 , . . . , y δ }. Then α(q)=∪ and the proof Π(q) consists of the following parts. (1) Coefficients b δ , b δ-1 , . . . , b 0  of polynomial (y 1+s)(y   2+s) . . . (y   δ+s) that is associated with the union ∪={y   1 , y 2 , . . . , y δ }. (2) Accumulation values acc(S j ), j=1, . . . , t, which are associated with sets S j , along with their respective correctness proofs Π j , both output of algorithm queryTree(j, D h , auth(D h ), pk). (3) Membership witnesses W y     i     , S     k    of y i , i=1, . . . , δ (see Equation 1), which prove that y i  belongs to some set S k , 1≦k≦t, and which are computed with O(N log N) total complexity and have O(δ) total group complexity (Lemma 2). (4) Subset witnesses W S     j     ,∪ , J=1, . . . , t, which are associated with sets S i  and union ∪ and prove that ∪ is a superset of S j , 1≦k≦t, and which are computed with O(N log N) total is complexity and have O(t) total group complexity (Lemma2). 
         [0103]    Algorithm {accept, reject}←verify(q, α, Π, d h , pk): (Union): Verifying the result of a union query includes the following steps. (1) First, the algorithm uses b=[b δ , b δ-1 , . . . , b 0 ] and the answer ∪=α(q)={y 1 , y 2 , . . . , y δ } as an input to algorithm certify(b, α(q), pk), in order to certify the validity of b δ , b δ-1 , . . . , b 0 . (2) Subsequently, the algorithm uses the proofs ø j  to verify the correctness of acc(S j ), by using algorithm verifyTree(j, acc(S j ), Π j , d h , pk) for j=1, . . . , t. If the verificatio fails for at least one of acc(S j ), the algorithm outputs reject. (3) Next, the algorithm verifie that each element y, i=1, . . . , δ, of the reported union belongs to some set S k , for some 1≦k≦t (O(δ) complexity). This is done by checking that relation e(W y     i   , S k , g y     i    g S )=e(acc(S k ), g) holds for all i=1, . . . , δ; otherwise the algorithm outputs reject. (4) Finally, the algorithm verifie that all sets specifie by the query are subsets of the union, by checking the following conditions: 
         [0000]    
       
         
           
             
               
                 e 
                  
                 
                   ( 
                   
                     
                       W 
                       
                         
                           S 
                           j 
                         
                         , 
                         U 
                       
                     
                     , 
                     
                       acc 
                        
                       
                         ( 
                         
                           S 
                           j 
                         
                         ) 
                       
                     
                   
                   ) 
                 
               
                
               
                 = 
                 ? 
               
                
               
                 e 
                 ( 
                 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         0 
                       
                       δ 
                     
                      
                     
                       
                         ( 
                         
                           g 
                           
                             s 
                             i 
                           
                         
                         ) 
                       
                       
                         b 
                         i 
                       
                     
                   
                   , 
                   g 
                 
                 ) 
               
             
             , 
             
               
                 for 
                  
                 
                     
                 
                  
                 j 
               
               = 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               t 
               . 
             
           
         
       
     
         [0104]    If any of the above checks fails, the algorithm outputs reject, otherwise, it outputs accept, i.e., ∪ is accepted as the correct union. 
         [0105]    Subset and set difference query. For a subset query (positive or negative), we use the property S i   ⊃ S j           ∀ y εS i , yεS j . For a set difference query we use the property 
         [0000]    
       
      
       D=S 
       i 
       −S 
       j 
               
       ∃F:F∪D=S 
       i 
               
       F=S 
       i 
       ∩S 
       j.  
      
     
         [0106]    The above conditions can both be checked in an operation-sensitive manner using the techniques we have presented before. We now give the main result in our work. 
         [0107]    Theorem 1 Consider a collection of m sets S 1 , . . . , S m  and let M=Σ i=1   m |S i | and 0≦ε≦1. For a query operation involving t sets, let N be the sum of the sizes of the involved sets, and δ be the answer size. Then there exists an ADS scheme          ={genkey, setup, update, refresh, query, verify} for a sets collection data structure D with the following properties: (1)           is correct and secure according to Definitions 2 and 3 and based on the bilinear q-strong Diffie-Hellman assumption; (2) The access complexity of algorithm (i) genkey is O(1); (ii) setup is O(m+M); (iii) update is O(1) outputting information upd of O(1) group complexity; (iv) refresh is O(1); (3) For all queries q (intersection/union/subset/difference), constructing the proof with algorithm query has O(N log 2  N log log N+tm ε  log m) access complexity, algorithm verify has O(t+δ) access complexity and the proof Π(q) has O(t+δ) group complexity; (4) The group complexity of the authenticated data structure auth(D) is O(m+M). 
       Security, Protocols and Applications 
       [0108]    In this section we give an overview of the security analysis of our ADS scheme, describe how it can be employed to provide verificatio protocols in the three-party [36]( FIG. 2 ) and two-party [30] authentication models ( FIG. 1 ), and finall discuss some concrete applications. 
         [0109]    Security proof sketch. We provide some key elements of the security of our verificatio protocols focusing on set intersection queries. The security proofs of the other set operations share similar ideas. Let D 0  be a sets collection data structure consisting of m sets S 1 , S 2 , . . . , S m , 14  and consider our ADS scheme          ={genkey, setup, update, refresh, query, verify}. Let k be the security parameter and let {sk, pk}←genkey(1 k ). The adversary is given the public key pk, namely {h(•), p,                    e, g, g s , . . . g s     q   }, and unlimited access to all the algorithms of          , except for setup and update to which he only has oracle access. The adversary initially outputs the authenticated data structure auth(D 0 ) and the digest d 0 , through an oracle call to algorithm setup. Then the adversary picks a polynomial number of updates μ t  (e.g., insertion of an element χ into a set S r ) and outputs the data structure D i , the authenticated data structure auth(D i ) and the digest d i  through oracle access to update. Then he picks a set of indices q={1, 2, . . . , t}(wlog), all between 1 and m and outputs a proof Π(q) and an answer          ≠S 1 ∩S 2 ∩ . . . ∩S t  which is rejected by check as incorrect. Suppose the answer α(q) contains d elements. The proof Π(q) contains (i) Some coefficient b 0 , b 1 , . . . , b d ; (ii) Some accumulation values acc j  with some respective correctness proofs Π j , for j=1, . . . , t; (iii) Some subset witnesses W j  with some completeness witnesses F j , for j=1, . . . , t (this is, what algorithm verify expects for input).  14  Note here that since the sets are picked by the adversary, we have to make sure that no element in any set is equal to s, the trapdoor of the scheme (see definitio of the bilinear-map accumulator domain). However, this event occurs with negligible probability since the sizes of the sets are polynomially-bounded and s is chosen at random from a domain of exponential size. 
         [0110]    Suppose verify accepts. Then: (i) By Lemma 3, b 0 , b 1 , . . . , b d  are indeed the coefficient of the polynomial Π χεχ   (χ+s) , except with negligible probability; (ii) By Lemma 4, values acc j  are indeed the accumulation values of sets S j , except with negligible probability; (iii) By Lemma 1, values W j  are indeed the subset witnesses for set           (with reference to S j ), i.e., W j =g P     j     (s)  percent with negligible probability; (iv) However, P 1 (s), P 2 (s), . . . , P t (s) are not coprime since           is incorrect and therefore           cannot contain all the elements of the intersection. Thus the polynomials P 1 (s), P 2 (s), . . . , P t (s) (Equation 8) have at least one common factor, say (r+s) and it holds that P j (s)=(r+s)Q j (s) for some polynomials Q j (s) (computable in polynomial time), for all j=1, . . . , t. By the verificatio of Equation 10 (completeness condition), we have 
         [0000]    
       
         
           
             
               
                 
                   
                     e 
                      
                     
                       ( 
                       
                         g 
                         , 
                         g 
                       
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       t 
                     
                      
                     
                       e 
                        
                       
                         ( 
                         
                           
                             W 
                             j 
                           
                           , 
                           
                             F 
                             j 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       t 
                     
                      
                     
                       e 
                        
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 P 
                                 j 
                               
                                
                               
                                 ( 
                                 s 
                                 ) 
                               
                             
                           
                           , 
                           
                             F 
                             j 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       t 
                     
                      
                     
                       e 
                        
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 ( 
                                 
                                   r 
                                   + 
                                   s 
                                 
                                 ) 
                               
                                
                               
                                 
                                   Q 
                                   j 
                                 
                                  
                                 
                                   ( 
                                   s 
                                   ) 
                                 
                               
                             
                           
                           , 
                           
                             F 
                             j 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       t 
                     
                      
                     
                       
                         e 
                          
                         
                           ( 
                           
                             
                               g 
                               
                                 
                                   Q 
                                   j 
                                 
                                  
                                 
                                   ( 
                                   s 
                                   ) 
                                 
                               
                             
                             , 
                             
                               F 
                               j 
                             
                           
                           ) 
                         
                       
                       
                         ( 
                         
                           r 
                           + 
                           s 
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ( 
                       
                         
                           ∏ 
                           
                             j 
                             = 
                             1 
                           
                           t 
                         
                          
                         
                           e 
                            
                           
                             ( 
                             
                               
                                 g 
                                 
                                   
                                     Q 
                                     j 
                                   
                                    
                                   
                                     ( 
                                     s 
                                     ) 
                                   
                                 
                               
                               , 
                               
                                 F 
                                 j 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0111]    Therefore we can derive an (r+s)-th root of e(g, g) as 
         [0000]    
       
         
           
             
               
                 e 
                  
                 
                   ( 
                   
                     g 
                     , 
                     g 
                   
                   ) 
                 
               
               
                 1 
                 
                   r 
                   + 
                   s 
                 
               
             
             = 
             
               
                 ∏ 
                 
                   j 
                   = 
                   1 
                 
                 t 
               
                
               
                 
                   e 
                    
                   
                     ( 
                     
                       
                         g 
                         
                           
                             Q 
                             j 
                           
                            
                           
                             ( 
                             s 
                             ) 
                           
                         
                       
                       , 
                       
                         F 
                         j 
                       
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
         [0112]    This means that if the intersection           is incorrect and all the verificatio tests are satisfied we can derive a polynomial-time algorithm that outputs a bilinear q-strong Diffie-Hellma challenge (r, e(g, g) 1/(r+s) ) for an element r that is a common factor of the polynomials P 1 (s), P 2 (s), . . . , P t (s), which by Assumption 1 happens with probability neg(k). This concludes an outline of the proof strategy for the case of intersection. 
         [0113]    Protocols. As mentioned in the introduction, our ADS scheme           can be used by a verificatio protocol in the three-party model [36](See  FIG. 2 ). Here, referring to  FIG. 5 , a trusted entity, called source, owns a sets collection data structure D h , but desires to outsource query answering, in a trustworthy (verifiable way. As shown in  FIG. 6 , the source runs genkey and setup and outputs the authenticated data structure auth(D h ) along with the digest d h . The source subsequently signs the digest d h , and it outsources auth(D h ), D h , the digest d h  and its signature to some untrusted entities, called servers as shown in  FIG. 7 . On input a data structure query q (e.g., an intersection query) sent by clients, the servers use auth(D h ) and D h  to compute proofs Π(q), by running algorithm query, and they return to the clients Π(q) and the signature on d h  along with the answer α(q) to q (See  FIGS. 8 and 9 ). Clients can verify these proofs Π(q) by running algorithm verify (since they have access to the signature of d h , they can verify that d h  is authentic). When there is is an update in the data structure (issued by the source), the source uses algorithm update to produce the new digest d′ h  to be used in next verifications while the servers update the authenticated data structure through refresh. 
         [0114]    Additionally, our ADS scheme           can also be used by a non-interactive verificatio protocol in the two-party model [30] as shown in  FIG. 2 . In this case, the source and the client coincide, i.e., the client issues both the updates and the queries, and it is required to keep only constant state, i.e., the digest of the authenticated data structure. Whenever there is an update by the client, the client retrieves a verifiable constant-size portion of the authenticated data structure that is used for locally performing the update and for computing the new local state, i.e., the new digest. A non-interactive two-party protocol that uses an ADS scheme for a data structure D is directly comparable with the recent protocols for verifiabl computing [1, 12, 16] for the functionalities offered by the data structure D, e.g., computation of intersection, union, etc. Due to space limitations, we defer the detailed description of these protocols to the full version of the paper. 
         [0115]    Furthermore, our ADS scheme           can also be used by a non-interactive verificatio protocol in the multi-party model [30] as shown in  FIG. 3 . That is, where there is more than one trusted source. In this instance, the multiple sources must synchronize together whenever there is an update by one of them to the server in order that they maintain a consistent collection of sets and can produce a digest that is verifiabl across all sets. 
         [0116]    Applications. First of all, our scheme can be used to verify keyword-search queries implemented by the inverted index data structure [4]: Each term in the dictionary corresponds to a set in our sets collection data structure which contains all the documents that include this term. A usual text query for terms m 1  and m 2  returns those documents that are included in both the sets that are represented by m 1  and m 2 , i.e., their intersection. Moreover, the derived authenticated inverted index can be efficientl updated as well. However, sometimes in keyword searches (e.g., keyword searches in the email inbox) it is desirable to introduce a “second” dimension: For example, a query could be “return emails that contain terms m 1  and m 2  and which were received between time t 1  and t 2 ”, where t 1 &lt;t 2 . We call this variant a timestamped keyword-search, which is shown in  FIG. 4 . One solution for verifying such queries could be to embed a timestamp in the documents (e.g., each email message) and have the client do the filterin locally, after he has verified—usin our scheme—the intersection of the sets that correspond to terms m 1  and m 2 . However, this approach is not operation-sensitive: The intersection can be bigger than the set output after the local filtering making this solution inefficient To overcome this inefficien y, we can use a segment-tree data structure [35], verifying in this way timestamped keyword-search queries efficientl with O(t log r+δ) complexity, where r is the total number of timestamps we are supporting. This involves building a binary tree T on top of sets of messages sent at certain timestamps and requiring each internal node of T be the union of messages stored in its children. Finally, our method can be used for verifying equi-join queries over relational tables, which boil down to set intersections. 
       Conclusion 
       [0117]    In this paper, we presented an authenticated data structure for the optimal verificatio of set operations. The achieved efficien y is mainly due to new, extended security properties of accumulators based on pairing-based cryptography. Our solution provides two important properties, namely public verifiability and dynamic updates, as opposed to existing protocols in the verifiabl computing model that provide generality and secrecy, but verifiability in a static, secret-key setting only. 
         [0118]    A natural question to ask is whether outsourced verifiabl computations with secrecy and efficient dynamic updates are feasible. Analogously, it is interesting to explore whether other specifi functionalities (beyond set operations) can be optimally and publicly verified Finally, according to a recently proposed definitio of optimality [33], our construction is nearly optimal: verificatio and updates are optimal, but not queries. It is interesting to explore whether an optimal authenticated sets collection data structure exists, i.e., one that asymptotically matches the bounds of the plain sets collection data structure, reducing the query time from O(N log 2  N) to O(N). 
         [0119]    It would be appreciated by those skilled in the art that various changes and modification can be made to the illustrated embodiments without departing from the spirit of the present invention. All such modification and changes are intended to be within the scope of the present invention except as limited by the scope of the appended claims. 
       REFERENCES 
       [0000]    
       
         [1]B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficien verificatio via secure computation. In  Int. Colloquium on Automata, Languages and Programming  (ICALP), pp. 152-163, 2010. 
         [2]M. J. Atallah, Y. Cho, and A. Kundu. Efficien data authentication in an environment of untrusted third-party distributors. In  Int. Conference on Data Engineering  (ICDE), pp. 696-704, 2008. 
         [3]M. H. Au, P. P. Tsang, W. Susilo, and Y. Mu. Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems. In  RSA, Cryptographers&#39; Track  (CT-RSA), pp. 295-308, 2009. 
         [4]R. Baeza-Yates and B. Ribeiro-Neto.  Modern Information Retrieval . Addison-Wesley Publishing Company, Reading, Mass., 1999. 
         [5]M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementality at reduced cost. In  Advances in Cryptology  (EUROCRYPT), pp. 163-192, 1997. 
         [6]S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiabl delegation of computation over large datasets. In  Int. Cryptology Conference  (CRYPTO), 2011. 
         [7]M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories.  Algorithmica,  12(2/3):225-244, 1994. 
         [8]D. Boneh and X. Boyen. Short signatures without random oracles and the SDH assumption in bilinear groups.  J. Cryptology,  21(2):149-177, 2008. 
         [9]D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data. In  Theoretical Cryptography Conference  (TCC), pp. 535-554, 2007. 
         [10]S. Canard and A. Gouget. Multiple denominations in e-cash with compact transaction data. In  Financial Cryptography  (FC), pp. 82-97, 2010. 
         [11]K.-M. Chung, Y. Kalai, F.-H. Liu, and R. Raz. Memory delegation. In  Int. Cryptology Conference  (CRYPTO), 2011. 
         [12]K.-M. Chung, Y. Kalai, and S. Vadhan. Improved delegation of computation using fully homomorphic encryption. In  Int. Cryptology Conference  (CRYPTO), pp. 483-501, 2010. 
         [13]I. Damgard and N. Triandopoulos. Supporting non-membership proofs with bilinear-map accumulators. Cryptology ePrint Archive, Report 2008/538, 2008. http://eprint.iacr.org/. 
         [14]C. Dwork, M. Naor, G. N. Rothblum, and V. Vaikuntanathan. How efficien can memory checking be? In  Theoretical Cryptography Conference  (TCC), pp. 503-520, 2009. 
         [15]M. J. Freedman, K. Nissim, and B. Pinkas. Efficien private matching and set intersection. In  Advances in Cryptology  (EUROCRYPT), pp. 1-19, 2004. 
         [16]R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiabl computing: Outsourcing computation to untrusted workers. In  Int. Cryptology Conference  (CRYPTO), pp. 465-482, 2010. 
         [17]M. T. Goodrich, R. Tamassia, and J. Hasic. An efficien dynamic and distributed cryptographic accumulator. In  Information Security Conference  (ISC), pp. 372-388, 2002. 
         [18]M. T. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In  DARPA Information Survivability Conference and Exposition II  (DISCEXII), pp. 68-82, 2001. 
         [19]M. T. Goodrich, R. Tamassia, and N. Triandopoulos. Super-efficien verificatio of dynamic outsourced databases. In  RSA, Cryptographers&#39; Track  (CT-RSA), pp. 407-424, 2008. 
         [20]M. T. Goodrich, R. Tamassia, and N. Triandopoulos. Efficien authenticated data structures for graph connectivity and geometric search problems.  Algorithmica,  60(3):505-552, 2011. 
         [21]D. Kratsch, R. M. McConnell, K. Mehlhorn, and J. P. Spinrad. Certifying algorithms for recognizing interval graphs and permutation graphs. In  Symposium on Discrete Algorithms  (SODA), pp. 158-167, 2003. 
         [22]J. Li, N. Li, and R. Xue. Universal accumulators with efficien nonmembership proofs. In  Applied Cryptography and Network Security  (ACNS), pp. 253-269, 2007. 
         [23]C. Martel, G. Nuckolls, P. Devanbu, M. Gertz, A. Kwong, and S. G. Stubblebine. A general model for authenticated data structures.  Algorithmica,  39(1):21-41, 2004. 
         [24]R. C. Merkle. A certifie digital signature. In  Int. Cryptology Conference  (CRYPTO), pp. 218-238, 1989. 
         [25]Y. Minsky, A. Trachtenberg, and R. Zippel. Set reconciliation with nearly optimal communication complexity.  IEEE Transactions on Information Theory,  49(9):2213-2218, 2003. 
         [26]R. Morselli, S. Bhattacharjee, J. Katz, and P. J. Keleher. Trust-preserving set operations. In  Int. Conference on Computer Communications  (INFOCOM), 2004. 
         [27]M. Naor and K. Nissim. Certificat revocation and certificat update. In  USENIX Security Symposium , pp. 217-228, 1998. 
         [28]L. Nguyen. Accumulators from bilinear pairings and applications. In  RSA, Cryptographers&#39; Track  (CT-RSA), pp. 275-292, 2005. 
         [29]H. Pang and K.-L. Tan. Authenticating query results in edge computing. In  Int. Conference on Data Engineering  (ICDE), pp. 560-571, 2004. 
         [30]C. Papamanthou and R. Tamassia. Time and space efficien algorithms for two-party authenticated data structures. In  Int. Conference on Information and Communications Security  (ICICS), pp. 1-15, 2007. 
         [31]C. Papamanthou and R. Tamassia. Cryptography for efficien y: Authenticated data structures based on lattices and parallel online memory checking. Cryptology ePrint Archive, Report 2011/102, 2011. http://eprint.iacr.org/. 
         [32]C. Papamanthou, R. Tamassia, and N. Triandopoulos. Authenticated hash tables. In  Int. Conference on Computer and Communications Security  (CCS), pp. 437-448, 2008. 
         [33]C. Papamanthou, R. Tamassia; and N. Triandopoulos. Optimal authenticated data structures with multilinear forms. In  Int. Conference on Pairing - Based Cryptography  (PAIRING), pp. 246-264, 2010. 
         [34]F. P. Preparata and D. V. Sarwate. Computational complexity of Fourier transforms over finit fields  Mathematics of Computation,  31(139):pp. 740-751, 1977. 
         [35]F. P. Preparata and M. I. Shamos.  Computational Geometry: An Introduction . Springer-Verlag, New York, N.Y., 1985. 
         [36]R. Tamassia. Authenticated data structures. In  European Symp. on Algorithms  (ESA), pp. 2-5, 2003. 
         [37]R. Tamassia and N. Triandopoulos. Certificatio and authentication of data structures. In  Alberto Mendelzon Workshop on Foundations of Data Management,  2010. 
         [38]Y. Yang, D. Papadias, S. Papadopoulos, and P. Kalnis. Authenticated join processing in outsourced databases. In  Int. Conf. on Management of Data  (SIGMOD), pp. 5-18, 2009. 
         [39]M. L. Yiu, Y. Lin and K. Mouratidis. Efficien verificatio of shortest path search via authenticated hints. In  Int. Conference on Data Engineering  (ICDE), pp. 237-248, 2010.