Online citations, reference lists, and bibliographies.

Zero Knowledge Proofs From Ring-LWE

X. Xie, Rui Xue, Minqian Wang
Published 2013 · Mathematics, Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
Zero-Knowledge proof is a very basic and important primitive, which allows a prover to prove some statement without revealing anything else. Very recently, Jain et al. proposed very efficient zero-knowledge proofs to prove any polynomial relations on bits, based on the Learning Parity with Noise (LPN) problem (Asiacrypt'12). In this work, we extend analogous constructions whose security is based on the Ring Learning with Errors (RLWE) problem by adapting the techniques presented by Ling et al. (PKC'13). Specifically, we show a simple zero-knowledge proof of knowledge (Σ-protocol) for committed values, and prove any polynomial relations in the underlying ring. I.e. proving committed ring elements m, m 1,...,m t satisfying m = f(m 1,...,m t ) for any polynomial f. Comparing to other existing Σ-protocols, the extracted witness (error vector) has length only small constant times than the one possessed by the prover. When representing ring element as elements in i¾? q , our protocol has amortized communication complexity $\tilde{O}(\lambda\cdot|f|)$ with exponentially small soundness in security parameter λ, where |f| is the size of the circuit in i¾? q computing f.
This paper references
10.1007/978-3-642-13190-5
Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings
H. Gilbert (2010)
10.1007/3-540-48658-5
Advances in Cryptology — CRYPTO ’94
Y. Desmedt (2001)
10.1145/22145.22178
The knowledge complexity of interactive proof-systems
S. Goldwasser (1985)
10.1007/978-3-642-29011-4_29
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE
Gilad Asharov (2011)
10.1007/BFb0055745
Zero-Knowledge Proofs for Finite Field Arithmetic; or: Can Zero-Knowledge be for Free?
R. Cramer (1998)
10.1007/978-3-642-36362-7_8
Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications
S. Ling (2013)
10.1007/978-3-642-38348-9_3
A Toolkit for Ring-LWE Cryptography
Vadim Lyubashevsky (2013)
10.1007/978-3-540-45146-4_17
Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More
Daniele Micciancio (2003)
10.1007/978-3-642-34961-4_40
Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise
A. Jain (2012)
10.1007/s10623-014-9938-4
Worst-case to average-case reductions for module lattices
A. Langlois (2012)
10.1007/978-3-540-78440-1
Public Key Cryptography - PKC 2008, 11th International Workshop on Practice and Theory in Public-Key Cryptography, Barcelona, Spain, March 9-12, 2008. Proceedings
R. Cramer (2008)
10.1007/s001450010011
Short Non-Interactive Cryptographic Proofs
J. Boyar (2015)
10.1007/978-3-642-29011-4_40
Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation
A. Boldyreva (2012)
10.1007/3-540-48405-1
Advances in Cryptology — CRYPTO’ 99
M. Wiener (1999)
10.1145/1250790.1250792
Statistically-hiding commitment from any one-way function
Iftach Haitner (2007)
10.1007/3-540-45537-X_10
Polynomial Reconstruction Based Cryptography
A. Kiayias (2001)
10.1145/1250790.1250794
Zero-knowledge from secure multiparty computation
Y. Ishai (2007)
10.1007/978-3-642-16280-0_1
Improved Zero-Knowledge Identification with Lattices
Pierre-Louis Cayrel (2010)
10.1007/978-3-642-03356-8_11
On the Amortized Complexity of Zero-Knowledge Protocols
R. Cramer (2009)
10.1007/3-540-48329-2_2
A New Identification Scheme Based on Syndrome Decoding
J. Stern (1993)
10.1007/0-387-34805-0_46
Zero Knowledge Proofs of Knowledge in Two Rounds
U. Feige (1989)
10.1007/978-3-540-78440-1_10
Lattice-Based Identification Schemes Secure Under Active Attacks
Vadim Lyubashevsky (2008)
10.1007/978-3-540-89255-7_23
Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems
Akinori Kawachi (2008)
10.1007/3-540-48658-5_19
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
R. Cramer (1994)
10.1145/1060590.1060603
On lattices, learning with errors, random linear codes, and cryptography
O. Regev (2005)
10.1007/978-3-642-13190-5_1
On Ideal Lattices and Learning with Errors over Rings
Vadim Lyubashevsky (2010)
10.1007/3-540-44750-4_26
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs
I. Damgård (1995)
10.1007/978-3-642-03356-8
Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings
S. Halevi (2009)
10.1007/978-3-642-32284-6_4
On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations
R. Cramer (2012)
Advances in Cryptology - CRYPTO '98
H. Krawczyk (1998)
10.1007/b11817
Advances in Cryptology - CRYPTO 2003
D. Boneh (2003)
Commitments and Efficient Zero-Knowledge Proofs from Hard Learning Problems
Abhishek Jain (2012)
10.1007/978-3-540-89255-7
Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings
J. Pieprzyk (2008)
10.1007/s001459900032
An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions
J. Kilian (1998)
10.1007/978-3-642-29011-4_43
Lattice Signatures Without Trapdoors
Vadim Lyubashevsky (2011)
10.1007/978-3-642-19574-7_12
A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem
Pierre-Louis Cayrel (2010)
10.1007/978-3-540-78967-3
Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings
N. Smart (2008)
10.1561/0100000036
Information Theoretic Security
Y. Liang (2009)
10.1007/978-3-642-38348-9
Advances in Cryptology – EUROCRYPT 2013
T. Johansson (2013)
10.1007/3-540-48329-2
Advances in Cryptology — CRYPTO’ 93
D. Stinson (2001)



This paper is referenced by
Post-Quantum Commitment Schemes
Nabil Alkeilani Alkadri (2015)
10.3934/amc.2020046
A Post-Quantum UC-Commitment Scheme in the Global Random Oracle Model from Code-Based Assumptions
Pedro Branco (2019)
Zero-Knowledge for QMA from Locally Simulatable Proofs
A. Broadbent (2019)
Fully post-quantum protocols for e-voting, coercion resistant cast as intended and mixing networks
Ramiro Martínez Pinilla (2018)
10.1007/978-3-662-53890-6_4
Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption
B. Libert (2016)
10.1007/978-3-319-96881-0_25
Multi-Theorem Preprocessing NIZKs from Lattices
S. Kim (2018)
10.1145/3022227.3022327
On unconditionally binding code-based commitment schemes
K. Morozov (2017)
10.1007/978-3-319-70700-6_11
Zero-Knowledge Arguments for Lattice-Based PRFs and Applications to E-Cash
B. Libert (2017)
Lattice-Based Techniques for Accountable Anonymity: Composition of Abstract Stern's Protocols and Weak PRF with Efficient Protocols from LWR
R. Yang (2017)
10.1007/978-3-319-96881-0_24
Lattice-Based Zero-Knowledge Arguments for Integer Relations
B. Libert (2018)
Zero-Knowledge Proof for Knowledge of RLWE (Ring-Learning with Errors) Secret Keys
V SaraswathyR (2018)
10.1007/978-3-319-70700-6
Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part III
J. Kittler (2017)
10.1007/978-3-030-44223-1_15
Short Zero-Knowledge Proof of Knowledge for Lattice-Based Commitment
Yang Tao (2020)
Efficient Commitments and Zero-Knowledge Protocols from Ring-SIS with Applications to Lattice-based Threshold Cryptosystems
C. Baum (2016)
Privacy-preserving cryptography from pairings and lattices
Fabrice Mouhartem (2018)
10.1007/978-3-319-24174-6_16
Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings
F. Benhamouda (2015)
10.1007/978-3-662-53890-6_13
Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions
B. Libert (2016)
10.1007/978-3-319-98113-0_20
More Efficient Commitments from Structured Lattice Assumptions
C. Baum (2018)
10.1007/978-3-030-35199-1_13
RLWE-Based Zero-Knowledge Proofs for Linear and Multiplicative Relations
Ramiro Martínez (2019)
10.1007/s00145-019-09324-0
Multi-theorem Preprocessing NIZKs from Lattices
S. Kim (2019)
10.1007/978-3-319-76581-5_4
Attribute-based Signatures for Unbounded Circuits in the ROM and Efficient Instantiations from Lattices
A. Kaafarani (2018)
10.1016/j.tcs.2019.01.003
Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption
B. Libert (2019)
How to validate the secret of a Ring Learning with Errors (RLWE) key
J. Ding (2018)
Semantic Scholar Logo Some data provided by SemanticScholar