Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Resilient Delegation Revocation with Precedence for Predecessors is NP-Complete
Cramer, Marcos; Van Hertum, Pieter; Lapauw, Ruben et al.
2016In IEEE 29th Computer Security Foundations Symposium
Peer reviewed
 

Files


Full Text
NP-complete_IEEE.pdf
Author postprint (217.71 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
access control; delegation; revocation; resilience; negative authorization; denial; predecessor takes precedence; complexity
Abstract :
[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.
Research center :
SnT
Disciplines :
Computer science
Author, co-author :
Cramer, Marcos ;  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
External co-authors :
yes
Language :
English
Title :
Resilient Delegation Revocation with Precedence for Predecessors is NP-Complete
Publication date :
2016
Event name :
Computer Security Foundations Symposium
Event place :
Lisbon, Portugal
Event date :
from 27-06-2016 to 01-07-2016
Audience :
International
Main work title :
IEEE 29th Computer Security Foundations Symposium
Pages :
432-442
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
FnR Project :
FNR4758104 - Specification Logics And Inference Tools For Verification And Enforcement Of Policies, 2011 (01/06/2012-30/04/2017) - Leon Van Der Torre
Name of the research project :
Specification logics and Inference tools for verification and Enforcement of Policies
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 15 March 2017

Statistics


Number of views
51 (0 by Unilu)
Number of downloads
127 (1 by Unilu)

Scopus citations®
 
2
Scopus citations®
without self-citations
0
WoS citations
 
1

Bibliography


Similar publications



Contact ORBilu