Zero Knowledge Proofs from Ring-LWE

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 ℤ

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 ℤ

q

computing

f

.