# Zero Knowledge Proofs From Ring-LWE

X. Xie, Rui Xue, Minqian Wang

Published 2013 · Mathematics, Computer Science

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)