We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes in the literature that use symmetric cryptographic primitives, each user is assigned a single secret and derives decryption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on a chain partition of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. In general, many different chain partitions exist for the same policy and, until now, it was not known how to compute an appropriate one. In this paper, we introduce the notion of a tree partition, of which chain partitions are a special case. We show how a tree partition may be used to define a cryptographic enforcement scheme and prove that such schemes can be instantiated in such a way as to preserve the strongest security properties known for cryptographic enforcement schemes. We establish a number of results linking the amount of secret material that needs to be distributed to users with a weighted acyclic graph derived from the tree partition. These results enable us to develop efficient algorithms for deriving tree and chain partitions that minimize the amount of secret material that needs to be distributed.
In an edge-based scheme, public information is associated with each pair @math where @math from which @math can be extracted with knowledge of @math . Thus, informally, we might define @math to be @math , where @math is some symmetric encryption algorithm with key @math contained in @math . An edge-based scheme can be used for arbitrary posets but requires public information @cite_19 .
@cite_19
1982128483
For an unweighted graph @math , @math is a subgraph if @math , and @math is a Steiner graph if @math , and for any pair of vertices @math , the distance between them in @math (denoted @math ) is at least the distance between them in @math (denoted @math ). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) @math of a graph @math is a subgraph (resp., Steiner) @math -preserver of @math if for every pair of vertices @math with @math , @math . We show that any graph (resp., digraph) has a subgraph @math -preserver with at most @math edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner @math -preserver contains @math edges. However, we show that if one allows a directed Steiner (diSteiner) @math -preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner @math -preserver with @math arcs, and that this result is tight up to a constant factor. We also study @math -preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least @math one from another. We show that there exists a @math -preserving labeling scheme with labels of size @math , and that labels of size @math are required for any @math -preserving labeling scheme. We consider the multiple-unicast problem with three source–terminal pairs over directed acyclic networks with unit-capacity edges. The three @math pairs wish to communicate at unit-rate via network coding. The connectivity between the @math pairs is quantified by means of a connectivity-level vector, @math such that there exist @math edge-disjoint paths between @math and @math . In this paper, we attempt to classify networks based on the connectivity level. It can be observed that unit-rate transmission can be supported by routing if @math , for all @math . In this paper, we consider connectivity-level vectors such that $ i = 1, , 3 k_i . We present either a constructive linear network coding scheme or an instance of a network that cannot support the desired unit-rate requirement, for all such connectivity-level vectors except the vector [1 2 4] (and its permutations). The benefits of our schemes extend to networks with higher and potentially different edge capacities. Specifically, our experimental results indicate that for networks where the different source–terminal paths have a significant overlap, our constructive unit-rate schemes can be packed along with routing to provide higher throughput as compared to a pure routing approach. Let @math be a weighted undirected graph having nonnegative edge weights. An estimate @math of the actual distance @math between @math is said to be of stretch @math if and only if @math . Computing all-pairs small stretch distances efficiently (both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs @math -stretch distances for a whole range of stretch @math , and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24]. Given a large data matrix @math , we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution @math , or instead @math contains a principal submatrix @math whose entries have marginal distribution @math . As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided @math for a suitable constant @math . However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when @math . Recently Meka and Wigderson meka2013association , proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree- @math SOS relaxation, and study the construction of meka2013association to prove that SOS fails unless @math . An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erd "os-Renyi random graph.