Variations on a theme by Akl and Taylor: Security and tradeoffs

In 1983, AM and Taylor [Cryptographic solution to a problem of access control in a hierarchy, ACM Transactions on Computer Systems 1 (3) (1983) 239-248] first suggested the use of cryptographic techniques to enforce access control in hierarchical structures. Due to its simplicity and versatility, the scheme has been used, for more than twenty years, to implement access control in several different domains, including mobile agent environments and XML documents. However, despite its use over time, the scheme has never been fully analyzed with respect to security and efficiency requirements. In this paper we provide new results on the Akl-Taylor scheme and its variants. More precisely: We provide a rigorous analysis of the Akl-Taylor scheme. We consider different key assignment strategies and prove that the corresponding schemes are secure against key recovery. We show how to obtain different tradeoffs between the amount of public information and the number of steps required to perform key derivation in the proposed schemes. We also look at the MacKinnon et al. and Harn and Lin schemes and prove they are secure against key recovery. We describe an Akl-Taylor based key assignment scheme with time-dependent constraints and prove the scheme efficient, flexible and secure. We propose a general construction, which is of independent interest, yielding a key assignment scheme offering security w.r.t. key indistinguishability, given any key assignment scheme which guarantees security against key recovery. Finally, we show how to use our construction, along with our assignment strategies and tradeoffs, to obtain an Akl-Taylor scheme, secure w.r.t. key indistinguishability, requiring a constant amount of public information. (C) 2009 Elsevier B.V. All rights reserved