[Resource Topic] 2019/1486: RLWE-based Zero-Knowledge Proofs for linear and multiplicative relations

Welcome to the resource topic for 2019/1486

RLWE-based Zero-Knowledge Proofs for linear and multiplicative relations

Authors: Ramiro Martínez, Paz Morillo


We present efficient Zero-Knowledge Proofs of Knowledge (ZKPoK) for linear and multiplicative relations among secret messages hidden as Ring Learning With Errors (RLWE) samples. Messages are polynomials in \mathbb{Z}_q[x]/\left<x^{n}+1\right> and our proposed protocols for a ZKPoK are based on the celebrated paper by Stern on identification schemes using coding problems (Crypto’93). Our 5-move protocol achieves a soundness error slightly above 1/2 and perfect Zero-Knowledge. As an application we present Zero-Knowledge Proofs of Knowledge of relations between committed messages. The resulting commitment scheme is perfectly binding with overwhelming probability over the choice of the public key, and computationally hiding under the RLWE assumption. Compared with previous Stern-based commitment scheme proofs we decrease computational complexity, improve the size of the parameters and reduce the soundness error of each round.

ePrint: https://eprint.iacr.org/2019/1486

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .