Cryptology ePrint Archive: Report 2010/374

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

Zhen Liu and 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.

Category / Keywords: Attribute-Based Encryption, Access Policy, Monotone Access Structure, Linear Secret Sharing Scheme

Date: received 29 Jun 2010, last revised 28 Dec 2014

Contact author: liuzhen sjtu at gmail com, zfcao@sei ecnu edu cn, duncan@cityu edu hk

Available format(s): PDF | BibTeX Citation

Version: 20141228:131745 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]