Efficient integer span program for hierarchical threshold access structure

• We propose an efficient integer span program that realizes the hierarchical threshold access structure.
• Our construction is the first efficient one for non-threshold access structure, to the best knowledge of the authors.
• Some efficient non-threshold black-box secret sharing schemes and linear integer secret sharing schemes can be constructed by our construction.

Integer span program (ISP) is a monotone span program (MSP) over ZZ, which is introduced by Cramer and Fehr in CRYPTO 2002. ISP can be used to construct black-box secret sharing scheme (BBSSS) and linear integer secret sharing scheme (LISSS). The efficiency of ISPs is a very important research objective, as efficient ISP can be used to construct efficient BBSSS and efficient LISSS. Until now, only efficient ISPs that realize threshold access structure have been constructed, but not efficient ISPs realizing other access structures. The main contribution of this paper is that we propose an efficient ISP that realizes the hierarchical threshold access structure, to the best knowledge of the authors, which is the first efficient one for non-threshold access structure. Accordingly, with the proposed construction of efficient ISP realizing hierarchical threshold access structure, the construction of efficient non-threshold BBSSSs and LISSSs for a useful family of access structures is presented.