Survey

* Your assessment is very important for improving the workof artificial intelligence, which forms the content of this project

Survey

Document related concepts

Transcript

Computational Bounds on Hierarchical Data Processing with Applications to Information Security Roberto Tamassia and Nikos Triandopoulos Department of Computer Science, Brown University. Email: {rt, nikos}@cs.brown.edu Abstract. We study the complexity of a class of computations based on a directed acyclic graph (DAG) that describes the computation of a collection of output values from an input set of n elements. We present an Ω(log n) lower bound on various computational cost measures for our class of computations. Also, we develop a new randomized DAG scheme that provides improved computational performance over previously known schemes. We apply our results to two information security problems, data authentication through cryptographic hashing and multicast key distribution using key-graphs. We show that both problems involve hierarchical data processing and prove logarithmic lower bounds on their computational and communication costs. Also, using our new DAG scheme, we present a new authenticated dictionary data structure with improved authentication overhead. Finally, we present a new skip-list version such that the expected number of comparisons in a search is 1.25 log2 n + O(1). 1 Introduction In this paper, we present a unified analysis and design of algorithms and data structures for two important, and seemingly unrelated, information security problems, the authentication of membership queries in the presence of data replication at untrusted directories and the distribution of cryptographic keys by the controller of a dynamic multicast group. We provide logarithmic lower bounds on various time and space cost measures for these problems. We also develop new efficient data structures and give an accurate analysis of their performance, taking into account constant factors in the leading asymptotic term. Our unified approach is based on the definition of the class of hierarchical data processing problems, where a directed acyclic graph (DAG) describes the computation of a collection of output values from an input set of n elements. We define structural metrics for subgraphs of a DAG that express cost measures related to computations in a hierarchical data processing problem. We prove Ω(log n) lower bounds on these cost measures using a reduction to searching by comparisons in an ordered set. We also design a new randomized DAG scheme for hierarchical data processing problems, based on a variation of the skip-list. Our results for the two information security problems are obtained by showing that they can be modeled by a hierarchical data processing problem and by appropriately applying to their domain the general lower bounds and our new data structure. Our contributions are summarized as follows. Hierarchical Data Processing We introduce the class of hierarchical data processing (HDP) problems and study their complexity. This class models computations on a dynamic set of elements that share the following characteristics. Associated with the elements is a structured collection of values, organized according to a DAG. As elements change over time, the values are accordingly updated, where various costs regarding the computations involved depend on certain structural properties of the underlying DAG. Finally queries on elements are issued, where typically the answer of a query is a subset of the associated values. Again, the cost of answering a query depends on the hierarchy induced by the DAG. Previous Work. We are not aware of any previous systematic study of the class of HDP problems. Our Results. We define several cost measures for subgraphs of a DAG that characterize the space and time complexity of queries and update operations in a HDP problem. For a problem of size n, we relate each of these cost measures to the number of comparisons performed in the search of an element in an ordered set of size n. Through this reduction, we prove an Ω(log n) lower bound on the space and time complexity of query and update operations in a hierarchical data processing problem. We also show that trees are optimal DAG structures compared with general DAGs. We also design a new randomized DAG for HDP problems, based on a variation the skip-list. We give a detailed analysis of the cost measures of our scheme taking into account the constant factor on the leading asymptotic term. Skip-Lists The skip-list, introduced in [25, 26], is an efficient randomized data structure for dictionaries. Previous Work. A search in a skip-list with n elements takes 1.5 log2 n + O(1) expected comparisons [25, 26], Our Results. As a first application of our improved DAG, we design a new type of skip-list where the expected number of comparisons in a search is 1.25 log2 n + O(1), which is closer to optimal up to an additive constant term. Authenticated Data Structures With the growing use of Web services and data replication applications, queries on a data structure are often answered by a third party different from the source of the data. Thus, the problem arises of authenticating the answers given by this third party, which may not be trusted by the user. An authenticated data structure (ADS ) is a distributed model of computation where a directory answers queries on a data structure on behalf of a trusted source and provides to the user a cryptographic proof of the validity of the answer. The source signs a digest (i.e., a cryptographic summary) of the content of the data structure and sends it to the directory. This signed digest is forwarded by the directory to the user together with the proof of the answer to a query. To verify the validity of answer, the user computes the digest of the data from the answer and the proof, and compares this computed digest against the original digest signed by the source. Cost parameters for an ADS include the space used (for the source and directory), the update time (for the source and directory), the query time (for the directory), the digest size, the proof size and the verification time (for the user). In the important class of hash-based authenticated data structures, the digest of the data set is computed by hierarchical hashing, i.e., by hierarchically applying a cryptographic hash function over the data set. Section 4 provides more details about the model and authenticated dictionaries. Previous Work. Early work on ADSs has focused on hash-based authenticated dictionaries. The hash tree scheme by Merkle [18, 19] implements a static authenticated dictionary by hierarchical hashing over a balanced binary tree. For a set of size n, the scheme uses O(n) space and has O(log n) proof size, query time and verification time. Dynamic authenticated dictionaries that achieve O(log n) proof size, query time, update time and verification time are presented in [23] (based on hash trees) and in [1, 11] (base on skip-lists). Other authentication schemes for dictionaries, based on variations of hash trees, have been proposed in [2, 8, 16]. General techniques for hash-based query authentication are presented in [17, 13]. Beyond dictionaries, hashbased ADSs have been developed for relational database operations and multidimensional orthogonal range queries [7], pattern matching in tries and multidimensional orthogonal range searching (static case) [17], path and connectivity queries in dynamically evolving graphs and search queries in 2-dimensional static geometric objects (e.g., point location queries and segment intersection queries) [13]. An alternative approach to the design of an authenticated dictionary, based on the RSA accumulator (and not on hierarchical hashing), is presented in [12]. Related work on accumulators appears in [3]. Work related to ADSs includes [6, 9, 22, 1]. Related to ADSs is also recent work on consistency proofs [20, 24] that models data authentication in a more adversarial environment, where the data source is not considered trusted per-se, but the proposed schemes use significantly more computational resources than ADSs. The computational overhead incurred by an authenticated data structure over a non-authenticated one consists of: (1) the additional space used to store authentication information (e.g., signatures and hash values) in the data structure and in the proof of the answer, and (2) the additional time spent performing authentication computations (e.g., signatures and cryptographic hashes) in query, update and verification operations. Since cryptographic operations such as signatures and hashes are orders of magnitude slower than comparisons and a single hash value is relatively long (e.g., 16B or 20B), the authentication overhead dominates the performance of an ADS. All the existing hash-based authenticated dictionaries have logarithmic query, update and verification cost and logarithmic proof cost. Naor and Nissim [23] posed as an open problem the question of whether one can achieve sublogarithmic authentication overhead for dictionaries. We answer this question negatively for hash-based ADSs. Our Results. We present the first study on the cost of authenticated data structures, focusing on dictionaries. In Section 4, we model a hash-based dictionary ADS as a hierarchical data processing problem. We consider a very general authentication technique where hashing is performed over the data set in any possible way and where more than one digests of the data structure are digitally signed by the source. Applying our results from Section 2 in this domain, we prove the first nontrivial lower bound on the authentication cost for dictionaries. In particular, we show that in any hash-based authenticated dictionary of size n where the source signs k digests of the data set, any of the authentication costs (update/query time, proof size or verification time) is Ω(log nk ) in the worst case. Thus, the optimal trade-off between signature cost and hashing cost is achieved with O(1) signature cost and Ω(log n) hashing cost. In this case, we show that hash-based authenticated dictionaries of size n incur Θ(log n) complexity. We also present a new hash-based dictionary ADS based on our skip-list structure from Section 3 and show that it has better authentication cost parameters than previous hash-based ADS constructions. Multicast Key Distribution Multicast key distribution (or multicast encryption) is a model for realizing secrecy in multicast communications among a dynamic group of n users. To achieve secrecy, one needs to extend the conventional point-to-point encryption schemes to the multicast transmission setting. Namely, the users share a common secret key, called group-key, and encrypt multicast messages with this key, using a secret-key (symmetric) encryption scheme. When changes in the multicast group occur (through additions/deletions of users), in order to preserve (forward and backward) security, the group-key needs to be securely updated. In general, a group controller (physical or logical entity) is responsible for distributing an initial set of keys to the users. Each user possesses his own secret-key (known only to the controller), the group-key and a subset of other keys. Upon the insertion or removal of a user into/from the group, a subset of the keys of the users are updated. Namely, new keys are encrypted by some of the existing keys so that only legitimate users in the updated group can decrypt them. The main cost associated with this problem is the number of messages that need to be transmitted after an update. Additional costs are related to the computational time spent for key encryptions and decryptions. Previous Work. Many schemes have been developed for multicast key distribution. We focus on the widely studied key-graph scheme, introduced in [32, 33], where constructions are presented for key-graphs realized by balanced binary trees such that O(log n) messages are transmitted after an update, where n is the current number of users. Further work has been done on key-graphs based on specific classes of binary trees, such as AVL trees, 2-3 trees and dynamic trees. See, e.g., [14, 10, 27]. In [5], the first lower bounds are given for a restricted class of key distribution protocols, where group members have limited memory or the key distribution scheme has a certain structure-preserving property. In [29], an amortized logarithmic lower bound is presented on the number of messages needed after an update. The authors prove the existence of a series of 2n update operations that cause the transmission of Ω(n log n) messages. Recently, a similar amortized logarithmic lower bound has been shown in [21] for a more general class of key distribution protocols, where one can employ a pseudorandom generator to extract (in a one-way fashion) two new keys from one key and one can perform multiple nested key encryptions. Pseudorandom generators for this problem were first described in [4], where the number of messages are decreased from 2 log n to log n. Our Results. We show that the multicast key distribution problem using key-graphs is a hierarchical data processing problem. Applying our results from Sections 2 and 3 to this domain: (i) we perform the first study of general key-graphs (other than trees) and show that trees are optimal structures; (ii) we prove an exact worst-case logarithmic lower bound on both the communication cost (number of messages) and the computational cost (cost due to encryption/decryption) of any update operation, the first of this type; and (iii) we present a new scheme (tree DAG) that achieves costs closer to the theoretical optimal. Note that we give the first lower bounds on the encryption/decryption costs and that our lower bound proof is more generic since it depends on no certain series of update operations. In essence, we present the first exact, worst case logarithmic lower bound for the communication cost of the multicast key distribution problem. All of the previously known lower bounds are amortized, i.e., they prove the existence of a sequence of updates that include an expensive (of at least logarithmic cost) one. In contrast, we prove the existence of a single update of at least blog nc + 1 communication cost for any instance of the problem. Our lower bound holds also for protocols that use pseudorandom generators or multiple encryption, as in the model studied in [21]. These results are described in Section 5. Organization of the Paper The rest of the paper is organized as follows. In Section 2, we introduce the problems of hierarchical data processing, study their complexity, prove lower bounds on various associated costs and show that tree DAGs are optimal when used to lead data processing. In view of these results, we focus on tree DAGs and in Section 3 we design and analyze a new DAG for the hierarchical data processing problem that is based on skip-lists and achieves performance close to optimal. In Section 4 we apply our results to data authentication problem through hashing and in Section 5 to the multicast key distribution using key-graphs. Symbol [A] in lemmas and theorems denotes that the corresponding proof is presented in the Appendix. This extended abstract omits some of the details of our work. A full version is available in [31]. 2 Hierarchical Data Processing and its Theoretical Limits In this section, we define several structural metrics for subgraphs of a DAG and prove lower bounds on cost measures of these metrics. Such cost measures are related to the computational complexity of operations in a class of problems that we call hierarchical data processing problems. Our lower bounds are naturally translated to complexity results of this type of problems. DAG Scheme Before we introduce our new concepts, we recall some graph terminology. Let G = (V, E) be a directed acyclic graph. For each node v of G, indeg(v) denotes the in-degree of v, i.e., the number of incoming edges of v, and similarly, outdeg(v) denotes the out-degree of v, i.e., the number of outgoing edges of v. A source of G is a node v such that indeg(v) = 0. A sink of G is a node v such that outdeg(v) = 0. We denote with Vso ⊂ V the set of source nodes of G and with Vsi ⊂ V the set of sink nodes of G. For any edge e = (u, v) in E, node u is a predecessor of v and node v is a successor of u. A directed path connecting node u to some other node is called trivial, if every node in the path other than u has in-degree 1. A subgraph H of G is said to be weakly connected, if it is connected when one ignores edge directions and non-trivial, if it contains no trivial paths. For any node v in a DAG G, Gv denotes the subgraph in G whose nodes are connected with v through directed paths that start at v, i.e., they are successor nodes of v in the transitive closure of G. We say that subgraph Gv is reachable from node v. Definition 1 (DAG scheme). A DAG scheme Γ is a quadruple (G, S, n, k), where G = (V, E) is a directed acyclic graph without parallel edges, S ⊂ V is a set of special nodes and n and k are integers such that: (i) |Vso | = n; (ii) |V | is O(n); and (iii) |S| = k, S ⊃ Vsi and S ∩ Vso = ∅. That is, G has n source nodes and O(n) nodes in total; G contains a subset of k non-source nodes, called special nodes, that includes all the sink nodes of G. We first define three structural metrics for a subgraph of a DAG. Definition 2 (Structural metrics for subgraphs). Let H = (VH , EH ) be a weakly connected subgraph of a DAG G. We define the following with respect to G: (i) The node size size(H) of H is the number of nodes in H, i.e., size(H) = |VH |; (ii) the degree P size indeg(H) of H is the sum of the in-degrees (with respect to G) of the nodes of H, i.e., indeg(H) = v∈H indeg(v); (iii) the combined size comb(H) of H is the sum of its node and degree sizes, i.e., comb(H) = size(H) + indeg(H); (iv) the boundary size bnd(H) of H is the number of edges of G that enter nodes of H but are not in H. Whenever it is not clear from the context with respect to which DAG G a structural metric is defined, we use subscripts; e.g., indegH (·) denotes the degree size with respect to graph H. Using the above structural metrics, we define three cost measures for a DAG scheme Γ . Definition 3 (Cost measures of DAG scheme). Given a DAG scheme Γ = (G, S, n, k), let s be a source node of G. Let Pst denote the set of directed paths connecting node s to node t in G. The associated path πs of s is a directed path in Gs that starts at s, ends at a node of S and has the minimum combined size among all such paths, i.e., comb(πs ) = minu∈S,p∈Psu comb(p). We define the following cost measures for Γ : 1. the update cost U(Γ ) of Γ is U(Γ ) = maxs∈Vso comb(Gs ), i.e., the maximum, over all source nodes in Vso , combined size of the subgraph Gs reachable from s; 2. the query cost Q(Γ ) of Γ is Q(Γ ) = maxs∈Vso comb(πs ) = maxs minu∈S,p∈Psu comb(p), i.e., the maximum, over all source nodes in Vso , combined size of the associated path πs of s; 3. the sibling cost S(Γ ) of Γ is S(Γ ) = maxs∈Vso bnd(πs ), i.e., the maximum, over all source nodes in Vso , boundary size of the associated path πs of s. Note that the associated path of a source node s (which is not necessarily unique) is generally not the minimum boundary size path from s to a node in S, because for general graphs minimum combined size does not imply minimum boundary size. The following lemma states some useful statements about the structural metrics of a DAG and the cost measures of a DAG scheme. Lemma 1. Let Γ = (G, S, n, k) be a DAG scheme with update cost U(Γ ), query cost Q(Γ ) and sibling cost P S(Γ ), H be a subgraph of G and p be any directed path. We have (with respect to G): (i) comb(H) = v∈H (1+ indeg(v)) and bnd(p) = 1+indeg(p)−size(p); (ii) comb(H) > indeg(H) ≥ size(H) and indeg(H) ≥ bnd(H); (iii) U(Γ ) ≥ Q(Γ ) > S(Γ ). [A] Note that, by the above lemma, for any DAG scheme, the update cost is no less than the query cost and the query cost is no less than the sibling cost. This fact will be used for the lower bound derivation: it suffices to focus only on the smallest of the costs of a DAG scheme, i.e., its sibling cost. In particular, from Lemma 1, in the worst case, the combined and boundary sizes of the associated paths of source nodes of DAG scheme Γ = (G, S, n, k), and also any structural metric of the subgraphs reachable from the source nodes of G or of their associated paths, are each lower bounded by cost measure S(Γ ) of Γ . Our motivation for introducing DAG schemes is that they can be used to model a computational problem where a DAG G holds a collection of n input elements (stored at the source nodes) and O(n) output values (stored at the non-source nodes) which are computed using the DAG structure. Query operations on elements return a collection of values and update operations modify the DAG G and the input elements, causing accordingly the set of values to be updated. We consider problems where computations are performed sequentially and hierarchically according to the hierarchy induced by the underlying DAG and where the computational cost (time, space, or communication complexity) of a query and update operation can be expressed as the as the combined, degree or boundary size of a subgraph Gs or πs of a source node s of G, where every node v in H contributes to the cost an amount proportional to indegG (v). Generally, any computational cost of problems in this class is completely characterized by structural metrics of subgraphs of DAG G. We refer to such, due to space limitations, informally defined problems as hierarchical data processing (HDP) problems. In the rest of the section we study the cost measures of general DAG schemes and accordingly derive results that explain the inherent computational limits that exist in any HDP problem and that, furthermore, characterize the optimal DAG scheme structure for these problems. Sibling Cost Vs. Search by Comparisons We first show that the cost measures for a tree-based DAG scheme are related to the number of comparisons in a search tree derived from the scheme. By the above discussion and Lemma 1, focusing on the sibling cost suffices. A directed tree is a DAG resulting from a rooted tree when its edges are assigned directions towards the root of the tree. Let (X, ¹) a totally ordered set of size n, drawing values from universe U , where ¹ is a binary relation, referred as greater or equal. Given any element y ∈ U , we say that we locate y in X if we find the predecessor (element) of y in X, if it exists, defined to be the maximum (with respect to relation ¹) element x ∈ X such that x ¹ y. Locating an existing element of X in X corresponds to finding the element itself. A leaf-based search tree for (X, ¹) is a rooted tree where leaves store elements in X and internal nodes are assigned elements from X such that by searching the tree through comparisons ¹, the predecessor x of y in X can be located for any y ∈ U . Lemma 2. Let (X, ¹) a totally ordered set with n elements drawn from universe U and let (T, S, n, 1) be a DAG scheme, where T is a directed tree. We can build from T a search tree T 0 for X by storing the elements of X at the leaves of T and assigning tuples of elements in X to internal tree nodes of T , such that using T 0 any element x ∈ X stored at source node s of T can be found in X with bnd(πs ) comparisons. [A] Lemma 2 draws a direct analogy between the sibling cost of any tree-based DAG scheme and the number of comparisons performed in a search tree corresponding to the DAG scheme. We use this analogy as the basis for a reduction from searching by comparisons to any computational procedure of a HDP problem with cost that is expressed by the sibling cost of a tree-based DAG scheme. Theorem 1. Any DAG scheme ∆ = (T, S, n, 1) such that T is a directed tree has Ω(log n) update, query and sibling costs. Proof. It follows from Lemma 2 and the Ω(log n) lower bound on searching for an element in an ordered sequence in the comparison model [15]. This fundamental result states that any algorithm for finding an element x in a list of n entries, by comparing x to list entries, must perform at least blog nc + 1 comparisons for some input x. The above statement holds also for any search tree built for a totally ordered set X of size n, since any search path in the tree completely describes the sequence of comparisons performed in the search. From Lemma 2, we get that for any DAG scheme ∆ = (T, S, n, 1) with T being a directed tree, there exists a source node s such that the boundary size bnd(πs ) of the associated path of s is at least blog nc, i.e., bnd(πs ) is Ω(log n). By definition, for any DAG scheme ∆ = (T, S, n, 1) we have that S(∆) is Ω(log n) and since S(∆) < Q(∆) ≤ U(∆), we finally get that Q(∆) is Ω(log n) and that U(∆) is Ω(log n). 2 Note that the associated path πs in a tree is also the minimum boundary size path from s to the root, thus, the logarithmic lower bound applies also to the maximum (over all source nodes) minimum boundary size of a path from the source node to the special node in T . Optimality of Tree Structures Next, we show that trees have optimal cost measures among all possible DAG schemes. Theorem 2. Let Γ = (G, S, n, 1) be a DAG scheme. There exists a DAG scheme ∆ = (T, S, n, 1) such that T is a directed tree and U(∆) ≤ U(Γ ), Q(∆) ≤ Q(Γ ), and S(∆) ≤ S(Γ ). [A] Note that the directed tree T in the proof is an optimal tree with respect to the structural metric combined size, but not necessarily optimal with respect to the structural metric boundary size. Finally, we examine how allowing more than one special node in a DAG scheme affects its cost measures. We have that a DAG scheme Γ with k special nodes achieve minimum cost measures when the roots of at most k distinct trees are the only special nodes in Γ . Lemma 3. Let Γ = (G, SG , n, k) be a DAG scheme. There exists a DAG scheme Φ = (F, SF , n, `) such that F is a forest of ` ≤ k directed trees, SF ⊆ SG and additionally U(Φ) ≤ U(Γ ), Q(Φ) ≤ Q(Γ ), and S(Φ) ≤ S(Γ ). [A] The following theorem, which follows from Theorems 1 and 2 and Lemma 3, summarizes the results of this section with respect to the cost measures of any DAG scheme. Theorem 3. Any DAG scheme Γ = (G, S, n, k) has Ω(log nk ) update, query and sibling costs. [A] The above results form a reduction from searching by comparisons to computations related to HDP problems (computations performed sequentially and hierarchically according to the hierarchy induced by the underlying DAG scheme) and give us lower bounds on costs of these computations. Also, the optimality of tree-based DAG schemes over general graphs further characterize the optimal schemes for HDP problems. The connection between HDP problems and DAG schemes is explained in Sections 4 and 5, where we model two information security problems as HDP problems and translate the results of this section to their domain. 3 A New DAG Scheme Based on Skip-Lists In view of the logarithmic lower bounds and the optimality of tree structures in terms of cost measures of DAG schemes, we describe a new tree-based DAG scheme that is based on skip-lists [25, 26]. Our DAG scheme ∆ = (T, S, n, 1), which we call skip-list DAG, is defined with respect to skip-lists. We study the performance of ∆ and show that the structural metrics size(·), indeg(·) and bnd(·) have low expected values. Skip-Lists and Bridges We briefly describe some useful notation. A skip-list with probability parameter p is a set of lists L1 , ..., Lh , where L1 stores the element of a totally ordered set (X, ¹) of size n (sorted according to ¹), with elements drawn from universe U , and, for each i, each of the elements of list Li is independently chosen to be contained in Li+1 with probability p. Lists are viewed as levels and we consider all elements of the same value that are stored in different levels to form a tower. The level of a tower is the the level of its top element. Each node of a tower has a forward pointer to the successor element in the corresponding list and a pointer to the element one level below it. A header tower that stores sentinel element −∞ (minimum with respect to ¹ value in U ) is included in the skip-list as the left-most tower of level one more than the maximum level in the skip-list. A node of the skip-list is a plateau node if it is the top node of its tower. Furthermore, we introduce the notion of a bridge and also define relative concepts. Definition 4. In a skip-list: (i) a bridge b is a sequence of towers of the same level, where no higher tower is interfering them and the plateau nodes of the towers are all reachable in a sequence using forward pointers; (ii) the bridge size |b| of bridge b is the number of towers in the bridge and the bridge size of a tower is the size of the bridge that the tower belongs to; (iii) a child bridge of b is a bridge that is contained under b and to which a tower of b is connected through forward pointers; (iv) the plateau towers of a tower t are the towers whose plateau nodes can be reached by t using one forward pointer. Directed Tree T We now describe the skip-list DAG scheme ∆ = (T, r, n, 1), where T is a directed tree with n leaves and one special node, the root r of T . We use the term skip-list DAG to refer to both ∆ and T . Skip-list DAG ∆ is defined with respect to a skip-list with probability parameter p. By list node we refer to a node of the skip-list and by DAG node to a node of T . An edge (v, u) in T is directed towards node u. We define an operation on DAG nodes, which, given existing DAG nodes in T , creates new DAG nodes and edges in T : if v, v1 , . . . , vl are nodes in T , then operation N ew(v, v1 , . . . , vl ) creates in T new nodes u1 , . . . , ul and new edges (v1 , u2 ), . . . , (vl−1 , ul ), (vl , v), edges (u1 , u2 ), . . . , (ul−1 , ul ) and (ul , v), where DAG node u1 is a source node in T , i.e., it creates and connects in T a directed path from new source node u1 to node v, where v1 , . . . , vl are sibling nodes in the path. Each DAG node is attached to some list node in the skip-list. The notion of a bridge is essential in skip-list DAG T . For each bridge b in the skip-list, a corresponding node v(b) is created in T . We call v(b) the DAG node of b. Node v(b) is connected in T with the DAG nodes of all the child bridges of b, so DAG T with respect to a skip-list is defined in a recursive way. First all bridges in the skip-list are identified and the DAG node for the outer bridge (header tower) is created. Then, given that the DAG node v(b) of a bridge b is created, using operation N ew(·), v(b) is connected with paths in T to the newly created DAG nodes of the child bridges of b, as follows (see Figure 1). b b v(b3) v(b) v(b) v(b13) v(t1) v(t2) v(t3) v(b12) v(b2) v(b1) v(b22) v(b11) v(b21) v(b31) u1 t3 t22 t31 t11 t12 t1 t2 t3 t13 t2 t21 t1 (a) (b) Fig. 1. Skip-list DAG ∆: DAG node v(b) of bridge b is recursively connected to the DAG nodes of the child bridges, for the case where (a) the size of bridge b is one or (b) the size of b is more than one. Circle nodes are DAG nodes of T and square nodes are list nodes of skip-list. A DAG node is assigned to the list node in which it is contained. t If the size of b is one (Figure 1(a)), let t1 , ..., tl be the plateau towers of t (in increasing level). If plateau tower ti belongs in bridge bi , then let v(b1 ), ..., v(bl ) be the DAG nodes of the bridges. We perform operation N ew(v(b), v(b1 ), . . . , v(bl )) where v(b) is the DAG node of b. New nodes of T are assigned to list nodes as follows: source node u1 (basis of recursion) is assigned to the lowest list node of the tower, node ui , 2 ≤ i ≤ l, is assigned to the list node of t at the level of bridge bi−1 and the DAG node v(b) of b is attached to the list node of t at the level of bridge bl . If the size of b is k > 1 (Figure 1(b)), then, let t1 , . . . , tk be the towers of b. For each such tower ti , we create a new DAG node v(ti ), 1 ≤ i ≤ k. For tower tk , we consider its, say l, plateau towers tk1 , . . . , tkl and perform operation N ew(v(tk ), v(bk1 ), . . . , v(bkl )), where bk1 , . . . , bkl are the child bridges of b that plateau towers ti1 , ..., til belong in. Moreover, for each tower ti , i < k, of, say l + 1, plateau towers, we consider its l lowest plateau towers ti1 , . . . , til , that is, for i < k, tower ti+1 is omitted from this sequence. Let bi1 , . . . , bil be the child bridges b that plateau towers ti1 , ..., til belong in. For tower ti , i < k, we perform operation N ew(v(ti ), v(bi1 ), . . . , v(bil )). Finally, we add k new edges in T : edge (v(ti ), v(b)) for 1 ≤ i ≤ k. New DAG nodes are assigned to list nodes of tower ti as before: v(b) is assigned to the top-left list node of b, any non-source node is assigned to the list node of ti at the level of the bridge it is connected to, and a source node is assigned to the lowest-level list node of ti . By this construction T is a directed tree with root the DAG node r of the header bridge and exactly n leaves. Skip-list DAG ∆ = (T, r, n, 1) (Figure 2, Appendix) is defined with respect to a skip-list, thus it is a randomized DAG scheme. Cost Measures of Skip-List DAG To analyze the cost measures of DAG scheme ∆, since we know that U(∆) = Q(∆) > S(∆), all lower bounded log n, it suffices to analyze the structural metrics of the associated path πs of a source node s, focusing on the constant factor of the leading logarithmic term. ∆ is a randomized DAG scheme, so we study its expected values of size(·), indeg(·) and bnd(·). We show that ∆ achieves cost measures that are close to the theoretical optimal (also for randomized DAG schemes) value of blog nc + 1. Theorem 4. With respect to a skip-list with probability parameter p, the skip-list DAG scheme Γ = (T, r, n, 1), for any fixed source node s of T and the corresponding source to root path πs , has the following expected 2 log p1 n + O(1); (iii) performance: (i) E[size(πs )] ≤ 2(1 − p) log p1 n + O(1); (ii) E[indeg(πs )] ≤ (1 − p) (1+p) p E[bnd(πs )] ≤ (1−p)(1+p2 ) p log p1 n + O(1); (iv) E[size(T )] ≤ (1 + pq 2 + pq + p q(2−pq 2 ) )n, where q = 1 − p. [A] From Lemma 2 and Theorem 4, we have a new version of the skip-list data structure with an expected number of comparisons closer to the theoretical optimal blog nc + 1, up to an additive constant term, than the one of the standard skip-list. The new skip-list version can be viewed as a multi-way extension of the skip-list data structure, thus referred as multi-way skip-list. Theorem 5. There is a multi-way version of a skip-list for set X of size n and probability parameter p, where the expected number of comparisons performed while searching in X for any fixed element is at most (1−p)(1+p2 ) log2 n + O(1), or 1.25 log2 n + O(1) for p = 21 . p log 1 2 p Proof. It follows from Lemma 2 and Theorem 4. Since for DAG scheme ∆ = (T, r, n, 1), T is a directed tree, from Lemma 2 we get a transformation of T into a search tree T 0 for set X, where interior nodes of T 0 are assigned with elements from X. It follows that every element xs in X stored at source node s of T 0 can be located with bnd(πs ) comparisons, which completes the proof. 2 The idea behind multi-way skip-list is to use our skip-list DAG ∆ as a search tree structure in the skip-list for searching elements in X. The multi-way skip-list is implemented by appropriately modifying the regular skip-list data structure, such that the search tree T 0 of Theorem 5 is implicitly represented and searches are performed according to T 0 . We can keep the simplicity in creating and updating a skip-list, but we can save element comparisons by using T 0 . Note that for bridges of size k ≥ 2, k − 1 (instead of k) comparisons are needed. Although the tree-like interpretation of skip-lists is known in the literature, our result provides a new such interpretation with closer to optimal search performance: the expected number 2 log2 n + O(1) for standard skip-lists (improved version in [26]) and is of comparison in a search is p 1−p log 1 2 p reduced to (1−p)(1+p2 ) 1 p log2 p log2 n + O(1) for multi-way skip-lists (e.g, for p = 21 , the logarithmic constant drops from 1.5 to 1.25). Multi-way skip-lists have a more explicit tree structure than standard skip-lists and can be viewed as randomized search trees. E[size(πs )] E[indeg(πs )] E[bnd(πs )] E[size(T )] red-black tree log n 2 log n log n 2n standard skip-list 1.5 log n 3 log n 1.5 log n 2n multi-way skip-list log n 2.25 log n 1.25 log n 1.9n Table 1. Comparison of three tree DAG schemes in terms of structural metrics. For red-black trees, expectation corresponds to the average search paths, which has size c log n for a constant c very close to 1 (see [28]). For skip-lists, p = 0.5. Note that comb(πs ) corresponds to the number of comparisons performed in the search path πs and that size(T ) corresponds to the total number of decision nodes in search tree T . We compare the multi-way skip-list with red-black tree and the standard skip-list (improved version [26], Figure 3, Appendix) in terms of the structural metrics of the search DAGs. For each tree DAG T and any fixed element stored at a source node s, we compare the expected values of the node size size(πs ), degree size indeg(πs ) and boundary size bnd(πs ) of path πs and the node size size(T ) of T . We omit the details of the comparison due to space limitations. Table 1 summarizes the comparison results. The multi-way skip-list DAG has better performance (achieves lower constants) when compared with the standard skip-list. On the other hand, we observe an interesting trade-off on the performance that reb-black tree and multi-way skiplists achieve, which suggests further investigation: in multi-way skip-lists the combined and boundary sizes of πs are larger but the node size of T is less. Note that the value size(T ) of the skip-list DAG is only an upper bound of the actual expected value (Theorem 4). The experimental value of size(T ) is close to 1.5n. 4 Data Authentication Through Hashing In this section, we apply our results of Sections 2 and 3 in data authentication through cryptographic hashing. We focus on authenticated dictionaries, authenticated data structures (ADSs) that authenticate membership queries. We show that this is a hierarchical data processing problem and, by applying our results, we get a logarithmic lower bound on the authentication cost for any authentication scheme that uses cryptographic hashes, and also a new authenticated dictionary based on skip-lists with authentication cost closer to optimal. ADSs provide a model of computation, where an untrusted directory answers queries issued by a user on a data structure on behalf of a trusted source and provides a proof of the validity of the answer to the user. In this model, authentication is achieved by having the data source signing some digest of the data, where, for data authentication through hashing, a hash function is systematically used to produce this digest. On any query, along with the answer, the signed digest and some information that relates the answer to this digest are also given to the user and these are used for the answer verification. Authenticated Dictionary Let X be a data set owned by the source that evolves through update operations insert and delete. Membership queries exists are issued on X. A (multivariate extension of a) cryptographic hash function h is used to produce a digest of set X which is signed by the source (see [13]). In our study, we actually consider a more general model where more than one digests are produced and signed by the source. These digests are computed through a hashing scheme over a directed acyclic graph (DAG) that has k signature nodes t1 , . . . , tk and stores the elements of X at the source nodes. Each node u of G stores a label or hash value L(u) such that, if u is a source of G, then L(u) = h(e1 , . . . , ep ), where e1 , . . . , ep are elements of X, else (u is not a source of G) L(u) = h(L(w1 ), . . . , L(wl ), e1 , . . . , eq ), where (w1 , u), . . . , (wl , u) are edges of G, e1 , . . . , eq are elements of X and p, q and l are some non negative integers. Without loss of generality, we focus our study on the canonical case where p = 1 and q = 0, noting that any general hashing scheme is equivalent to a canonical one. We view the labels L(ti ) of the signature nodes ti of G as the digests of X, which are computed via the above DAG G. The authentication technique is based on the following general approach. The source and the directory store identical copies of the data structure for X and maintain the same hashing scheme on X. The source periodically signs the digests of X together with a time-stamp and sends the signed time-stamped digests to the directory. When updates occur on X, they are sent to the directory together with the new signed time-stamped digests. We refer to this information as update authentication information. In this setting, the update authentication information has O(k) size. When the user poses a query, the directory returns to the user some answer authentication information, which consists of: (1) one signed time-stamped digest of X, (2) the answer to the query and (3) a proof consisting of a small collection of labels from the hashing scheme (or of data elements if needed) that allows the recomputation of the digest. The user validates the answer by recomputing the digest, checking that it is equal to the signed one and verifying the signature of the digest; the total time spent for this process is called the answer verification time. Security (against the possibility that the user verifies a, forged by the directory, proof for a non-authentic answer), typically follows from the properties of the signature scheme and the hash function. Authentication Overhead Now we study the performance overhead due to authentication-related computations in an authenticated dictionary based on a hashing scheme (the analysis is valid for any ADS). This overhead, called authentication overhead, consists of time overhead for the (i) maintenance of the hashing scheme after updates, (ii) generation of the answer authentication information in queries, and (iii) verification of the proof of the answer; communication overhead, defined as the size of the answer authentication information; storage overhead, given by the number of hash values used by the authentication scheme; and signature overhead, defined as the number of signing operations performed at the source (and thus the number of signatures sent by the source). Even with the most efficient implementations, the time for computing a hash function is a few orders of magnitude larger than the time for comparing two basic numerical types (e.g., integers or floating-point numbers). Thus, the rehashing overhead dominates the update time and the practical performance of an ADS is characterized by the authentication overhead, which depends on the hash function h in use and the mechanism used to realize a multivariate hash function from h. Cryptographic Hash Functions The basic cryptographic primitive for an ADS is a collision-resistant hash function h(x) that maps a bit string x of arbitrary length to a hash value of fixed length, such that collisions (i.e., distinct inputs that hash to same value) are hard to find. We refer to h simply as hash function. Generic constructions of hash functions are modeled by iterative computations [30] based on a compression function f (·) that is applied serially and iteratively on the input. Lemma 4. There exist constants c1 and c2 such that, given an input string x of size `, the iterative computation of a hash function h(x) takes time T (`) = c1 ` + c2 . [A] If h(x) be a hash function. In order to realize a hashing scheme, we extend h to a multivariate function using string concatenation. Namely, we define hC (x1 , ..., xd ) = h(x1 k...kxd ). There exist alternative realizations of a multivariate hash function (e.g., use hC for d = 2 and a binary hash tree for d > 2), but the following lemma states that, without loss of generality, we can restrict our analysis to the concatenation hash function hC . Lemma 5. Any realization of a d-variate function h(x1 , ..., xd ) can be expressed by iterative applications of hC expressed through a hashing scheme G. Cost of Data Authentication Through Hashing Let G be any hashing scheme used to implement an hash-based authenticated dictionary for set X of size n, where k signature nodes store hash values signed by the source. Hashing scheme G along with the signature nodes can be viewed as DAG scheme Γ = (G, S, n, k), where special nodes are signature nodes and there are exactly n source nodes in G storing elements in X. Each cost parameter of the authentication overhead, (e.g., time overhead and storage overhead), is expressed as some structural metric of a subgraph of G. The node size corresponds to the number of hash operations that are performed at some of the three parties (source, directory or user) and the degree size to the total number of hash values that participate as operands in these hash operations. In particular, each cost parameter of the authentication overhead depends linearly on size(H) and indeg(H) for some subgraph H of G. Lemma 6. Let Γ = (G, S, n, k) be any hashing scheme used to implement a hash-based authenticated dictionary for set X, where special nodes are signature nodes. Let s be a source node of G storing element x ∈ X, Gs be the subgraph of G that is reachable from s, and πs the associated path of s. We have: (i) an update operation on element x has update time overhead that is lower bounded by comb(Gs ); (ii) a query operation on element x has verification time overhead that is lower bounded by comb(πs ) and communication overhead that is lower bounded by bnd(πs ); (iii) the storage overhead is size(G). All involved computations are performed according to the hierarchy induced by G. [A] Thus, hash-based authentication of membership queries is a HDP problem, where operations insert/delete are related to the update cost and operation exists to the query cost of the underlying DAG scheme. Theorems 1-4 and Lemma 6 suggest that signing more than one hash values does not help, tree hashing structures are optimal and also the use of our skip-list DAG to implement an authenticated dictionary. Theorem 6. In the data authentication model through hashing, any hashing scheme with k signature nodes that implements an authenticated dictionary of size n has (i) Ω(log nk ) worst-case update and verification time overheads; (ii) Ω(log nk ) worst-case communication overhead; and (iii) Ω(k) signature overhead. Theorem 7. There exists a skip-list authenticated dictionary of size n and probability parameter p that achieves the following expected performance. For any fixed element in the skip-list and constants c1 and c2 that depend on the hash function h in use, the expected hashing overhead of an update or verification operation 2 is lower bounded by (1−p)(2c2 + (1+p) c1 ) log p1 n+O(1), the expected communication cost is lower bounded by p 2 p 2 1 (1 − p)( 1+p p ) log p n + O(1) and the expected storage overhead is lower bounded by (1 + pq + pq + q(2−pq 2 ) )n, where q = 1 − p. 5 Multicast Key Distribution Using Key-Graphs In this section, we apply results from Sections 2 and 3 in multicast key distribution using key-graphs. We prove that key-trees are optimal compared to general key-graphs and derive logarithmic lower bounds for involved computational and communication costs. In contrast to previous amortized logarithmic lower bounds on the communication cost that any protocol requires [29, 21], we proof exact worst case lower bounds and our proof is more general, since it does not depend on any series of update operations. Multicast Key Distribution The problem refers to the confidentiality security problem in multicast groups. A group consists of a set of n users and a group key controller. Private key cryptography is used to transmit encrypted multicast messages to all the users of the group. These messages are encrypted using a group key available to all the current users of the group. The security problem arises when updates on the group are performed, i.e., when users are added or removed from the group. The goal is to achieve non-group confidentiality, i.e., only members of the group can decrypt the multicast messages, and forward (backward) secrecy, i.e., users deleted from (added in) the group can not decrypt messages transmitted in the future (past). No collusion between users should break any of the above requirements. Key-Graphs In this model, the group controller, a trusted authority and, conventionally, not member of the group, is responsible for distributing secret keys to the users and replacing (updating) them appropriately after user updates (additions/removals) in the group. The idea is that a set of keys, known to the controller, is distributed to the users, so that a key is possessed by more than one user and a user possesses more than one keys. In particular, any user is required to have a secret key that no other user knows and all users possess a group key, which is used for secure (encrypted) transmissions. In this model, on any user update, a subset of the keys needs to be updated to preserve the security requirements. Some keys are used for securely changing the group key as needed and for updating previous keys that have to be replaced. That is, new keys are encrypted with existing valid keys or with other previously distributed new keys. Key-graphs [32, 33] provide a framework to implement this idea. A key-graph models the possession of keys by users and the computations (key encryptions at the controller, key decryptions at the users) and message transmissions that need to be performed after any update. A key-graph is a single-sink DAG G that the group controller and users know and that facilitates group updates. Source nodes in G correspond to users and store their individual secret keys and all non source nodes correspond to keys that can be shared among many users. A user possesses all and only the keys that correspond to the subgraph Gs of G that is reachable from its source node s. On any update of the user corresponding to s, these keys have to change (the group key at the root is always among them) to achieve forward and backward secrecy. A new keys is distributed by being sent encrypted by an old or previously distributed key. Cost parameters The cost parameters associated with key distribution using key-graphs after an update are: (i) the computational cost at the controller, the encryption cost, for encrypting all new keys and thus producing the messages for transmission, and the computational cost at a user, the decryption cost, for decrypting received messages and updating her keys, (ii) the communication cost, the number of transmitted messages, and (iii) the total number of keys stored at the key controller or a user. We can view a key-graph G as DAG scheme Γ = (G, S, n, 1), where S consists of the unique sink node of G, called group node and n source nodes correspond to the users. Each cost parameter of key distribution is expressed as some structural metric of a subgraph of G. The node size corresponds to keys stored at users and also to key generations and the degree size corresponds to the number of encryptions and decryption performed during the update. In particular, each cost parameter depends linearly on size(H) and indeg(H) for some subgraph H of G. Lemma 7. Let Γ = (G, S, n, 1) be any key-graph scheme used to for the multicast group management problem, where the unique special node corresponds to the group key. Let s be any source node of G corresponding to a user u and Gs be the subgraph of G that is reachable from s. Then: (i) an update operation on user u results in size(Gs ) key changes, encryption cost that is lower bounded by comb(Gs ) and communication cost of indeg(Gs ); and (ii) the key-graph stores size(G) keys in total. All involved encryptions and decryptions are performed according to the hierarchy induced by G. [A] Thus, multicast key distribution using key-graphs is a HDP problem, where the overhead of an update in the group is related to the update cost of the underlying DAG scheme, and Theorems 1 and 2 translate to the following result. Theorem 8. For a multicast key distribution problem of size n using key-graphs, tree structures are optimal over general graphs and any update operation in the group requires at least blog nc + 1 communication cost and Ω(log n) encryption and decryption costs. We finish by noting that the above result holds even in the more general class of key-graph protocols described in [21], where (i) multiple encryptions are allowed to apply to new keys (e.g., key kv of node v, reachable through directed paths from nodes u1 , u2 , u3 is sent as Eku1 (Eku2 (Eku3 (kv )))) and (ii) pseudorandom generators can be used to build one-way key-chains by repeatedly expanding a key to two new ones. We refer to this model as extended key-graphs. Corollary 1. The complexity bounds of Theorem 8 hold also for the multicast key distribution problem using extended key-graphs. [A] References [1] A. Anagnostopoulos, M. T. Goodrich, and R. Tamassia. Persistent authenticated dictionaries and their applications. In Proc. Information Security Conference (ISC 2001), volume 2200 of LNCS, pages 379–393. SpringerVerlag, 2001. [2] A. Buldas, P. Laud, and H. Lipmaa. Eliminating counterevidence with applications to accountable certificate management. Journal of Computer Security, 10(3):273–296, 2002. [3] J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Proc. CRYPTO, 2002. [4] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas. Multicast security: A taxonomy and some efficient constructions. In Proc. INFOCOM ’99, volume 2, pages 708–716, New York, Mar. 1999. [5] R. Canetti, T. Malkin, and K. Nissim. Efficient communication - storage tradeoffs for multicast encryption. In Advances in cryptology (EUROCRYPT’99), LNCS 1592, pages 459–474, 1999. [6] P. Devanbu, M. Gertz, A. Kwong, C. Martel, G. Nuckolls, and S. Stubblebine. Flexible authentication of XML documents. In Proc. ACM Conference on Computer and Communications Security, 2001. [7] P. Devanbu, M. Gertz, C. Martel, and S. G. Stubblebine. Authentic third-party data publication. In Fourteenth IFIP 11.3 Conference on Database Security, 2000. [8] I. Gassko, P. S. Gemmell, and P. MacKenzie. Efficient and fresh certification. In Int. Workshop on Practice and Theory in Public Key Cryptography (PKC ’2000), volume 1751 of LNCS, pages 342–353. Springer-Verlag, 2000. [9] M. T. Goodrich, M. Shin, R. Tamassia, and W. H. Winsborough. Authenticated dictionaries for fresh attribute credentials. In Proc. Trust Management Conference, volume 2692 of LNCS, pages 332–347. Springer, 2003. [10] M. T. Goodrich, J. Z. Sun, and R. Tamassia. Efficient tree-based revocation in groups of low-state devices. In Advances in Cryptology – CRYPTO 2004, Lecture Notes in Computer Science. Springer-Verlag, 2004. [11] M. T. Goodrich and R. Tamassia. Efficient authenticated dictionaries with skip lists and commutative hashing. Technical report, Johns Hopkins Information Security Institute, 2000. Available from http://www.cs.brown. edu/cgc/stms/papers/hashskip.pdf. [12] M. T. Goodrich, R. Tamassia, and J. Hasic. An efficient dynamic and distributed cryptographic accumulator. In Proc. of Information Security Conference (ISC), volume 2433 of LNCS, pages 372–388. Springer-Verlag, 2002. [13] M. T. Goodrich, R. Tamassia, N. Triandopoulos, and R. Cohen. Authenticated data structures for graph and geometric searching. In Proc. RSA Conference—Cryptographers’ Track, pages 295–313. Springer, LNCS 2612, 2003. [14] J. Goshi and R. E. Ladner. Algorithms for dynamic multicast key distribution trees. In Proc. of the twenty-second Annual Symposium on Principles of Distributed Computing (PODC 2002), pages 243–251. ACM, 2003. [15] D. Knuth. The art of computer programming. Addison-Wesley, 1973. [16] P. C. Kocher. On certificate revocation and validation. In Proc. Int. Conf. on Financial Cryptography, volume 1465 of LNCS. Springer-Verlag, 1998. [17] C. Martel, G. Nuckolls, P. Devanbu, M. Gertz, A. Kwong, and S. Stubblebine. A general model for authentic data publication, 2001. Available from http://www.cs.ucdavis.edu/~devanbu/files/model-paper.pdf. [18] R. C. Merkle. Protocols for public key cryptosystems. In Proc. Symp. on Security and Privacy, pages 122–134. IEEE Computer Society Press, 1980. [19] R. C. Merkle. A certified digital signature. In G. Brassard, editor, Proc. CRYPTO ’89, volume 435 of LNCS, pages 218–238. Springer-Verlag, 1990. [20] S. Micali, M. Rabin, and J. Kilian. Zero-Knowledge sets. In Proc. 44nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 80–91, 2003. [21] D. Micciancio and S. Panjwani. Optimal communication complexity of generic multicast key distribution. In Advances in Cryptology — EUROCRYPTO 2003, volume 3027 of Lecture Notes in Computer Science, pages 153–170. Springer Verlag, 2004. [22] R. Morselli, S. Bhattacharjee, J. Katz, and P. Keleher. Trust-preserving set operations. In 23rd Conference of the IEEE Communications Society (Infocom), March 2004. [23] M. Naor and K. Nissim. Certificate revocation and certificate update. In Proc. 7th USENIX Security Symposium, pages 217–228, Berkeley, 1998. [24] R. Ostrovsky, C. Rackoff, and A. Smith. Efficient consistency proofs for generalized queries on a committed database. In Proc. 31th International Colloquium on Automata, Languages and Programming (ICALP), 2004. [25] W. Pugh. Skip list cookbook. Technical Report CS-TR-2286, Dept. Comput. Sci., Univ. Maryland, College Park, MD, July 1989. [26] W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM, 33(6):668–676, 1990. [27] O. Rodeh, K. P. Birman, and D. Dolev. Using AVL trees for fault tolerant group key management. International Journal on Information Security, pages 84–99, 2001. [28] R. Sedgewick. Algorithms in C++. Addison-Wesley, Reading, MA, 1992. [29] J. Snoeyink, S. Suri, and G. Varghese. A lower bound for multicast key distribution. In Proceedings IEEE Infocomm 2001, 2001. [30] D. R. Stinson. Cryptography: Theory and Practice, Second Edition. CRC Press Series, 2002. [31] R. Tamassia and N. Triandopoulos. Computational bounds on hierarchical data processing with applications to information security. Technical report, Brown University, 2004. Available from http://www.cs.brown.edu/ cgc/stms/papers/cbhdp.pdf. [32] D. M. Wallner, E. G. Harder, and R. C. Agee. RFC 2627 – Key management for multicast: issues and architecture, Sept. 1998. [33] C. K. Wong, M. Gouda, and S. S. Lam. Secure group communications using key graphs. IEEE/ACM Transactions on Networking, 8(1):16–30, 2000. Appendix Proof of Lemma 1 Proof. (i) By definition. (ii) By definition and noticing that size(H) > 0 and indeg(H) = bnd(H) + |EH | for any subgraph H in G. (iii) Note that the associated path πs of any source node of G is contained in the reachable from s graph Gs . Thus, comb(Gs ) ≥ comb(πs ) for any s and accordingly, U(Γ ) ≥ Q(Γ ). Similarly, since for any subgraph H of G we have from (ii) that comb(H) > bnd(H), we take that for any s ∈ Vso it holds that comb(πs ) > bnd(πs ). Thus, if s∗ is the source node in G with the associated path πs of maximum boundary size, we have that Q(Γ ) ≥ comb(πs∗ ) > bnd(πs∗ ) = S(Γ ). 2 Proof of Lemma 2 Proof. Assume that tree T is non-trivial. We fix a left-right ordering of the children of any node in T and using this ordering we also consider a topological order t(G) of T that corresponds to a postorder traversal of T . We traverse T according to t(G) and as we encounter leaves of T we store elements of X in increasing order. Using t(G) we next perform the following element assignment for each internal node in T . Each non-source node v with predecessor nodes u1 , . . . , u` (listed according to left-right ordering) is assigned the ordered (` − 1)-tuple of elements xv1 , . . . , xv`−1 ∈ X, where for 1 ≤ i ≤ ` − 1, xvi is the maximum element with respect to relation ¹ that is stored at the source nodes of the subtree in T defined by ui . Tree T along with the elements stored at leaves and elements assigned at internal nodes is a leaf-based search tree T 0 for set X. To search for element y ∈ U , while being at non-source node v, elements xv1 , . . . , xv`−1 can be used to decide to which node, among nodes u1 , . . . , u` , to advance our search: for relation Â being the complement of relation ¹, we advance the search at node u1 if y ¹ xv1 , at node u` if y Â xv`−1 , or otherwise at node ui , where i is the unique integer value 1 ≤ i ≤ ` − 2 such that y Â xvi and y ¹ xvi+1 . At source node s storing element xs , we report as the predecessor of y in X element xs . Correctness follows directly, by noticing that T 0 satisfies the desired search tree property: at any node, elements stored in subtrees of children nodes that are to the right (in the left-to-right ordering) are larger (with respect to relation ¹) than elements stored in subtrees of children nodes that are to the left (in this left-to-right ordering). At every new node, we correctly reduce our search space in X. Consider the search path ps for searching element x ∈ X that ends at source node s in T 0 (storing element x). Path ps is the associated path πs of s. If v is a non-source node of πs , indeg(v) − 1 comparisons at node v suffice to advance our search to the correct child is needed. Thus, we can find x in X by performing in total P P node of v and at node s, not comparison v∈πs (indeg(v)−1) = bnd(πs ) comparisons. If T contains trivial paths, v∈πs |indeg(v)>0 (indeg(v)−1) = 1+ the proof is as above with only one difference with respect to any node w with in-degree 1: we assign to w the element assigned to its child and perform no comparison ¹ at w, but immediately advance our search at the child node. The number of comparisons is again bnd(πs ). 2 Proof of Theorem 2 Proof. DAG scheme Γ has only one special node, the unique sink node of G, so associated paths of the source nodes of G are paths from a source node to the sink node of G. Fix a topological order t(G) of G. Define DAG T to be the union of all minimum combined cost directed paths πs for all source nodes in G, where ties in computing paths πs are broken using a consistent rule according to t(G). It is easy to see that the union is a directed tree: if two paths πs1 and πs2 from source nodes s1 and s2 cross at node v and meet again at node u (u may be the sink node of G), this contradicts the fact that each path has minimum combined cost or the tie breaking rule. By definition, it holds that U(∆) ≤ U(Γ ), since Ts is a subgraph of Gs . With respect to query and sibling cost, the associated path πs of source node s is the same in graphs G and T , but |EG | ≥ |ET |, thus indegT (πs ) ≤ indegG (πs ). So, Q(∆) ≤ Q(Γ ), and S(∆) ≤ S(Γ ), as stated. 2 Proof of Lemma 3 Proof. The proof is similar to the proof of Theorem 2. Consider the union F of the minimum combined size paths π1 , . . . , πn in G from source nodes s1 , . . . , sn to a special node, where ties break according to a well-defined and consistent rule. The resulting subgraph F of G is a forest: two paths never cross, but they only meet to same special node, and additionally, no path connecting two distinct special nodes exists in F . As in the proof of Theorem 2, since any subgraph Fs reachable from source node s in F is a subgraph of the corresponding reachable from s graph Gs in G, |EF | ≤ |EG |, and since the minimum combined size paths are the same in F we have that U(Φ) ≤ U(Γ ), Q(Φ) ≤ Q(Γ ), and S(Φ) ≤ S(Γ ). 2 Proof of Theorem 3 Proof. It follows directly from Theorems 1 and 2 and Lemma 3. First, by Lemma 3 and Theorem 2 we get that the best (lowest) cost measures of DAG scheme Γ are achieved when G is a forest F of at most k trees. In this case, since these trees are minimum combined cost trees, the update, query and sibling cost of G are defined by tree T ∗ ∈ F having the maximum complexity in terms of sibling cost. Moreover, this cost measure depends of the number of source nodes Vso (T ∗ ) of T ∗ . We know that |Vso (T ∗ )| is Ω( nk ). If Φ = (F, SF , n, `), ` ≤ k, is the DAG scheme of Lemma 3 and ∆ = (T ∗ , S, |Vso (T ∗ )|, 1) is the DAG scheme that corresponds to tree T ∗ , we have that S(Γ ) ≥ S(Φ) = S(∆), which from Theorems 1 is Ω(log nk ). By Lemma 1 we get also that U(Γ ) is Ω( nk ) and that Q(Γ ) is Ω( nk ). 2 Proof of Theorem 4 Proof. We use a worst case scenario, assuming that the skip-list has infinite size to the left or right direction, and thus compute upper bounds of the expected values of random variables related to our analysis. For any of the structural metrics we use a backward analysis as in [25, 26]. Given a skip-list, we consider the corresponding skip-list data structure storing a totally ordered set X of size n and we consider traveling backwards on the search path π for element x stored at source node s. Given the way with which DAG nodes of T are assigned to list nodes of the skip-list, the associated path πs in T is contained in path π. So, as we travel backwards (starting from s) along the search path π, we compute the structural metrics size(πs ), indeg(πs ) and bnd(πs ) of path πs in T . Assuming a worst case scenario, where π reaches level log p1 n in skip-list, we split π in two subpaths π1 and π2 : π1 takes us to level log p1 n and π completes the backward search up to the first skip-list node of π. Accordingly, in our analysis we partition πs into subpaths πs1 and πs2 corresponding to subpaths π1 and respectively π2 of π. Obviously, since πs = πs1 ∪ πs2 , size(πs ) = size(πs1 ) + size(πs2 ), indeg(πs ) = indeg(πs1 ) + indeg(πs2 ) and bnd(πs ) = bnd(πs1 ) + bnd(πs2 ). The node, degree and boundary sizes of πs2 are all on average constant, because the skip-list size (number of list nodes) above level log p1 n is on average constant [25]. (i) For the node size of πs1 , let Ck (t) be a random variable counting the node size size(π) computed so far when k upwards moves remain to be taken in π1 and we are performing the t-th step. Then if t+1 we move up Ckt = XU + Ck−1 , otherwise Ckt = XL + Ckt+1 , where XU , XL are 0-1 random variables that count if a DAG-node is encountered when moving up or left respectively. We have that Pr[XU = 1] = p(1 − p), because with probability 1 − p the node that the forward pointer points to is a plateau node and with probability p the node that we move to is not a plateau node (i.e., we count a DAGnode created by applying operation N ew(·)). Also we have that Pr[XL = 1] = p + p(1 − p), because with probability p we left a bridge and with probability (1 − p) the bridge has size more that one (i.e., we count a node created by operation N ew(·) and possibly a bridge DAG node). Observe that we count DAG nodes of bridges of size 1 when moving up. Since we have an infinite skip list, Ckt ∼ Ckt+i ∼ Ck for any i > 0, where Ck is a random variable distributed as Ckt . Thus, using conditional expectation we get that E[Ck ] = E[p(XU + Ck−1 ) + (1 − p)(XL + Ck )] = p(E[XU ] + E[Ck−1 ]) + (1 − p)(E[XL ] + E[Ck ]), thus E[Ck ] = E[Ck−1 ] + 2(1 − p). Finally we get that E[Ck ] = 2(1 − p)k. But E[size(πs1 )] ≤ E[Ck ] for k = log p1 n, thus E[size(πs )] = E[size(πs1 )] + E[size(πs2 )] ≤ 2(1 − p) log p1 n + O(1). (ii) Similarly, for the degree size of πs1 , let Ck (t) be a random variable counting the degree size indeg(π) so far, when k upwards moves remain to be taken and we are performing the t-th step. Then if we move t+1 up Ckt = XU + Ck−1 , otherwise Ckt = XL + Ckt+1 . Here XU and XL are random variables that count the number of predecessor DAG nodes that we have to add when moving up or left respectively. We have that E[XU ] = 2p(1 − p) because with probability p(1 − p) we count two predecessors after moving up (a node 2 created by operation N ew(·) has in-degree two). Also E[XL ] = p(2 + 1−p p ), because with probability p we have just left a bridge moving left and, thus, we count 2 + Y predecessors, i.e., two predecessor of a node created by operation N ew(·) and Y predecessors (a random variable) of a possible bridge DAG node. 1−p2 Observe that Y = 0 unless the bridge has size at least 2 and we compute E[Y ] = (1 − p)(2 + 1−p p ) = p . 2 1 Using conditional expectation as above, we finally get E[indeg(πs )] ≤ (1 − p)(2p + 2 + 1−p p ) log p n + O(1) = 2 (1 − p) (1+p) log p1 n + O(1). p (iii) For the boundary size of πs1 , let Ck (t) be a random variable counting the degree size bnd(π) counted t+1 so far, defined as above. If we move up Ckt = XU + Ck−1 , otherwise Ckt = XL + Ckt+1 , where XU and XL are random variables that count the number of sibling nodes of DAG nodes in πs1 that we have to add when moving up or left respectively. We have that E[XU ] = p(1 − p) because with probability p(1 − p) we count one sibling DAG node after moving up (a node created by operation N ew(·) has in-degree two: one node is in ps and one is a sibling node). Also E[XL ] = p(1 + 1−p p ) = 1, because with probability p we have just left a bridge moving left and, thus, we count 1 + Y sibling nodes, one sibling of the node created by operation N ew(·) and Y siblings (a random variable) corresponding to the possible bridge DAG node that we just 1−p left. We have that E[Y ] = (1 − p)(1 + 1−p p ) = p . Using conditional expectation as before, we finally get 2 1 E[bnd(πs )] ≤ (1 − p)( 1+p p ) log p n + O(1). (iv) By construction, VT = Vso (T ) ∪ B ∪ N , where Vso (T ) is the set of the n source nodes in T , B the set of bridge DAG nodes and N the set of the non-source, non-bridge, DAG nodes (created by operation N ew(·) or being predecessors of a DAG node of a bridge). Let B1 denote the set of DAG nodes in B that are assigned to list-nodes of level 1 and let B>1 = B − B1 . Similarly, let N1 denote the set of DAG nodes in N that are assigned to list-nodes of level 1 and let N>1 = N − N1 . We can compute that E[|B1 |] ≤ p(1 − p)2 n using the union bound, since with probability p(1 − p)2 the lowest plateau tower of a tower is the left most tower of a bridge of level 1 and of size at least two. Similarly, we can compute that E[|N1 |] ≤ p(1 − p)n, again by applying the union bound and noticing that with probability p(1 − p) a non-source DAG node is created by operation N ew(·). Now, let M denote the set of list nodes in the skip-list that have not been assigned a DAG node, which we call empty nodes, then for the set K>1 of list nodes in the skip-list of level 2 or more, we have that K>1 = M ∪ B>1 ∪ N>1 , where in this formula DAG nodes are treated like the list nodes they are assigned to. We next pair up DAG nodes in B>1 ∪ N>1 to distinct empty list nodes in M . Nodes in B>1 are paired up with probability 1. Consider any node u in B>1 corresponding to bridge b, with |b| ≥ 2. Node u can be paired with any of the empty list nodes of the top level of b. Any DAG node u in B>1 corresponding to bridge b, with |b| = 1, can be paired with the empty list node one level up in its tower. Any DAG node u in N>1 can be paired up with the empty list node l(u) on its left, if it not paired with a node in B>1 . The probability that u can not be paired up with l(u) is λ = p(1 − p)2 (l(u) is the top-right node of a bridge of size 2), an independent event from any other node in N>1 not being paired up with its empty node of the left. Thus, we have that, if M = M1 ∪ M2 ∪ M3 , where M1 , M2 , M3 are disjoint sets containing the empty nodes paired up with nodes in B>1 , in N>1 and respectively with no DAG nodes, then E[|M1 |] = E[|B>1 |] and E[|M2 | = (1 − λ)E[|N>1 |]]. Using this, we get that E[|K>1 |] = 2E[|B>1 |] + (2 − λ)E[|N>1 |] + E[|M3 |] >1 ] and the bound E[|B>1 |] + E[|N>1 |] ≤ E[K 2−λ . Putting all together, we finally get the upper bound for n E[size(T )] = E[|VT |]. Note that E[size(T )] < 1−p , the expected size of a skip-list. 2 r DAG T Fig. 2. The skip-list DAG ∆ = (T, r, n, 1) of a skip-list. T is a directed tree. Fig. 3. The DAG scheme ∆ of an improved version (w.r.t. number of comparisons) of standard skip list [26]. Proof of Lemma 4 Proof. The generic model uses compression function f (z, y) that maps a string z of N bits and a string y of B bits to an output string of N bits. The input string x is preprocessed using some padding rule into a string y whose length is a multiple of B. Let y = y1 ky2 k...kyk , where each yi has length B and let z0 be a public initial value of N bits. Then h(x) = zk , where zk is given by the following iterative application of function f : z1 = f (z0 , y1 ), z2 = f (z1 , y2 ), . . . , zk = f (zk−1 , yk ). Accordingly, the computational time is linear on |x| = `, expressed as T (`) = c1 ` + c2 , where constants c1 and c2 depend on the compression function f and the pudding rule respectively. Note that since constant c1 depends on the compression function f in use, it may depend also on some security parameter k. Still, the dependency of the hashing time on the input length is linear. This is a very general assumption that holds for any collision resistant function. For instance, for hash functions based on block ciphers or on algebraic structures and modular arithmetic (e.g. based on discrete logarithm using Pedersen’s commitment scheme) or custom designed hash function (e.g, SHA-1). 2 Proof of Lemma 6 Proof. For an update operation (insert or delete) on an element at source node s in G, the hash values stored in the nodes of the reachable from s subgraph Gs of G need to be updated. Updating the hash value of node u of Gs using the concatenation multivariate hash function (Lemma 5 justifies this choice) takes time c1 indeg(u) + c2 (Lemma 4), thus the update operation is performed hierarchically in time c1 indeg(Gs ) + c2 size(Gs ), which is Ω(comb(Gs )) . For a query operation exists the query element is first located in X and suppose it is found in X. Without loss of generality we consider only positive answers (standard techniques to authenticate negative answers have similar authentication overhead). Providing the proof to the user involves collecting a set of hash values that can be used to recompute a data digest. For this reason, a path of minimum authentication cost from source node s storing the query element is found and this path is exactly the associated path πs of s, the minimum combined size path from s to a signature node. Regarding the size of proof that is sent to the user, we note that in order the user to compute the hash value that is stored at node u of G, exactly indeg(u) − 1 hash values need to be sent by the directory. Thus the proof consists of bnd(πs ) labels and the communication overhead is Ω(bnd(πs )). In addition, the user verifies this proof by hierarchically hashing the hash values of the proof along path πs in time c1 indeg(πs ) + c2 size(πs ), which is Ω(comb(Gs )). Finally, for the storage overhead, clearly size(G) hash values are stored in the data structure at the source and the directory. 2 Proof of Lemma 7 Proof. For updating the size(Gs ) keys, the controlled traverses graph Gs in a bottom-up fashion. At a node u of Gs , using the keys stored at the predecessors of u in G that do not belong in Gs (i.e., stored at sibling nodes), a new key for u is encrypted and the corresponding message is sent to the users. The new distributed keys are further used to encrypt new keys in Gs that lie higher in the hierarchy of G. At each node u of Gs , exactly indeg(u) messages are sent: for each predecessor node v of u, message Ekv (ku ), where E(·) is the encryption algorithm and kv is the (possibly new) key corresponding to v and ku is the new key corresponding to v. The encryption cost is proportional to indeg(u) + 1, since one new key (ku ) is created additionally to the applications of encryption function E(·) indeg(u) times. Obviously, indeg(u) messages are sent. 2 Proof Sketch of Corollary 1 Proof Sketch. First observe that multiple encryptions do not affect encryption and decryption costs. With respect to communication cost, in key-trees, multiple encryptions do not help. For general graphs, multiple encryptions can be used to reduce the communication cost for updating the keys that are the intersection of the keys that two or more subgroups (subset of users) possess. Every multiple encryption of depth k saves k − 1 messages. However, when updating the keys of Gs , only keys that are the union of keys that subgroups possess need to be updated. On the other hand, since all keys need to be distinct, the use of pseudorandom generators can only affect source-to-sink subgraphs Gs of G by reducing communication cost from indeg(Gs ) to bnd(Gs ) = indeg(Gs ) − size(Gs ). But our lower bounds are proved by studying exactly the sibling cost of DAG schemes. 2