Paper 2020/1612

A New Efficient Hierarchical Multi-secret Sharing Scheme Based on Linear Homogeneous Recurrence Relations

Jiangtao Yuan, Jing Yang, Guoai Xu, Xingxing Jia, Fang-wei Fu, and Chenyu Wang


Hierarchical secret sharing is an important key management technique since it is specially customized for hierarchical organizations with different departments allocated with different privileges, such as the government agencies or companies. Hierarchical access structures have been widely adopted in secret sharing schemes, where efficiency is the primary consideration for various applications. How to design an efficient hierarchical secret sharing scheme is an important issue. In 2007, a famous hierarchical secret sharing (HSS) scheme was proposed by Tassa based on Birkhoff interpolation, and later, based on the same method, many other HSS schemes were proposed. However, these schemes all depend on Polya's condition, which is a necessary condition not a sufficient condition. It cannot guarantee that Tassa's HSS scheme always exists. Furthermore, this condition needs to check the non-singularity of many matrices. We propose a hierarchical multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations and the one-way function. In our scheme, we select $m$ linearly independent homogeneous recurrence relations. The participants in the highly-ranked subsets $\gamma_1, \gamma_2 ,\cdots, \gamma_{j-1}$ join in the $j$-th subset to construct the $j$-th LHR relation. In addition, the proposed hierarchical multi-secret sharing scheme just requires one share for each participant, and keeps the same computational complexity. Compared with the state-of-the-art hierarchical secret sharing schemes, our scheme has high efficiency.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Hierarchical access structurelinear homogeneous recurrence relationssecret sharing schememulti-secret sharing scheme
Contact author(s)
jiangt_yuan @ 163 com
2020-12-30: revised
2020-12-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jiangtao Yuan and Jing Yang and Guoai Xu and Xingxing Jia and Fang-wei Fu and Chenyu Wang},
      title = {A New Efficient Hierarchical Multi-secret Sharing Scheme Based on Linear Homogeneous Recurrence Relations},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1612},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.