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

Cybersecurity

Shorter lattice-based verifiable encryption using bimodal Gaussian

Dong Fang, Guifang Huang, Shuai Chang, Haonan Yang, Lei Hu, Dingfeng Ye

Published Sep 9, 2025• 0 citations
Publisher

Abstract

Abstract Verifiable encryption enables the decryption to be taken on properly generated ciphertexts, by making the encryptor provide a zero-knowledge proof. To meet the quantum-safe application requirements, such as key escrow, Lyubashevsky et al. proposed a one-shot verifiable encryption (LN17 scheme) based on the hardness of lattice problems. In their scheme, the FSwA-type zero-knowledge proof was obtained using rejection sampling on a discrete Gaussian distribution. In this paper, we present a construction of verifiable encryption that utilizes rejection sampling on bimodal Gaussian to get the associated zero-knowledge proof. Our new construction, while exhibiting a weaker soundness property than LN17 scheme, benefits from a smaller proof size, leading to a reduced size of the verifiable ciphertext. As for the weaker soundness property, it supports some applications such as key escrow where honestly generated verifiable ciphertexts are more useful to be decrypted out in the hope of doing some further computation tasks. We provide the efficiency comparison of the new construction by instantiating it with several sets of concrete parameters.

DOI
10.1186/s42400-024-00351-4

Related papers

Application of invertible elements in a zero-knowledge proof

Karolína Kučerová

This work is focused on the description of one verifiable encryption scheme, specifically a zero-knowledge proof of knowledge protocol. Verifiable encryption allows us to prove properties of data without revealing its content. The main goal of the presented method is verification of knowledge of a secret key. This method can be used for group signa- tures, multiple steps secret sharing, key escrow protocols, and many others cryptographic protocols. It is based on the hardness of the Ring-LWE problem and problems of finding solutions to linear relations over some ring. It uses the principle of rejection sampling. The method is build on two closely described cryptographic protocols, Ring-LWE and Fiat-Shamir with aborts. It uses the construction of polynomial rings R = Z[x]/(xn + 1) a Rq = Zq[x]/(xn + 1). 1

•Jan 1, 2022•0 citations

Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems.

Rikke Bendlin, Ivan Damgård

Abstract. We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical re-duction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active ad-versaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge- prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key. 1

•Jan 1, 2009•0 citations

An Ideal Lattice Signcryption Scheme for Data Protection

Mingna Hou, Jie Cai, Jinxin Huang +2 more

Signcryption simultaneously provides confidentiality and authenticity, rendering it well-suited for secure data transmission. However, most existing signcryption constructions rely on number-theoretic hard problems, which renders them susceptible to quantum attacks. For this reason, this paper designs a trapdoor-free signcryption scheme over ideal lattices. Our scheme employs bimodal Gaussian rejection sampling to reduce the rejection constant from e12α+12α2 to e12α2, and leverages the Number Theoretic Transform for faster polynomial multiplication. Furthermore, we demonstrate that the scheme simultaneously satisfies IND-CPA confidentiality and EUF-CMA unforgeability based on the R-LWE and R-SIS hardness assumptions within the random oracle model. In contrast to present lattice-based signcryption schemes, the proposed construction achieves smaller key sizes and lower computational cost, making it suitable for privacy-preserving applications.

Applied Sciences•Oct 17, 2026•0 citations

Compressed Zero-Knowledge Proofs for Lattice-Based Accumulator

Shumin Si, Xiuhan Lin, Puwen Wei

Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with $2^{32}$ members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in $l\cdot n_{s}$, where $l$ and $n_{s}$ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when $l=32$. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.

The Computer Journal•Mar 10, 2023•3 citations

A Conditional Privacy-Preserving Certificateless Signature Scheme Based on Lattice

Pan Chen, Liquan Chen, Bo Yang +2 more

A myriad of conditional privacy-preserving signature (CPPS) schemes have emerged recently, aiming to secure communication data while preserving user privacy. However, many of these schemes, relying on classical mathematical problems and identity based cryptographic mechanism, suffer from key escrow vulnerabilities and are susceptible to quantum attacks. In this paper, we propose a lattice based conditional privacy-preserving certificateless signature scheme. By leveraging the ring small integer solution problem and the decisional compact knapsack problem, our scheme demonstrates robust resistance against quantum attacks with high asymptotic efficiency. We utilize certificateless signature to circumvent the key escrow issue inherent in identity based CPPS schemes. While ensuring conditional privacy preservation, we enhance the security and efficiency of the signature process through a rejection sampling algorithm based on the bimodal Gaussian distribution. Furthermore, our security analysis demonstrates resilience against type I and type II adversaries, meeting diverse security requirements such as traceability and unlinkability. Through a comparative analysis of communication traffic, we observe commendable efficiency in signature generation, making our scheme particularly suitable for wireless communication scenarios. Finally, we detail implementation strategies tailored for drone networks, enhancing the practicality and relevance of our contributions in wireless communication contexts.

International Conference on Big Data Computing and Communications (BigCom)•Aug 9, 2024•0 citations

Non-interactive zero-knowledge proof scheme from RLWE-based key exchange

Shaofen Xie, Wang Yao, Faguo Wu +1 more

Lattice-based non-interactive zero-knowledge proof has been widely used in one-way communication and can be effectively applied to resist quantum attacks. However, lattice-based non-interactive zero-knowledge proof schemes have long faced and paid more attention to some efficiency issues, such as proof size and verification time. In this paper, we propose the non-interactive zero-knowledge proof schemes from RLWE-based key exchange by making use of the Hash function and public-key encryption. We then show how to apply the proposed schemes to achieve the fixed proof size and rapid public verification. Compared with previous approaches, our schemes can realize better effectiveness in proof size and verification time. In addition, the proposed schemes are secure from completeness, soundness, and zero-knowledge.

PLoS ONE•Aug 20, 2021•3 citations
Abstract Verifiable encryption enables the decryption to be taken on properly generated ciphertexts, by making the encryptor provide a zero-knowledge proof. To meet the quantum-safe application requirements, such as key escrow, Lyubashevsky et al. proposed a one-shot verifiable encryption (LN17 scheme) based on the hardness of lattice problems. In their scheme, the FSwA-type zero-knowledge proof was obtained using rejection sampling on a discrete Gaussian distribution. In this paper, we present a construction of verifiable encryption that utilizes rejection sampling on bimodal Gaussian to get the associated zero-knowledge proof. Our new construction, while exhibiting a weaker soundness property than LN17 scheme, benefits from a smaller proof size, leading to a reduced size of the verifiable ciphertext. As for the weaker soundness property, it supports some applications such as key escrow where honestly generated verifiable ciphertexts are more useful to be decrypted out in the hope of doing some further computation tasks. We provide the efficiency comparison of the new construction by instantiating it with several sets of concrete parameters.
This work is focused on the description of one verifiable encryption scheme, specifically a zero-knowledge proof of knowledge protocol. Verifiable encryption allows us to prove properties of data without revealing its content. The main goal of the presented method is verification of knowledge of a secret key. This method can be used for group signa- tures, multiple steps secret sharing, key escrow protocols, and many others cryptographic protocols. It is based on the hardness of the Ring-LWE problem and problems of finding solutions to linear relations over some ring. It uses the principle of rejection sampling. The method is build on two closely described cryptographic protocols, Ring-LWE and Fiat-Shamir with aborts. It uses the construction of polynomial rings R = Z[x]/(xn + 1) a Rq = Zq[x]/(xn + 1). 1
Abstract. We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical re-duction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active ad-versaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge- prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key. 1
Signcryption simultaneously provides confidentiality and authenticity, rendering it well-suited for secure data transmission. However, most existing signcryption constructions rely on number-theoretic hard problems, which renders them susceptible to quantum attacks. For this reason, this paper designs a trapdoor-free signcryption scheme over ideal lattices. Our scheme employs bimodal Gaussian rejection sampling to reduce the rejection constant from e12α+12α2 to e12α2, and leverages the Number Theoretic Transform for faster polynomial multiplication. Furthermore, we demonstrate that the scheme simultaneously satisfies IND-CPA confidentiality and EUF-CMA unforgeability based on the R-LWE and R-SIS hardness assumptions within the random oracle model. In contrast to present lattice-based signcryption schemes, the proposed construction achieves smaller key sizes and lower computational cost, making it suitable for privacy-preserving applications.
Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with 2322^{32}232 members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in l⋅nsl\cdot n_{s}l⋅ns​, where lll and nsn_{s}ns​ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when l=32l=32l=32. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.
A myriad of conditional privacy-preserving signature (CPPS) schemes have emerged recently, aiming to secure communication data while preserving user privacy. However, many of these schemes, relying on classical mathematical problems and identity based cryptographic mechanism, suffer from key escrow vulnerabilities and are susceptible to quantum attacks. In this paper, we propose a lattice based conditional privacy-preserving certificateless signature scheme. By leveraging the ring small integer solution problem and the decisional compact knapsack problem, our scheme demonstrates robust resistance against quantum attacks with high asymptotic efficiency. We utilize certificateless signature to circumvent the key escrow issue inherent in identity based CPPS schemes. While ensuring conditional privacy preservation, we enhance the security and efficiency of the signature process through a rejection sampling algorithm based on the bimodal Gaussian distribution. Furthermore, our security analysis demonstrates resilience against type I and type II adversaries, meeting diverse security requirements such as traceability and unlinkability. Through a comparative analysis of communication traffic, we observe commendable efficiency in signature generation, making our scheme particularly suitable for wireless communication scenarios. Finally, we detail implementation strategies tailored for drone networks, enhancing the practicality and relevance of our contributions in wireless communication contexts.
Lattice-based non-interactive zero-knowledge proof has been widely used in one-way communication and can be effectively applied to resist quantum attacks. However, lattice-based non-interactive zero-knowledge proof schemes have long faced and paid more attention to some efficiency issues, such as proof size and verification time. In this paper, we propose the non-interactive zero-knowledge proof schemes from RLWE-based key exchange by making use of the Hash function and public-key encryption. We then show how to apply the proposed schemes to achieve the fixed proof size and rapid public verification. Compared with previous approaches, our schemes can realize better effectiveness in proof size and verification time. In addition, the proposed schemes are secure from completeness, soundness, and zero-knowledge.