A lattice based changeable threshold multi-secret sharing scheme and its application to threshold cryptography

In this paper, we propose a threshold increasing algorithm for a (t;n) lattice based threshold multi-stage secret sharing (TMSSS) scheme. For realization of the changeability feature, we use the zero addition protocol to construct a new (tœ;n) TMSSS scheme. Therefore, the new scheme enjoys the significant feature of threshold changeability in addition to the inherited features of being multi-stage, multi-use and verifiable from our previously proposed lattice based TMSSS scheme. Furthermore, we use the improved TMSSS scheme to propose a threshold decryption algorithm for the learning with error (LWE) based public key encryption scheme based on Lindner and Peikert’s. For threshold decryption, each authorized subset of participants decrypts the ciphertext partially and sends the result to the combiner. Using them, the combiner can decrypt the ciphertext. The security of both schemes is based on the hardness of lattice problems, i.e., LWE and inhomogeneous small integer solution (ISIS) problems, which are believed to resist against the quantum algorithms. The proposed schemes are efficient, especially in the participants’ side, making them suitable for the applications in which the participants have limited processing capacities.