Paper 2023/1411
zk-SNARKs from Codes with Rank Metrics
, Institute of Cryptography Science and Technology, Vietnam, Léonard de Vinci Pôle Universitaire, Research Center, Paris-La Défense, FranceAbstract
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
-
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},
note = {\url{https://eprint.iacr.org/2023/1411}},
url = {https://eprint.iacr.org/2023/1411}
}
