A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric

Mladen Kovačević; Tatjana Grbić; Darko Čapko; Nemanja Nedić; Srđan Vukmirović

Paper 2025/1373

A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric

Mladen Kovačević

, University of Novi Sad, Serbia

Tatjana Grbić, University of Novi Sad, Serbia

Darko Čapko, University of Novi Sad, Serbia, Ethernal, Novi Sad, Serbia

Nemanja Nedić, University of Novi Sad, Serbia, Ethernal, Novi Sad, Serbia

Srđan Vukmirović, University of Novi Sad, Serbia, Ethernal, Novi Sad, Serbia

Abstract

The syndrome decoding problem is one of the NP-complete problems lying at the foundation of code-based cryptography. The variant thereof where the distance between vectors is measured with respect to the Lee metric, rather than the more commonly used Hamming metric, has been analyzed recently in several works due to its potential relevance for building more efficient code-based cryptosystems. The purpose of this article is to present a zero-knowledge proof of knowledge for this variant of the problem.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. arxiv
DOI: 10.48550/arXiv.2502.11641
Keywords: zero-knowledge proof code-based cryptography post-quantum cryptography syndrome decoding Lee metric
Contact author(s): kmladen @ uns ac rs
History: 2025-07-30: approved; 2025-07-28: received; See all versions
Short URL: https://ia.cr/2025/1373
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1373,
      author = {Mladen Kovačević and Tatjana Grbić and Darko Čapko and Nemanja Nedić and Srđan Vukmirović},
      title = {A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1373},
      year = {2025},
      doi = {10.48550/arXiv.2502.11641},
      url = {https://eprint.iacr.org/2025/1373}
}