Paper 2023/1411

zk-SNARKs from Codes with Rank Metrics

Xuan-Thanh Do, Institute of Cryptography Science and Technology, Vietnam
Dang-Truong Mac
Quoc-Huy Vu, Léonard de Vinci Pôle Universitaire, Research Center, Paris-La Défense, France
Abstract

Succinct non-interactive zero-knowledge arguments of knowledge (zk-SNARKs) are a type of non-interactive proof system enabling efficient privacy-preserving proofs of membership for NP languages. A great deal of works has studied candidate constructions that are secure against quantum attackers, which are based on either lattice assumptions, or post-quantum collision-resistant hash functions. In this paper, we propose a code-based zk-SNARK scheme, whose security is based on the rank support learning (RSL) problem, a variant of the random linear code decoding problem in the rank metric. Our construction follows the general framework of Gennaro et al. (CCS'18), which is based on square span programs (SSPs). Due to the fundamental differences between the hardness assumptions, our proof of security cannot apply the techniques from the lattice-based constructions, and indeed, it distinguishes itself by the use of techniques from coding theory. We also provide the scheme with a set of concrete parameters.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. IMA International Conference on Cryptography and Coding 2023
Keywords
Code-based CryptographyRank support learning problemSquare span programszk-SNARKs
Contact author(s)
thanhkhtn @ gmail com
macdangtruong258 @ gmail com
qhvu @ ens fr
History
2023-09-24: approved
2023-09-19: received
See all versions
Short URL
https://ia.cr/2023/1411
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/1411,
      author = {Xuan-Thanh Do and Dang-Truong Mac and Quoc-Huy Vu},
      title = {zk-{SNARKs} from Codes with Rank Metrics},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1411},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1411}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.