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

PLoS ONE

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

Shaofen Xie, Wang Yao, Faguo Wu, Zhiming Zheng

Published Aug 20, 2021• 3 citations
Publisher

Abstract

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.

DOI
10.1371/journal.pone.0256372

Related papers

Hash Proof System Based on Lattice

Xia Feng, Bo Yang, Qiong Huang +1 more

We present a hash proof systems (HPS)based on hard lattice problems including learning with error (LWE) and inhomogeneous small integer solution (ISIS). Different from the HPS in past, ours is with error. That is to say, the deterministic private evaluation algorithm is not always equivalent to the deterministic public evaluation algorithm. The difference between them is one or zero. We also show how to construct a public-key encryption scheme which is semantically secure against key-leakage attacks in the standard model using our HPS based on lattice. Compared with previous cryptosystem based on lattice, our construction needs bigger public key space but fewer operations during encryption, and can resist quantum attacks because of the assumption on lattice problem.

International Journal of Advancements in Computing Technology•May 31, 2012•1 citation

Zero-knowledge Identification based on Lattices with Low Communication Costs

Rosemberg Silva, Pierre-Louis Cayrel, Richard Lindner

In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.

Simpósio Brasileiro de Cibersegurança (SBSeg)•Nov 6, 2011•3 citations

Post-Quantum Zero-Knowledge Proofs and Applications

Ron Steinfeld

Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 20, 2023•4 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

Zero-Knowledge Proof for Knowledge of RLWE (Ring-Learning with Errors) Secret Keys

Saraswathy Rv

Key Exchange is an essential primitive in cryptography that originated from the breakthrough idea of Diffie Hellman (DH) protocol presented in 1976.Following this work, there are many successful variants of DH using Elliptic curves, Isogeny and RLWE (Ring Learning with Errors).The Ring-Leaning with Errors (RLWE), Search and Decision version are hard problems in mathematics and it has been shown that solving worst case hard problems in ideal lattices can be reduced to solving RLWE in the average case.The reduction forms the basis of provable security for RLWE based key exchange against passive adversaries.The hardness of the decision version of RLWE, which means indistinguishability of RLWE samples from Uniform, makes it challenging to validate a RLWE form public key.This proves to be an advantage for malicious users to create public keys that deviate from a protocol to recover the secret of reused keys in Key Exchange (KE) protocols.In this thesis, we provide a cryptanalysis of RLWE key exchange, presenting two polynomial time strategies to exploit key reuse.Then we propose a defense against such exploits by presenting a Zero Knowledge authentication protocol to verify the prover's knowledge of a secret corresponding to his public key.The protocol is Statistical Zero Knowledge with negligible soundness and completeness errors so that the prover does not reveal any information about the secret in the proof.This is to ensure that a malicious verifier cannot impersonate the prover after the proof.The authentication protocol uses the signal function defined in RLWE key exchange to perform the verification.Firstly, I would like to express my gratitude to my advisor Prof.Ding for his expert advice, strong encouragement and support throughout my PhD study

•Jan 1, 2018•0 citations

More Efficient Lattice-Based Zero-Knowledge Proofs with Straight-Line Extractability

Ngoc Khanh Nguyen, George O'Rourke

In this work, we present a concretely efficient lattice-based zero-knowledge proof system that satisfies straight-line extractability. At the heart of our construction is a novel, non-generic application of the Katsumata transform (CRYPTO 2021) to the widely adopted zero-knowledge framework of Lyubashevsky, Nguyen and Plançon (CRYPTO 2022). Our approach significantly optimizes the proof size, achieving a 2X reduction compared to prior generic techniques. This makes our scheme particularly well-suited for anonymous credential systems, secure multi-party computation, and proving quantum security, where straight-line extractability is essential.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 6, 2025•2 citations
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.
We present a hash proof systems (HPS)based on hard lattice problems including learning with error (LWE) and inhomogeneous small integer solution (ISIS). Different from the HPS in past, ours is with error. That is to say, the deterministic private evaluation algorithm is not always equivalent to the deterministic public evaluation algorithm. The difference between them is one or zero. We also show how to construct a public-key encryption scheme which is semantically secure against key-leakage attacks in the standard model using our HPS based on lattice. Compared with previous cryptosystem based on lattice, our construction needs bigger public key space but fewer operations during encryption, and can resist quantum attacks because of the assumption on lattice problem.
In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.
Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].
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
Key Exchange is an essential primitive in cryptography that originated from the breakthrough idea of Diffie Hellman (DH) protocol presented in 1976.Following this work, there are many successful variants of DH using Elliptic curves, Isogeny and RLWE (Ring Learning with Errors).The Ring-Leaning with Errors (RLWE), Search and Decision version are hard problems in mathematics and it has been shown that solving worst case hard problems in ideal lattices can be reduced to solving RLWE in the average case.The reduction forms the basis of provable security for RLWE based key exchange against passive adversaries.The hardness of the decision version of RLWE, which means indistinguishability of RLWE samples from Uniform, makes it challenging to validate a RLWE form public key.This proves to be an advantage for malicious users to create public keys that deviate from a protocol to recover the secret of reused keys in Key Exchange (KE) protocols.In this thesis, we provide a cryptanalysis of RLWE key exchange, presenting two polynomial time strategies to exploit key reuse.Then we propose a defense against such exploits by presenting a Zero Knowledge authentication protocol to verify the prover's knowledge of a secret corresponding to his public key.The protocol is Statistical Zero Knowledge with negligible soundness and completeness errors so that the prover does not reveal any information about the secret in the proof.This is to ensure that a malicious verifier cannot impersonate the prover after the proof.The authentication protocol uses the signal function defined in RLWE key exchange to perform the verification.Firstly, I would like to express my gratitude to my advisor Prof.Ding for his expert advice, strong encouragement and support throughout my PhD study
In this work, we present a concretely efficient lattice-based zero-knowledge proof system that satisfies straight-line extractability. At the heart of our construction is a novel, non-generic application of the Katsumata transform (CRYPTO 2021) to the widely adopted zero-knowledge framework of Lyubashevsky, Nguyen and Plançon (CRYPTO 2022). Our approach significantly optimizes the proof size, achieving a 2X reduction compared to prior generic techniques. This makes our scheme particularly well-suited for anonymous credential systems, secure multi-party computation, and proving quantum security, where straight-line extractability is essential.