Affiliations: [a] Royal Holloway, University of London, UK | [b] Ruhr University Bochum, Germany
Correspondence:
[*]
Corresponding author: Jason Crampton, Information Security Group, Royal Holloway, University of London, Egham, TW20 9QY, UK. Tel.: +44 1784 443117; E-mail: jason.crampton@rhul.ac.uk.
Note: [1] This paper generalizes and extends our earlier results [in: Applied Cryptography and Network Security – 13th International Conference, ACNS 2015, Revised Selected Papers, Springer, 2015, pp. 389–408; in: Data and Applications Security and Privacy XXIX – 29th Annual IFIP WG 11.3 Working Conference, DBSec 2015, Proceedings, Springer, 2015, pp. 330–345]. In particular, we define a new form of enforcement scheme that subsumes chain-based [in: Data and Applications Security and Privacy XXIX – 29th Annual IFIP WG 11.3 Working Conference, DBSec 2015, Proceedings, Springer, 2015, pp. 330–345] and tree-based enforcement schemes [in: Applied Cryptography and Network Security – 13th International Conference, ACNS 2015, Revised Selected Papers, Springer, 2015, pp. 389–408]. We generalize results specific to these earlier schemes in order to support our more general framework.
Abstract: We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes in the literature that use symmetric cryptographic primitives, each user is assigned a single secret and derives decryption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on a chain partition of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. In general, many different chain partitions exist for the same policy and, until now, it was not known how to compute an appropriate one. In this paper, we introduce the notion of a tree partition, of which chain partitions are a special case. We show how a tree partition may be used to define a cryptographic enforcement scheme and prove that such schemes can be instantiated in such a way as to preserve the strongest security properties known for cryptographic enforcement schemes. We establish a number of results linking the amount of secret material that needs to be distributed to users with a weighted acyclic graph derived from the tree partition. These results enable us to develop efficient algorithms for deriving tree and chain partitions that minimize the total amount of secret material that needs to be distributed.
Keywords: Access control, information flow policies, cryptographic enforcement, chains, forests, trees
