Abstract
We present and analyze portable access control mechanisms for large data repositories, in that the customized access policies are stored on a portable device (e.g., a smart card). While there are significant privacy-preservation advantages to the use of smart cards anonymously created and bought in public places (stores, libraries, etc), a major difficulty is that, for huge data repositories and limited-capacity portable storage devices, it is not possible to represent any possible access configuration on the card. If we let n denote the number of documents on a server, then we need to design succinct descriptions of portable access rights to arbitrary subsets of these n documents, such as they "fit" in only k available space, where k is much smaller than n. We describe and analyze schemes for both unstructured and structured collections of documents. For these schemes, we give fast algorithms for efficiently using the limited space available on the card. For a customer whose card is supposed to contain a subset S of documents, access to all of S must be allowed. In some situations a small enough number of "false positives" (which are accesses to non-S documents) is acceptable to the server, and the challenge then is to minimize the number of false positives implicit to any given card. In our model the customer does not know which documents correspond to those false positives, the probability of a randomly chosen document being a false positive is small, and too many unsuccessful access attempts are viewed by the server as an exhaustive search attack, which can possibly result in zero-ing out the card.
Recent related work by Bykova and Atallah was geared towards the situation where the document repository and/or access policies change rapidly, and are therefore not vulnerable to on-line sharing of false-positive experiences by different users. In this paper we seek to prevent such collusive attacks by different card holders: It is a design requirement that the information in one card is useless to the holder of another card; that is, even if two customers have the same S, they would not have the same set of false positives.
