Succinct Specifications of Portable Document Access Policies

Get BibTex-formatted data

Download

PDF

Author

Marina Bykova, Mikhail Atallah

Tech report number

CERIAS TR 2004-19

Entry type

inproceedings

Abstract

When customers need to each be given portable access rights to a subset of documents from a large universe of n available documents, it is often the case that the space available for representing each customer's access rights is limited to much less than n, say it is no more than m bits. This is the case when, e.g., limited-capacity inexpensive cards are used to store the access rights to huge multimedia document databases. How does one represent subsets of a huge set of n elements, when only m bits are available and m is much smaller than n? We use an approach reminiscent of Bloom filters, by assigning to each document a subset of the m bits: If that document is in a customer's subset then we set the corresponding bits to 1 on the customer's card. This guarantees that each customer gets the documents he paid for, but it also gives him access to documents he did not pay for ("false positives"). We want to do so in a manner that minimizes the expected total false positives under various deterministic and probabilistic models: In the former model we assume k customers whose respective subsets are known a priori, whereas in the latter we assume (more realistically) that each document has a probability of being included in a customer's subset. We cannot use randomly assigned bits for each document (in the way Bloom filters do), rather we need to consider the a priori knowledge (deterministic or probabilistic) we are given in each model in order to better assign a subset of the m available bits to each of the n documents. We analyze and give efficient schemes for this problem.

Download

PDF

Date

2004 – 06

Booktitle

Symposium on Access Control Models and Technologies (SACMAT)

Key alpha

Bykova

Note

SACMAT'04 is taking place in Yorktown Heights, New York, USA, on June 2-4, 2004.

Organization

ACM

Publisher

ACM Press

Affiliation

Purdue University

Publication Date

2004-06-01

Copyright

ACM 1-58113-872-5/04/0006

Isbn

1-58113-872-5

Keywords

Portable access rights, compact policy representation, access control, access control enforcement, algorithm design, computational complexity

Language

English

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ Bykova,
	title = "Succinct Specifications of Portable Document Access Policies",
	author = "Marina Bykova, Mikhail Atallah",
	year = "2004",
	month = "06",
	booktitle = "Symposium on Access Control Models and Technologies (SACMAT)",
	note = "SACMAT'04 is taking place in Yorktown Heights, New York, USA, on June 2-4, 2004.",
	organization = "ACM",
	publisher = "ACM Press",
	abstract = "When customers need to each be given portable access rights to a subset of documents from a large universe of n available documents, it is often the case that the space available for representing each customer's access rights is limited to much less than n, say it is no more than m bits. This is the case when, e.g., limited-capacity inexpensive cards are used to store the access rights to huge multimedia document databases. How does one represent subsets of a huge set of n elements, when only m bits are available and m is much smaller than n? We use an approach reminiscent of Bloom filters, by assigning to each document a subset of the m bits: If that document is in a customer's subset then we set the corresponding bits to 1 on the customer's card.  This guarantees that each customer gets the documents he paid for, but it also gives him access to documents he did not pay for ("false positives").  We want to do so in a manner that minimizes the expected total false positives under various deterministic and probabilistic models: In the former model we assume k customers whose respective subsets are known a priori, whereas in the latter we assume (more realistically) that each document has a probability of being included in a customer's subset. We cannot use randomly assigned bits for each document (in the way Bloom filters do), rather we need to consider the a priori knowledge (deterministic or probabilistic) we are given in each model in order to better assign a subset of the m available bits to each of the n documents. We analyze and give efficient schemes for this problem.",
	affiliation = "Purdue University",
	copyright = "ACM 1-58113-872-5/04/0006",
	isbn = "1-58113-872-5",
	keywords = "Portable access rights, compact policy representation, access control, access control enforcement, algorithm design, computational complexity",
	language = "English",
}