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

• URL: http://arxiv.org/abs/2502.11641v2
• Date: Tue, 18 Feb 2025 10:38:21 GMT
• Title: A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric
• Authors: Mladen Kovačević, Tatjana Grbić, Darko Čapko, Nemanja Nedić, Srdjan Vukmirović,
• Abstract summary: The distance between vectors is measured with respect to the Lee metric, rather than the more commonly used Hamming metric.<n>The purpose of this article is to describe a zero-knowledge proof for this variant of the problem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 describe a zero-knowledge proof for this variant of the problem.

Related papers

• USDs: A universal stabilizer decoder framework using symmetry [0.0]
  We show that a technique previously shown to be effective for the Toric code can be generalized to address the challenge of label degeneracy.<n>For the Color code, we achieved an improvement of approximately 0.8% in decoding accuracy at a physical error rate of 5%, while for the Golay code the accuracy increased by about 0.1%.
  arXiv  Detail & Related papers  (2026-01-21T12:06:17Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Is Compression Really Linear with Code Intelligence? [60.123628177110206]
  textitFormat Annealing is a lightweight, transparent training methodology designed to assess the intrinsic capabilities of pre-trained models equitably.<n>Our empirical results reveal a fundamental logarithmic relationship between measured code intelligence and bits-per-character (BPC)<n>Our work provides a more nuanced understanding of compression's role in developing code intelligence and contributes a robust evaluation framework in the code domain.
  arXiv  Detail & Related papers  (2025-05-16T16:59:14Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Existence and Characterisation of Bivariate Bicycle Codes [0.0]
  We show that BB codes provide compact quantum memory with low overhead and enhanced error correcting capabilities. We explore these codes by leveraging their ring structure and predict their dimension as well as conditions on their existence.
  arXiv  Detail & Related papers  (2025-02-24T11:04:15Z)
• Lattice-Based Vulnerabilities in Lee Metric Post-Quantum Cryptosystems [3.277820036565198]
  Post-quantum cryptography has gained attention due to the need for secure cryptographic systems in the face of quantum computing. We consider a generic Lee metric based McEliece type cryptosystem and evaluate its security against lattice-based attacks.
  arXiv  Detail & Related papers  (2024-09-24T12:21:33Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. This paper attempts to find a reduction from the decoding problem of linear codes, for which several hardness results exist. We characterize the efficiency of the reduction in terms of the parameters of the decoding and problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• A blindness property of the Min-Sum decoding for the toric code [3.543432625843538]
  Kitaev's toric code is one of the most prominent models for fault-tolerant quantum computation. Recent efforts have been devoted to improving the error correction performance of the toric code under message-passing decoding.
  arXiv  Detail & Related papers  (2024-06-21T08:28:31Z)
• Uncovering LLM-Generated Code: A Zero-Shot Synthetic Code Detector via Code Rewriting [78.48355455324688]
  We propose a novel zero-shot synthetic code detector based on the similarity between the original code and its LLM-rewritten variants.<n>Our results demonstrate a significant improvement over existing SOTA synthetic content detectors.
  arXiv  Detail & Related papers  (2024-05-25T08:57:28Z)
• Error Correction in Dynamical Codes [1.6317061277457001]
  We ask what is the general framework for a quantum error correcting code that is defined by a sequence of measurements. We develop an algorithm that tracks information about the error syndromes through the protocol and put that together to determine the distance of a dynamical code.
  arXiv  Detail & Related papers  (2024-03-07T02:47:21Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel [8.092763074723594]
  A novel method is introduced for designing high-code-rate single-IDS-correcting codewords through deep Levenshtein distance embedding.<n>A deep learning model is utilized to project the sequences into embedding vectors that preserve the Levenshtein distances between the original sequences.<n>This embedding space serves as a proxy for the complex Levenshtein domain within which algorithms for codeword search and segment correcting is developed.
  arXiv  Detail & Related papers  (2023-12-20T02:22:54Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• Conservation laws and quantum error correction: towards a generalised matching decoder [2.1756081703276]
  We explore decoding algorithms for the surface code, a prototypical quantum low-density parity-check code. The decoder works by exploiting underlying structure that arises due to materialised symmetries among surface-code stabilizer elements. We propose a systematic way of constructing a minimum-weight perfect-matching decoder for codes with certain characteristic properties.
  arXiv  Detail & Related papers  (2022-07-13T18:00:00Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• A Transformer-based Approach for Source Code Summarization [86.08359401867577]
  We learn code representation for summarization by modeling the pairwise relationship between code tokens. We show that despite the approach is simple, it outperforms the state-of-the-art techniques by a significant margin.
  arXiv  Detail & Related papers  (2020-05-01T23:29:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.