Paper 2010/374

Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees

Zhen Liu, Zhenfu Cao, and Duncan S. Wong

Abstract

Linear Secret Sharing Scheme (LSSS) matrices are commonly used for implementing monotone access structures in highly expressive Ciphertext-Policy Attribute-Based Encryption (CP-ABE) schemes. However, LSSS matrices are much less intuitive to use when compared with other approaches such as boolean formulas or access trees. To bridge the gap between the usability of an access structure representation method and the implementation technique required in a concrete CP-ABE construction, Lewko and Waters proposed an algorithm which can convert any monotone boolean formulas to LSSS matrices. This algorithm is very useful in practice as a ciphertext policy can now be intuitively expressed using a monotone boolean formula, which has good usability, and the corresponding LSSS for an actual CP-ABE construction can then be generated accordingly using this algorithm. However, in this algorithm, the non-leaf nodes of a monotone boolean formula, when viewed as an access tree, can only be \textsf{AND} or \textsf{OR} gates. For general monotone access structures, for example, in a $(t, n)$-threshold access tree, the threshold gates of the tree have to be converted to \textsf{AND} and \textsf{OR} gates before we can apply the algorithm on this access tree. This results in generating a large LSSS matrix, and entailing a large CP-ABE ciphertext. To address this problem, in this paper, we propose a new algorithm which, in addition to \textsf{AND} and \textsf{OR} gates, can directly support threshold gates, and obtain much smaller LSSS matrices (or the same in the worst case when only \textsf{AND} and \textsf{OR} gates exist). This will particularly be useful for reducing the size of all ciphertexts with policies in the typical $(t, n)$-threshold type. Furthermore, as \textsf{AND} and \textsf{OR} gates are the special cases of the general $(t, n)$-threshold gates, not only an optimization, but also is this new algorithm a generalization of the Lewko-Waters algorithm.