Reference : Resilient Delegation Revocation with Precedence for Predecessors is NP-Complete
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Computational Sciences
Resilient Delegation Revocation with Precedence for Predecessors is NP-Complete
Cramer, Marcos mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Van Hertum, Pieter []
Lapauw, Ruben []
Dasseville, Ingmar []
Denecker, Marc []
IEEE 29th Computer Security Foundations Symposium
Computer Security Foundations Symposium
from 27-06-2016 to 01-07-2016
[en] access control ; delegation ; revocation ; resilience ; negative authorization ; denial ; predecessor takes precedence ; complexity
[en] In ownership-based access control frameworks with the possibility of delegating permissions and administrative rights, chains of delegated accesses will form. There are different ways to treat these delegation chains when revoking rights, which give rise to different revocation schemes. One possibility studied in the literature is to revoke rights by issuing negative authorizations, meant to ensure that the revocation is resilient to a later reissuing of the rights, and to resolve conflicts between principals by giving precedence to predecessors, i.e.\ principals that come earlier in the delegation chain.
However, the effects of negative authorizations have been defined differently by different authors. Having identified three definitions of this effect from the literature, the first contribution of this paper is to point out that two of these three definitions pose a security threat. However, avoiding this security threat comes at a price: We prove that with the safe definition of the effect of negative authorizations, deciding whether a principal does have access to a resource is an NP-complete decision problem. We discuss two limitations that can be imposed on an access-control system in order to reduce the complexity of the problem back to a polynomial complexity: Limiting the length of delegation chains to an integer m reduces the runtime complexity of determining access to O(n^m), and requiring that principals form a hierarchy that graph-theoretically forms a rooted tree makes this decision problem solvable in quadratic runtime. Finally we discuss an approach that can mitigate the complexity problem in practice without fully getting rid of NP-completeness.
Fonds National de la Recherche - FnR
Researchers ; Students
FnR ; FNR4758104 > Leon Van Der Torre > SIEP > Specification logics and Inference tools for verification and Enforcement of Policies > 01/06/2012 > 30/04/2017 > 2011

File(s) associated to this reference

Fulltext file(s):

Open access
NP-complete_IEEE.pdfAuthor postprint212.61 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.