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,mi, ...,mt 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 Z_q, our protocol has amortized communication complexity O(λ · |f|) with exponentially small soundness in security parameter λ, where |f| is the size of the circuit in Z_q computing f.
展开▼
机译：零知识证明是一个非常基本且重要的原语，它使证明者可以证明某些陈述而无需透露其他任何内容。最近，Jain等人。提出了一种非常有效的零知识证明，以基于噪声的学习奇偶性（LPN）问题来证明位上的多项式关系（Asiacrypt'12）。在这项工作中，我们通过适应Ling等人提出的技术，扩展了其安全性基于具有错误的环学习（RLWE）问题的类似构造。 （PKC'13）。具体来说，我们展示了一个简单的零知识知识证明（Σ-协议）的承诺值，并证明了底层环中的任何多项式关系。 IE。证明对于任何多项式f满足m = f（m_1，...，m_t）的承诺环元素m，mi，...，mt与其他现有的Σ协议相比，提取的证人（误差向量）的长度恒定时间仅比证明者所拥有的恒定时间小。当将环形元素表示为Z_q中的元素时，我们的协议具有摊销的通信复杂度O（λ·| f |），其安全性参数λ中的指数健壮性小，其中| f |是Z_q计算f中的电路大小。
展开▼
