|
Published Articles >> Table of Contents >> Abstract
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
pp. 127-136
Managing Digital Rights using Linear Logic
Adam Barth, Stanford University, USA
John C. Mitchell, Stanford University, USA
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.32
Send link to a friend
| Abstract |
|
Digital music players protect songs by enforcing licenses
that convey specific rights for individual songs or groups
of songs. For licenses specified in industry, we show that
deciding whether a license authorizes a sequence of actions
is NP-complete, with a restricted version of the problem
solvable efficiently using a reduction to maximum network
flow. The authorization algorithm used in industry
is online, deciding which rights to exercise as actions occur,
but we show that all online algorithms are necessarily
non-monotonic: each allows actions under one license
that it does not allow under a more flexible license. In one
approach to achieving monotonicity, we exhibit the unique
maximal set of licenses on which there exists a monotonic
online algorithm. This set of well-behaved licenses induces
an approximation algorithm by replacing each license with
a well-behaved license. In a second approach, we consider
allowing the player to revise its past decisions about which
rights to exercise while still ensuring compliance with the
license. We propose an efficient algorithm based on Linear
Logic, with linear negation used to revise past decisions.
We prove our algorithm monotonic, live, and sound with respect
to the semantics of licenses.
|
 Additional Information
|
Citation:
Adam Barth, John C. Mitchell,
"Managing Digital Rights using Linear Logic,"
lics,
pp. 127-136,
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06),
2006
|
|
