2006/01/10 by Halpern, Joseph Y., Weissman, Vicky
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #H.2.7 #K.4.4 #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.cs/0601034
A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of (multi-sorted) first-order logic can be used to represent and reason about policies. Because we use first-order logic, policies have a clear syntax and semantics. We show that further restricting the fragment results in a language that is still quite expressive yet is also tractable. More precisely, questions about entailment, such as `May Alice access the file?', can be answered in time that is a low-order polynomial (indeed, almost linear in some cases), as can questions about the consistency of policy sets.