Paper 2019/1486

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

Ramiro Martínez and Paz Morillo

Abstract

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.

Note: revised typo in DOI

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. IMACC 2019
DOI
10.1007/978-3-030-35199-1_13
Keywords
zero-knowledge proofs of knowledgecommitment schemering learning with errors
Contact author(s)
ramiro martinez @ upc edu
History
2020-09-02: revised
2019-12-30: received
See all versions
Short URL
https://ia.cr/2019/1486
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1486,
      author = {Ramiro Martínez and Paz Morillo},
      title = {RLWE-based Zero-Knowledge Proofs for linear and multiplicative relations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1486},
      year = {2019},
      doi = {10.1007/978-3-030-35199-1_13},
      note = {\url{https://eprint.iacr.org/2019/1486}},
      url = {https://eprint.iacr.org/2019/1486}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.