Cloud computing services are becoming more prevalent and readily available today, bringing to us economies of scale and making large-scale computation feasible. Security and privacy considerations, however, stand in the way of fully utilizing the benefits of such services and architectures. In this work we address the problem of secure outsourcing of large-scale biometric experiments to a cloud or grid in a way that the client can verify that with very high probability the task was computed correctly. We conduct thorough theoretical analysis of the proposed techniques and provide implementation results that indicate that our solution imposes modest overhead.

Sensor networks have the potential to allow users to “query the physical world” by querying the sensor nodes for an aggregate result. However, a concern with such aggregation is that a few corrupt nodes in the network may manipulate the results that the querier sees. There has been a substantial amount of work on providing integrity for sensor network computations. However to the best of our knowledge, this prior work has one or more of the following two limitations: i) the methods only work for a specific aggregation function, or ii) the methods do not consider adversaries whose goal is to prevent the base station and the querier from receiving the result. In this paper we present the first scheme that provides general aggregation for sensor networks in the presence of malicious adversaries. The generality of the scheme results from the ability to securely evaluate any algorithm in the streaming model of computation. The main idea of this paper is to convert the commonly used aggregation tree into an aggregation list, and a process for doing this conversion is also presented. This result is an interesting and important first step towards achieving the realization of general secure querying of a sensor network.

We give improved protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of large matrices) to a remote server, such that the server learns nothing about the customer's private input or the result of the computation, and any attempted corruption of the answer by the server is detected with high probability. The computational work performed at the client is linear in the size of its input and does not require the client to locally carry out any expensive encryptions of such input. The computational burden on the server is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3 for multiplying two n x n matrices). The improvements we give are: (i) whereas the previous work required more than one remote server and assumed they do not collude, our solution works with a single server (but readily accommodates many, for improved performance); (ii) whereas the previous work required a server to carry out expensive cryptographic computations (e.g., homomorphic encryptions), our solution does not make use of any such expensive cryptographic primitives; and (iii) whereas in previous work collusion by the servers against the client revealed to them the client's inputs, our scheme is resistant to such collusion. As in previous work, we maintain the property that the scheme enables the client to detect any attempt by the server(s) at corruption of the answer, even when the attempt is collusive and coordinated among the servers.

Hierarchies arise in the context of access control whenever the user population can be modeled as a set of partially ordered classes (represented as a directed graph). A user with access privileges for a class obtains access to objects stored at that class and all descendant classes in the hierarchy. The problem of key management for such hierarchies then consists of assigning a key to each class in the hierarchy so that keys for descendant classes can be obtained via efficient key derivation. We propose a solution to this problem with the following properties: (1) the space complexity of the public information is the same as that of storing the hierarchy; (2) the private information at a class consists of a single key associated with that class; (3) updates (i.e., revocations and additions) are handled locally in the hierarchy; (4) the scheme is provably secure against collusion; and (5) each node can derive the key of any of its descendant with a number of symmetric-key operations bounded by the length of the path between the nodes. Whereas many previous schemes had some of these properties, ours is the first that satisfies all of them. The security of our scheme is based on pseudorandom functions, without reliance on the Random Oracle Model. Another substantial contribution of this work is that we are able to lower the key derivation time at the expense of modestly increasing the public storage associated with the hierarchy. Insertion of additional, so-called shortcut, edges, allows to lower the key derivation to a small constant number of steps for graphs that are total orders and trees by increasing the total number of edges by a small asymptotic factor such as O (log * n ) for an n -node hierarchy. For more general access hierarchies of dimension d , we use a technique that consists of adding dummy nodes and dimension reduction. The key derivation work for such graphs is then linear in d and the increase in the number of edges is by the factor O (log d − 1 n ) compared to the one-dimensional case. Finally, by making simple modifications to our scheme, we show how to handle extensions proposed by Crampton [2003] of the standard hierarchies to “limited depth” and reverse inheritance.

Combinatorial group testing, given a set C of individuals ("customers"), consists of applying group tests on subsets of C for the purpose of identifying which members of C are infected (or, more generally, defective in some way). The outcome of a group test reveals only the presence or absence of infection(s) in that group, but a number of group tests exactly identifies all infected members.

Sensor networks have proven to be useful in many application domains. Having the sensor nodes aggregate their results inside the network before sending the results to a base station has been shown to increase the lifetime of the network. However, sensor networks that are deployed in hostile environments need aggregation protocols that protect the integrity of the result. Recently, Chan et al. [3] introduced such a scheme that requires O(Δlog2n) communication per node, where Δ$ is the degree of the aggregation tree for the network and n is the number of nodes in the network. In this paper, we introduce modifications of this approach that reduce the maximum communication per node to O(Δlog2n).

This article studies the notion of quantitative policies for trust management and gives protocols for realizing them in a disclosure-minimizing fashion. Specifically, Bob values each credential with a certain number of points, and requires a minimum total threshold of points before granting Alice access to a resource. In turn, Alice values each of her credentials with a privacy score that indicates her degree of reluctance to reveal that credential. Bob's valuation of credentials and his threshold are private. Alice's privacy-valuation of her credentials is also private. Alice wants to find a subset of her credentials that achieves Bob's required threshold for access, yet is of as small a value to her as possible. We give protocols for computing such a subset of Alice's credentials without revealing any of the two parties' above-mentioned private information. Furthermore, we develop a fingerprint method that allows Alice to independently and easily recover the optimal knapsack solution, once the computed optimal value is given, but also enables verification of the integrity of the optimal value. The fingerprint method is useful beyond the specific authorization problem studied, and can be applied to any integer knapsack dynamic programming in a private setting.

The problem of key management for access control systems has been well-studied, and the literature contains several schemes for hierarchy-based and temporal-based access control. The problem of key management in such systems is how to assign keys to users such that each user is able to compute and have access to the appropriate resources while minimizing computation and storage requirements. In the current paper, we consider key management schemes for geo-spatial access control. That is, the access control policy assigns to a user a specific geographic area, and the user consequently obtains access to her area or information about it.In this work, the geography is modeled as an m × n grid of cells (let m ≥ n). Each cell has its own key associated with it, and a user who wants to access the content of a cell needs to obtain its key. Each user obtains access to a rectangular area (or a finite collection of such rectangles) and is able compute keys corresponding to the cells that comprise her area.Our main result is an efficient scheme with the following properties: (i) each user obtains a small constant number of secret keys that permit access to an arbitrary rectangular sub-grid, (ii) computation to derive the key of a specific cell in that rectangle consists of a constant number of efficient operations, and (iii) the server needs to maintain O(mn(log log m)2 log* m) public information accessible to all users. The public storage requirement is the worst-case bound and can be improved if the grid is partitioned into regions where the cells of a region share the same key.

Access hierarchies are useful in many applications and are modeled as a set of access classes organized by a partial order. A user who obtains access to a class in such a hierarchy is entitled to access objects stored at that class, as well as objects stored at its descendant classes. Efficient schemes for this framework assign only one key to a class and use key derivation to permit access to descendant classes. Ideally, the key derivation uses simple primitives such as cryptographic hash computations and modular additions. A straightforward key derivation time is then linear in the length of the path between the user's class and the class of the object that the user wants to access. Recently, work presented in [2] has given an efficient solution that significantly lowers this key derivation time, while using only hash functions and modular additions. Two fastkey-derivation techniques in that paper were given for trees, achieving O(log log n) and O(1) key derivation times, respectively, where n is the number of access classes. The present paper presents efficient key derivation techniques for hierarchies that are not trees, using a scheme that is very different from the above-mentioned paper. The construction we give in the present paper is recursive and uses the onedimensional case solution as its base. It makes a novel use of the notion of the dimension d of an access graph, and provides a solution through which no key derivation requires more than 2d+1 hash function computations, even for "unbalanced" hierarchies whose depth is linear in their number of access classes n. The significance of this result is strengthened by the fact that many access graphs have a low d value (e.g., trees correspond to the case d = 2). Our scheme has the desirable property (as did [2] for trees) that addition and deletion of edges and nodes in the access hierarchy can be "contained".

In an open environment such as the Internet, the decision to collaborate with a stranger (e.g., by granting access to a resource) is often based on the characteristics (rather than the identity) of the requester, via digital credentials: access is granted if Alice's credentials satisfy Bob's access policy. The literature contains many scenarios in which it is desirable to carry out such trust negotiations in a privacy-preserving manner, i.e., so as minimize the disclosure of credentials and/or of access policies. Elegant solutions were proposed for achieving various degrees of privacy-preservation through minimal disclosure. In this paper, we present protocols that protect both sensitive credentials and sensitive policies. That is, Alice gets the resource only if she satisfies the policy, Bob does not learn anything about Alice's credentials (not even whether Alice got access), and Alice learns neither Bob's policy structure nor which credentials caused her to gain access. Our protocols are efficient in terms of communication and in rounds of interaction

The problem of key management in an access hierarchy has elicited much interest in the literature. The hierarchy is modeled as a set of partially ordered classes (represented as a directed graph), and a user who obtains access (i.e., a key) to a certain class can also obtain access to all descendant classes of her class through key derivation. Our solution to the above problem has the following properties: (i) only hash functions are used for a node to derive a descendant's key from its own key; (ii) the space complexity of the public information is the same as that of storing the hierarchy; (iii) the private information at a class consists of a single key associated with that class; (iv) updates (revocations, additions, etc.) are handled locally in the hierarchy; (v) the scheme is provably secure against collusion; and (vi) key derivation by a node of its descendant's key is bounded by the number of bit operations linear in the length of the path between the nodes. Whereas many previous schemes had some of these properties, ours is the first that satisfies all of them. Moreover, for trees (and other recursively decomposable hierarchies), we are the first to achieve a worst- and average-case number of bit operations for key derivation that is exponentially better than the of a balanced hierarchy (double-exponentially better if the hierarchy is unbalanced, i.e., tall and skinny); this is achieved with only a constant increase in the space for the hierarchy. We also show how with simple modifications our scheme can handle extensions proposed by Crampton of the standard hierarchies to limited depth and reverse inheritance [13]. The security of our scheme relies only on the use of pseudo-random functions.

Typically, when a borrower (Bob) wishes to establish a tradeline (e.g., a mortgage, an automobile loan, or a credit card) with a lender (Linda), Bob is subjected to a credit check by Linda. The credit check is done by having Linda obtain financial information about Bob in the form of a credit report. Credit reports are maintained by Credit Report Agencies, and contain a large amount of private information about individuals. Furthermore, Linda's criteria for loan qualification are also private information. We propose a "privacy-preserving" credit check scheme that allows Bob to have his credit checked without divulging private information to Linda while protecting Linda's interests. We give protocols for achieving the above while: i) protecting Bob's private information, ii) making sure that Bob cannot lie about his credit (thus Linda is assured that the information is accurate), iii) that Linda's qualification criteria are protected, and iv) that the CRA does not learn from the protocols anything other than "Bob requested a loan from Linda". What distinguishes this work from the traditional two-party privacy-preserving framework is (i) the need for secure and privacy-preserving third-party verification of the accuracy of the inputs used, and (ii) the fact that the function being computed is private to the lender and should not be revealed to either the borrower or to the above-mentioned third-party verifier. Although we choose to present the techniques of this paper for the credit checking application domain, they have much broader applicability and in fact work for any situation where there is a repository of public and private information about individuals, that is subsequently used for making decisions that impact the individuals (a credit rating agency is but one example of such a repository).