Cryptology ePrint Archive: Report 2020/1472

Enhancing Code Based Zero-knowledge Proofs using Rank Metric

Emanuele Bellini and Philippe Gaborit and 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.

Category / Keywords: cryptographic protocols / Post Quantum, Code-based cryptography, Rank metric, Zero-knowledge proof, Identification protocol, Commitment scheme

Original Publication (in the same form): Springer Nature Switzerland AG 2020 S. Krenn et al. (Eds.): CANS 2020, LNCS 12579, pp. 123, 2020.

Date: received 23 Nov 2020

Contact author: alexandros hasikos at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201124:113223 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]