Paper 2020/1472

Enhancing Code Based Zero-knowledge Proofs using Rank Metric

Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, and Victor Mateu

Abstract

The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et. al in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Springer Nature Switzerland AG 2020 S. Krenn et al. (Eds.): CANS 2020, LNCS 12579, pp. 1–23, 2020.
DOI
10.1007/978-3-030-65411-5_28
Keywords
Post QuantumCode-based cryptographyRank metricZero-knowledge proofIdentification protocolCommitment scheme
Contact author(s)
alexandros hasikos @ gmail com
History
2020-11-24: received
Short URL
https://ia.cr/2020/1472
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1472,
      author = {Emanuele Bellini and Philippe Gaborit and Alexandros Hasikos and Victor Mateu},
      title = {Enhancing Code Based Zero-knowledge Proofs using Rank Metric},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1472},
      year = {2020},
      doi = {10.1007/978-3-030-65411-5_28},
      note = {\url{https://eprint.iacr.org/2020/1472}},
      url = {https://eprint.iacr.org/2020/1472}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.