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.
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.
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.
Modern approaches to secret sharing have been examined, encompassing both classical and post-quantum cryptographic schemes. The study explores methods for distributing secret information among multiple participants using various mathematical primitives, such as Lagrange and Newton polynomials, the Chinese remainder theorem, error-correcting codes, lattice theory, elliptic curve isogenies, multivariate equations, and hash functions. A comparative analysis of different schemes is provided in terms of their resistance to quantum attacks, efficiency, and compliance with Shamir’s criteria. Special attention is given to assessing the schemes resilience against attacks using quantum computers, which is particularly relevant given the advancement of quantum technologies. The advantages and disadvantages of each scheme are discussed, including their computational complexity, flexibility, and adaptability to various conditions. It is shown that classical schemes, such as those by Shamir and Newton, remain efficient and easy to implement but are vulnerable to quantum attacks. Meanwhile, post-quantum schemes based on lattice theory demonstrate a high level of security but require more complex computations.
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.
In this paper, a variant of (t, n) threshold secret sharing scheme is realized using a lattice model. Due to the potential quantum attacks in the future, we need to construct a secure channels for transmitting secret shares. Such channels could be modeled by a lattice based public key cryptosystem whose security is based on the worst case hardness of lattice problems. Therefore, we propose a lattice based threshold secret sharing scheme that is compatible with the platform on which the cryptosystem is built. It is shown that the proposed scheme is correct and asymptotically perfect from information theoretic point of view.
Abstract Secret sharing, as an important cryptographic technique, effectively reduces the risk of single points of failure and centralized leakage by distributing secret information across multiple independent entities. With the widespread application of cloud computing and cloud storage, achieving long-term secure storage and controllable recovery of sensitive data in untrusted cloud environments has become a critical issue. Traditional cloud storage solutions face potential risks of security degradation and privacy exposure under long-term operation and future quantum computing threats. This paper proposes a quantum secret sharing (QSS) scheme for cloud storage scenarios, combining the threshold secret sharing with quantum secure communication and quantum information processing to achieve distributed storage and secure reconstruction of secret information across multiple cloud servers. A quantum identity authentication mechanism is introduced to the authenticated user based on a quantum sequence. This protocol enhances the long-term security of the system during the storage phase through threshold distribution and proactive share refreshing mechanisms, and utilizes quantum states to complete the secure reconstruction of secrets during the recovery phase. Additionally, this scheme avoids direct interaction between cloud servers, improving the security in untrusted cloud environments. Security analysis shows that this protocol can effectively resist threats such as external eavesdropping and internal collusion.
Despite being considered the first practical lattice-based cryptosystem, interest from the post-quantum cryptography society in the Goldreich-Goldwasser-Halevi (GGH) lattice-based cryptosystem drastically drop due to the embedding-based attacks. The attacks successfully simplified the underlying Closest-Vector Problem (CVP) and made the security of the scheme broken. The attacks become noxious to the GGH cryptosystem due to its ability to simplify the underlying CVP which triggered the enlargement of lattice gaps. Consequently, the simplified CVP can be reduced to a Shortest-Vector Problem (SVP) variant which can be solved by using lattice-reduction algorithms such as the LLL algorithm in a shorter amount of time. The simpler way to evade from these attacks is by implementing larger lattice dimensions which immediately reduce the efficiency of this scheme. Recently, an improved version of the GGH cryptosystem, namely the GGH-MKA cryptosystem, has been proven immune to the embedding-based attacks. The improvement is made by preventing the simplification of the underlying CVP. For that purpose, an error vector is introduced. The error vector is non-eliminable and at the same time maintains the lattice gap. Consequently, the underlying CVP remains in its original form without being simplified. In this study, we showed that the error vector is not unique. We proposed another error vector to combat the embedding-based attacks. We proved that the new error vector has similar capabilities in terms of preventing the simplification of the underlying CVP and maintaining the lattice gap. By improving the security of the GGH cryptosystem, more interest from the mainstream post-quantum discussion could be redirected to the scheme to make it competent and relevant again.