Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Dependable and Secure Computing

An Efficient Lattice Based Multi-stage Secret Sharing Scheme

Hossein Pilaram, Taraneh Eghlidos

Published Jan 1, 2015• 45 citations
Publisher

Abstract

In this paper, we construct a lattice based (t, n) threshold multi-stage secret sharing (MSSS) scheme according to Ajtai's construction for one-way functions. In an MSSS scheme, the authorized subsets of participants can recover a subset of secrets at each stage while other secrets remain undisclosed. In this paper, each secret is a vector from a t-dimensional lattice and the basis of each lattice is kept private. A t-subset of n participants can recover the secret(s) using their assigned shares. Using a lattice based one-way function, even after some secrets are revealed, the computational security of the unrecovered secrets is provided against quantum computers. The scheme is multi-use in the sense that to share a new set of secrets, it is sufficient to renew some public information such that a new share distribution is no longer required. Furthermore, the scheme is verifiable meaning that the participants can verify the shares received from the dealer and the recovered secrets from the combiner, using public information.

DOI
10.1109/tdsc.2015.2432800

Related papers

Post-quantum Multi-stage Secret Sharing Schemes using Inhomogeneous Linear Recursion and Ajtai's Function

Jing Yang, Fang‐Wei Fu

Secret sharing was firstly proposed in 1979 by Shamir and Blakley respectively. To avoid deficiencies of original schemes, researchers presented improvement schemes, among which the multi-secret sharing scheme (MSS) is significant. There are three categories of MSSs, however, we focus on multi-stage secret sharing scheme (MSSS) recovering secrets with any order in this work. By observing inhomogeneous linear recursions (ILRs) in the literature, we conclude a general formula and divide ILRs into two types according to different variables in them. Utilizing these two kinds of ILRs, we propose four verifiable MSSSs with Ajtai's function, which is a lattice-based function. Our schemes have the following advantages. Firstly, our schemes can detect cheat of the dealer and participants, and are multi-use. Secondly, we have several ways to restore secrets. Thirdly, we can turn our schemes into other types of MSSs due to the universality of our method. Fourthly, since we utilize a lattice-based function to mask shares, our schemes can resist the attack from the quantum computer with computational security. Finally, although our schemes need more memory consumption than some known schemes, we need much less time consumption, which makes our schemes more suitable facing limited computing power.

arXiv:2202.09026•Feb 18, 2022•0 citations

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

Hossein Pilaram, Taraneh Eghlidos

In this paper, we propose a threshold increasing algorithm for a (t; n) latticebased Threshold Multi-Stage Secret Sharing (TMSSS) scheme. To realize the changeability feature, we use the zero addition protocol to construct a new (t0; n) TMSSS scheme. Therefore, the new scheme enjoys the signi cant feature of threshold changeability along with the inherited features of being multi-stage, multi-use, and veri able derived fromour 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 the study of Lindner and Peikert. For threshold decryption, each authorized subset of participants decrypts the ciphertext partially and sends the result to the combiner. The combiner can decrypt the ciphertext using the partial decryptions. The security of both schemes is based on 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 eficient, especially on the participants' side, making them suitable for the applications in which the participants have limited processing capacities.

Scientia Iranica•Jun 1, 2017•15 citations

A Verifiable Multi-Secret Sharing Scheme Based on Short Integer Solution

Fulin Li, Jiayun Yan, Shixin Zhu +1 more

With the possible birth of the quantum computer, traditional secret sharing schemes have been unable to meet security requirements. We proposed a new verifiable multi-secret sharing scheme based on the short integer solution problem. By utilizing a symmetric binary polynomial,$k$secrets and secret shares can be generated, and then we convert the secret shares into binary string on$\mathbb{Z}_{q}$, which can be identified by one-way anti-collision hash function on the lattice, so that multiple secrets can be reconstructed safely. The advantages mainly focus on verifiability without interaction in the distribution phase and less memory requirement. In a secret sharing scheme, verifiability prevents the dealer to share the wrong shares and forces the participants to submit their shares correctly. Meanwhile, the interaction can be reduced, which means the security is improved. In a multi-secret sharing scheme, releasing the public values is inevitable, this paper has less public values and less size of shares per secret size to reduce the pressure of memory consumption in the proper parameters. In the end, it can also effectively resist the quantum attack.

Chinese Journal of Electronics•May 1, 2023•8 citations

A novel verifiable weighted threshold quantum secret sharing scheme

Yumin Dong, Yi Luo, Yanying Fu

Abstract Threshold quantum secret sharing is a cryptography technique for dividing and reconstructing secret information. The dealer shares a secret based on quantum mechanics principles, and a subset of participants cooperate to recover that secret. For example, in k , n quantum threshold scheme and n , n quantum threshold scheme, the former can only reconstruct the secret when at least k shares are collected. The latter requires all n shares to be collected to reconstruct the secret. However, in real scenarios, the priority of participant identities may vary. In order to meet the actual needs of participants with different rights, this paper proposes a w , ω , n quantum secret sharing (QSS) scheme. When the sum of participants’ weights w is greater than or equal to a threshold ω, they can cooperate to reconstruct the secret. In order to achieve this, this paper uses the entangled state of single particles and constructs a verifiable QSS scheme based on the Chinese remainder theorem. Significantly, in case of a dishonest participant, the dealer can delete the participant before recovering the secret to ensure the security of the communication. This scheme is more flexible than other threshold protocols. At the same time, it reduces the communication cost of the participants. In addition, security analysis shows that the scheme resists typical external and internal attacks.

Physica Scripta•Apr 21, 2023•7 citations

On the Security of a Lattice-Based Multi-Stage Secret Sharing Scheme

Zhichao Yang, Debiao He, Longjiang Qu +1 more

In response to the threat posed by quantum computers, Pilaram and Eghlidos proposed the first lattice-based multi-stage secret sharing scheme which is the only post-quantum multi-stage secret sharing scheme. In this paper, we introduce an efficient attack on it and show that any adversary can easily reconstruct unrecovered secrets as long as it collects enough pseudo-secret shares. For the sake of complete, we further list two countermeasures to protect the scheme from such attack.

IEEE Transactions on Dependable and Secure Computing•Sep 23, 2022•8 citations

Secret sharing scheme based on the Goldwasser-Goldrich-Halevi cryptosystem

Artemii Likhachov, Bogdana Oliynyk

With the development of quantum technologies, the issue of research and implementation of cryptographic primitives based on complex problems for quantum computing becomes relevant. Such cryptographic primitives are resistant to quantum cryptanalysis. Examples of problems with exponential complexity for quantum computing is lattice problems such as finding the shortest vector or finding the closest vector. One of the first and most famous quantum-resistant cryptosystems that use lattice problems as the basis of its mathematical apparatus is the Goldwasser-Goldrich-Halevi cryptosystem.A secret distribution scheme is a fundamental cryptographic primitive that allows the distribution of a secret among a set of participants while the secret recovery is possible only when all or a certain part of the participants (the threshold of participants) is authorized. Also, a necessary condition for a secret distribution scheme is the impossibility of individual participants, or groups of participants whose number is less than the threshold, to recover the secret. Variants of constructing secret sharing schemes on various mathematical models, including lattices, are currently being actively studied since they allow for security multiparty calculations and secure information dissemination by distributing the original data between different servers. It is also used for constructing compilers of schemes with protection against leakage, etc. In this paper, a new quantum-stable n-threshold secret sharing scheme for n participants, based on the Goldwasser-Goldrich-Halevi cryptosystem, is proposed.

Mohyla Mathematical Journal•May 12, 2025•1 citation
In this paper, we construct a lattice based (t, n) threshold multi-stage secret sharing (MSSS) scheme according to Ajtai's construction for one-way functions. In an MSSS scheme, the authorized subsets of participants can recover a subset of secrets at each stage while other secrets remain undisclosed. In this paper, each secret is a vector from a t-dimensional lattice and the basis of each lattice is kept private. A t-subset of n participants can recover the secret(s) using their assigned shares. Using a lattice based one-way function, even after some secrets are revealed, the computational security of the unrecovered secrets is provided against quantum computers. The scheme is multi-use in the sense that to share a new set of secrets, it is sufficient to renew some public information such that a new share distribution is no longer required. Furthermore, the scheme is verifiable meaning that the participants can verify the shares received from the dealer and the recovered secrets from the combiner, using public information.
Secret sharing was firstly proposed in 1979 by Shamir and Blakley respectively. To avoid deficiencies of original schemes, researchers presented improvement schemes, among which the multi-secret sharing scheme (MSS) is significant. There are three categories of MSSs, however, we focus on multi-stage secret sharing scheme (MSSS) recovering secrets with any order in this work. By observing inhomogeneous linear recursions (ILRs) in the literature, we conclude a general formula and divide ILRs into two types according to different variables in them. Utilizing these two kinds of ILRs, we propose four verifiable MSSSs with Ajtai's function, which is a lattice-based function. Our schemes have the following advantages. Firstly, our schemes can detect cheat of the dealer and participants, and are multi-use. Secondly, we have several ways to restore secrets. Thirdly, we can turn our schemes into other types of MSSs due to the universality of our method. Fourthly, since we utilize a lattice-based function to mask shares, our schemes can resist the attack from the quantum computer with computational security. Finally, although our schemes need more memory consumption than some known schemes, we need much less time consumption, which makes our schemes more suitable facing limited computing power.
In this paper, we propose a threshold increasing algorithm for a (t; n) latticebased Threshold Multi-Stage Secret Sharing (TMSSS) scheme. To realize the changeability feature, we use the zero addition protocol to construct a new (t0; n) TMSSS scheme. Therefore, the new scheme enjoys the signi cant feature of threshold changeability along with the inherited features of being multi-stage, multi-use, and veri able derived fromour 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 the study of Lindner and Peikert. For threshold decryption, each authorized subset of participants decrypts the ciphertext partially and sends the result to the combiner. The combiner can decrypt the ciphertext using the partial decryptions. The security of both schemes is based on 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 eficient, especially on the participants' side, making them suitable for the applications in which the participants have limited processing capacities.
With the possible birth of the quantum computer, traditional secret sharing schemes have been unable to meet security requirements. We proposed a new verifiable multi-secret sharing scheme based on the short integer solution problem. By utilizing a symmetric binary polynomial,kkksecrets and secret shares can be generated, and then we convert the secret shares into binary string onZq\mathbb{Z}_{q}Zq​, which can be identified by one-way anti-collision hash function on the lattice, so that multiple secrets can be reconstructed safely. The advantages mainly focus on verifiability without interaction in the distribution phase and less memory requirement. In a secret sharing scheme, verifiability prevents the dealer to share the wrong shares and forces the participants to submit their shares correctly. Meanwhile, the interaction can be reduced, which means the security is improved. In a multi-secret sharing scheme, releasing the public values is inevitable, this paper has less public values and less size of shares per secret size to reduce the pressure of memory consumption in the proper parameters. In the end, it can also effectively resist the quantum attack.
Abstract Threshold quantum secret sharing is a cryptography technique for dividing and reconstructing secret information. The dealer shares a secret based on quantum mechanics principles, and a subset of participants cooperate to recover that secret. For example, in k , n quantum threshold scheme and n , n quantum threshold scheme, the former can only reconstruct the secret when at least k shares are collected. The latter requires all n shares to be collected to reconstruct the secret. However, in real scenarios, the priority of participant identities may vary. In order to meet the actual needs of participants with different rights, this paper proposes a w , ω , n quantum secret sharing (QSS) scheme. When the sum of participants’ weights w is greater than or equal to a threshold ω, they can cooperate to reconstruct the secret. In order to achieve this, this paper uses the entangled state of single particles and constructs a verifiable QSS scheme based on the Chinese remainder theorem. Significantly, in case of a dishonest participant, the dealer can delete the participant before recovering the secret to ensure the security of the communication. This scheme is more flexible than other threshold protocols. At the same time, it reduces the communication cost of the participants. In addition, security analysis shows that the scheme resists typical external and internal attacks.
With the development of quantum technologies, the issue of research and implementation of cryptographic primitives based on complex problems for quantum computing becomes relevant. Such cryptographic primitives are resistant to quantum cryptanalysis. Examples of problems with exponential complexity for quantum computing is lattice problems such as finding the shortest vector or finding the closest vector. One of the first and most famous quantum-resistant cryptosystems that use lattice problems as the basis of its mathematical apparatus is the Goldwasser-Goldrich-Halevi cryptosystem.A secret distribution scheme is a fundamental cryptographic primitive that allows the distribution of a secret among a set of participants while the secret recovery is possible only when all or a certain part of the participants (the threshold of participants) is authorized. Also, a necessary condition for a secret distribution scheme is the impossibility of individual participants, or groups of participants whose number is less than the threshold, to recover the secret. Variants of constructing secret sharing schemes on various mathematical models, including lattices, are currently being actively studied since they allow for security multiparty calculations and secure information dissemination by distributing the original data between different servers. It is also used for constructing compilers of schemes with protection against leakage, etc. In this paper, a new quantum-stable n-threshold secret sharing scheme for n participants, based on the Goldwasser-Goldrich-Halevi cryptosystem, is proposed.