Projective Space Stern Decoding and Application to SDitH

• URL: http://arxiv.org/abs/2312.02607v1
• Date: Tue, 5 Dec 2023 09:33:15 GMT
• Title: Projective Space Stern Decoding and Application to SDitH
• Authors: Kevin Carrier, Valérian Hatey, Jean-Pierre Tillich,
• Abstract summary: We show that here standard decoding algorithms for generic linear codes over a finite field can speed up by a factor which is essentially the size of the finite field. We apply this technique to SDitH and show that the parameters of both the original submission and the updated version fall short of meeting the security requirements asked by the NIST.
• Score: 0.1755623101161125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that here standard decoding algorithms for generic linear codes over a finite field can speeded up by a factor which is essentially the size of the finite field by reducing it to a low weight codeword problem and working in the relevant projective space. We apply this technique to SDitH and show that the parameters of both the original submission and the updated version fall short of meeting the security requirements asked by the NIST.

Related papers

• Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement [0.2578242050187029]
  We study fundamental limitations of the generic Quantum Approximate Optimization Algorithm (QAOA) on constrained problems.<n>We present a provable route to exponential improvements via constraint embedding.<n>Thanks to the problem algorithm co design in the kernel construction, the techniques and guarantees extend beyond permutations to a broad class of NP-Hard constrained optimization problems.
  arXiv  Detail & Related papers  (2025-11-21T14:04:01Z)
• MPCitH-based Signatures from Restricted Decoding Problems [16.371060416568195]
  We embed the restricted decoding problem within MPCitH and VOLE-in-the-Head frameworks.<n>We propose a structurally simple modeling that achieves competitive signature sizes.<n>We obtain signature sizes comparable to the smallest MPCitH-based candidates in the NIST competition.
  arXiv  Detail & Related papers  (2025-10-13T10:09:32Z)
• 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)
• Style Quantization for Data-Efficient GAN Training [18.40243591024141]
  Under limited data setting, GANs often struggle to navigate and effectively exploit the input latent space. We propose textitSQ-GAN, a novel approach that enhances consistency regularization. Experiments demonstrate significant improvements in both discriminator robustness and generation quality.
  arXiv  Detail & Related papers  (2025-03-31T16:28:44Z)
• A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric [0.0]
  The distance between vectors is measured with respect to the Lee metric, rather than the more commonly used Hamming metric. The purpose of this article is to describe a zero-knowledge proof for this variant of the problem.
  arXiv  Detail & Related papers  (2025-02-17T10:35:18Z)
• Almost Linear Decoder for Optimal Geometrically Local Quantum Codes [8.837439668920288]
  We show how to achieve geometrically local codes that maximize both the dimension and the distance, as well as the energy barrier of the code.<n>We demonstrate the existence of a finite threshold error rate under the code capacity noise model using a minimum weight perfect matching decoder.
  arXiv  Detail & Related papers  (2024-11-05T09:15:06Z)
• 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)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• 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)
• Differentiable VQ-VAE's for Robust White Matter Streamline Encodings [33.936125620525]
  Autoencoders have been proposed as a dimension-reduction tool to simplify the analysis streamlines in a low-dimensional latent spaces. We propose a novel Differentiable Vector Quantized Variational Autoencoder, which ingests entire bundles of streamlines as single data-point.
  arXiv  Detail & Related papers  (2023-11-10T17:59:43Z)
• Ensuring Topological Data-Structure Preservation under Autoencoder Compression due to Latent Space Regularization in Gauss--Legendre nodes [0.0]
  We prove that regularised autoencoders ensure a one-to-one re-embedding of the initial data manifold to its latent representation. This observation extends through the classic FashionMNIST dataset up to real world encoding problems for MRI brain scans.
  arXiv  Detail & Related papers  (2023-09-15T07:58:26Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• 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)
• Autoregressive Linguistic Steganography Based on BERT and Consistency Coding [17.881686153284267]
  Linguistic steganography (LS) conceals the presence of communication by embedding secret information into a text. Recent algorithms use a language model (LM) to generate the steganographic text, which provides a higher payload compared with many previous arts. We propose a novel autoregressive LS algorithm based on BERT and consistency coding, which achieves a better trade-off between embedding payload and system security.
  arXiv  Detail & Related papers  (2022-03-26T02:36:55Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.