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. 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. 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. In our model the customer does not know which documents correspond to false positives, the probability of a randomly chosen document being a false positive is small, and information about false positives bound to one card is useless for any other card even if both of them permit access to the same set of documents S.
