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

arXiv:2202.09026

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

Jing Yang, Fang‐Wei Fu

Published Feb 18, 2022• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2202.09026

Related papers

An Efficient Lattice Based Multi-stage Secret Sharing Scheme

Hossein Pilaram, Taraneh Eghlidos

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.

IEEE Transactions on Dependable and Secure Computing•Jan 1, 2015•45 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

Quantum multi-secret sharing scheme with access structures and cheat identification

Deepa Rathi, Sanjeev Kumar

This work proposes a [Formula: see text]-dimensional quantum multi-secret sharing scheme with a cheat-detection mechanism. The dealer creates multiple secrets and distributes the shares of these secrets using multi-access structures and a monotone span program. The dealer detects the cheating of each participant using the black box’s cheat-detection mechanism. To detect the participants’ deceit, the dealer distributes secret shares’ shadows derived from a randomly invertible matrix [Formula: see text] to the participants, stored in the black box. The black box identifies the participant’s deceitful behavior during the secret recovery phase. Only honest participants authenticated by the black box acquire their secret shares to recover the multiple secrets. After the black box cheating verification, the participants reconstruct the secrets by utilizing the unitary operations and quantum Fourier transform. The proposed protocol is reliable in preventing attacks from eavesdroppers and participants. The scheme’s efficiency is demonstrated in different noise environments: dit-flip noise, [Formula: see text]-phase-flip noise and amplitude-damping noise, indicating its robustness in practical scenarios. The proposed protocol provides greater versatility, security and practicality.

arXiv:2309.06458•International Journal of Quantum Information•Feb 23, 2024•5 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

Lattice-Based Threshold Secret Sharing Scheme and Its Applications: A Survey

Jingyu Chen, Haitao Deng, Huachang Su +2 more

As the most popular cryptographic scheme in the post-quantum field, lattices have received extensive attention and research. Not only do they provide quantum-resistant security, they also enable the construction of complex applications. Currently, lattice cryptography schemes based on different difficult problems have been applied in different fields. The threshold secret sharing (TSS) scheme is an important field of cryptography and has important application value and development prospects in key protection, secure multi-party computation, privacy protection, etc. However, with the rapid development of quantum computing, many existing cryptography-underlying technologies are facing huge difficulties and challenges. Therefore, post-quantum TSS has important research significance and value for the future development of cryptography. In this paper, we summarize the existing secret sharing schemes based on lattice-hard problems and the relevant applications of these schemes in the post-quantum realm. We classify existing lattice-based TSS according to different functions and introduce typical solutions. To the best of our knowledge, this is the first review paper on lattice-based TSS schemes.

Electronics•Jan 8, 2024•15 citations

An efficient and novel weighted threshold quantum secret sharing scheme with changeable participant weights

Fulin Li, Mengting Zhang, Yixin Sun +1 more

Abstract Quantum secret sharing plays a crucial role in quantum cryptography. In this paper, an efficient and novel weighted threshold quantum secret sharing scheme with changeable participant weights is firstly proposed based on the monotone span program(MSP) and linear secret sharing(LSS) scheme. First, in the secret reconstruction phase, participants only need to perform simple measurement operations on the particles to successfully recover and verify the secret. Additionally, throughout the entire scheme, participants are not required to perform any quantum operations, significantly enhancing the efficiency of the scheme. Secondly, without altering the secret shares of all participants, our scheme firstly enables dynamic changes in participant weights without the need for re-execution, which improves the practicality of the scheme. Security analysis shows that our scheme is resistant to a series of typical attacks. Compared with the existing schemes, our scheme is more efficient and practical.

Chinese Physics B•Jan 27, 2026•0 citations
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 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.
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.
This work proposes a [Formula: see text]-dimensional quantum multi-secret sharing scheme with a cheat-detection mechanism. The dealer creates multiple secrets and distributes the shares of these secrets using multi-access structures and a monotone span program. The dealer detects the cheating of each participant using the black box’s cheat-detection mechanism. To detect the participants’ deceit, the dealer distributes secret shares’ shadows derived from a randomly invertible matrix [Formula: see text] to the participants, stored in the black box. The black box identifies the participant’s deceitful behavior during the secret recovery phase. Only honest participants authenticated by the black box acquire their secret shares to recover the multiple secrets. After the black box cheating verification, the participants reconstruct the secrets by utilizing the unitary operations and quantum Fourier transform. The proposed protocol is reliable in preventing attacks from eavesdroppers and participants. The scheme’s efficiency is demonstrated in different noise environments: dit-flip noise, [Formula: see text]-phase-flip noise and amplitude-damping noise, indicating its robustness in practical scenarios. The proposed protocol provides greater versatility, security and practicality.
As the most popular cryptographic scheme in the post-quantum field, lattices have received extensive attention and research. Not only do they provide quantum-resistant security, they also enable the construction of complex applications. Currently, lattice cryptography schemes based on different difficult problems have been applied in different fields. The threshold secret sharing (TSS) scheme is an important field of cryptography and has important application value and development prospects in key protection, secure multi-party computation, privacy protection, etc. However, with the rapid development of quantum computing, many existing cryptography-underlying technologies are facing huge difficulties and challenges. Therefore, post-quantum TSS has important research significance and value for the future development of cryptography. In this paper, we summarize the existing secret sharing schemes based on lattice-hard problems and the relevant applications of these schemes in the post-quantum realm. We classify existing lattice-based TSS according to different functions and introduce typical solutions. To the best of our knowledge, this is the first review paper on lattice-based TSS schemes.
Abstract Quantum secret sharing plays a crucial role in quantum cryptography. In this paper, an efficient and novel weighted threshold quantum secret sharing scheme with changeable participant weights is firstly proposed based on the monotone span program(MSP) and linear secret sharing(LSS) scheme. First, in the secret reconstruction phase, participants only need to perform simple measurement operations on the particles to successfully recover and verify the secret. Additionally, throughout the entire scheme, participants are not required to perform any quantum operations, significantly enhancing the efficiency of the scheme. Secondly, without altering the secret shares of all participants, our scheme firstly enables dynamic changes in participant weights without the need for re-execution, which improves the practicality of the scheme. Security analysis shows that our scheme is resistant to a series of typical attacks. Compared with the existing schemes, our scheme is more efficient and practical.