Alkaid: Resilience to Edit Errors in Provably Secure Steganography via Distance-Constrained Encoding

• URL: http://arxiv.org/abs/2603.06169v1
• Date: Fri, 06 Mar 2026 11:25:11 GMT
• Title: Alkaid: Resilience to Edit Errors in Provably Secure Steganography via Distance-Constrained Encoding
• Abstract summary: We propose Alkaid, a provably secure steganographic scheme resilient to edit errors via distance-constrained encoding.<n>Alkaid integrates the minimum distance decoding principle directly into the encoding process by enforcing a strict lower bound.<n>Experiments demonstrate that Alkaid achieves decoding success rates of 99% to 100% across diverse error channels.
• Score: 28.136825414024273
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While provably secure steganography provides strong concealment by ensuring stego carriers are indistinguishable from natural samples, such systems remain vulnerable to real-world edit errors (e.g., insertions, deletions, substitutions) because their decoding depends on perfect synchronization and lacks error-correcting capability. To bridge this gap, we propose Alkaid, a provably secure steganographic scheme resilient to edit errors via distance-constrained encoding. The key innovation integrates the minimum distance decoding principle directly into the encoding process by enforcing a strict lower bound on the edit distance between codewords of different messages. Specifically, if two candidate codewords violate this bound, they are merged to represent the same message, thereby guaranteeing reliable recovery. While maintaining provable security, we theoretically prove that Alkaid offers deterministic robustness against bounded errors. To implement this scheme efficiently, we adopt block-wise and batch processing. Extensive experiments demonstrate that Alkaid achieves decoding success rates of 99\% to 100\% across diverse error channels, delivers a payload of 0.2 bits per token for high embedding capacity, and maintains an encoding speed of 6.72 bits per second, significantly surpassing state-of-the-art (SOTA) methods in robustness, capacity, and efficiency.

Related papers

• Escaping Confidence Trap: Evolutionary Decoding for Mathematical Reasoning in Diffusion LLMs [69.52853771994451]
  We analyze the decoding trajectories of LLaDA 2.0 and identify a recurring diffusion confidence trap.<n>We propose Evolutionary Decoding, a training-free test-time scaling framework that views diffusion decoding as an evolutionary process.
  arXiv  Detail & Related papers  (2026-08-01T11:48:25Z)
• Follow the Latent Roadmap: Navigating Revocable Decoding for Diffusion LLMs with Anchor Tokens [22.687236570529844]
  We propose ASRD (Anchor Supervised Revocable Decoding), a training-free framework that operates within the embedding space.<n>We show that ASRD outperforms recent remasking baselines, achieving accuracy improvements of up to 6.4% while accelerating inference throughput by up to 7.2times$.
  arXiv  Detail & Related papers  (2026-06-15T15:23:47Z)
• SecureForge: Finding and Preventing Vulnerabilities in LLM-Generated Code via Prompt Optimization [61.91729298584227]
  We introduce SecureForge, an automated pipeline that audits security risks of frontier models and produces auditing-informed secure system prompts.<n>SecureForge first identifies benign prompts that produce statically detectable vulnerabilities, and then amplifies them into a large synthetic prompt corpus of diverse scenarios.<n>On frontier models, SecureForge yields a statistically significant improvement in both unit test success and output security, with output vulnerabilities reduced by up to 48%.
  arXiv  Detail & Related papers  (2026-05-08T18:40:47Z)
• Anchored Decoding: Provably Reducing Copyright Risk for Any Language Model [99.16364381244445]
  Modern language models (LMs) tend to memorize portions of their training data and emit verbatim spans.<n>We propose Anchored Decoding, a plug-and-play inference-time method for suppressing verbatim copying.<n>We evaluate our methods across six model pairs on long-form evaluations of copyright risk and utility.
  arXiv  Detail & Related papers  (2026-02-06T19:00:14Z)
• STEAD: Robust Provably Secure Linguistic Steganography with Diffusion Language Model [71.35577462669856]
  We propose a robust, provably secure linguistic steganography with diffusion language models (DLMs)<n>We introduce error correction strategies, including pseudo-random error correction and neighborhood search correction, during steganographic extraction.
  arXiv  Detail & Related papers  (2026-01-21T08:58:12Z)
• Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding [58.92526489742584]
  We propose provably lossless.<n> verification method that significantly boosts the expected number of accepted tokens.<n>We show that HSD yields consistent improvements in acceptance rates across diverse model families and benchmarks.
  arXiv  Detail & Related papers  (2026-01-09T11:10:29Z)
• Deferred Commitment Decoding for Diffusion Language Models with Confidence-Aware Sliding Windows [33.361153168706444]
  We propose Deferred Commitment Decoding (DCD) as a training-free decoding strategy.<n>DCD maintains a confidence-aware sliding window over masked tokens, resolving low-uncertainty tokens early while deferring high-uncertainty tokens until sufficient contextual evidence becomes available.<n>Experiments show that DCD improves generation accuracy by 1.39% with comparable time on average compared to fixed block-based diffusion methods, with the most significant improvement reaching 9.0%.
  arXiv  Detail & Related papers  (2026-01-05T12:57:33Z)
• Towards Better Code Generation: Adaptive Decoding with Uncertainty Guidance [42.737012213197865]
  AdaDec is an adaptive decoding framework that employs a lookahead-based, uncertainty-aware pause-and-rerank mechanism.<n>AdaDec achieves up to 20.9% absolute gains in Pass@1 accuracy compared with greedy decoding.<n>By applying reranking only when necessary, AdaDec reduces computational overhead and latency, enhancing efficiency alongside reliability.
  arXiv  Detail & Related papers  (2025-06-10T16:49:46Z)
• Fault-tolerant correction-ready encoding of the [[7,1,3]] Steane code on a 2D grid [0.0]
  We investigate various correction-ready encoding methods to fault-tolerantly prepare the zero-logical state of the Steane code on a 2D grid.<n>We show that parity-check encoding with a few Flag-Bridge qubits outperforms verification-based encoding by achieving lower error rates.<n>Surprisingly, compared to the resource-intensive Steane error correction, this low-overhead method still offers a practical advantage in noisy settings.
  arXiv  Detail & Related papers  (2025-04-01T18:00:30Z)
• MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs [50.41998220099097]
  Data errors, corruptions, and poisoning attacks during training pose a major threat to the reliability of modern AI systems.<n>We introduce MIBP-Cert, a novel certification method based on mixed-integer bilinear programming (MIBP)<n>By computing the set of parameters reachable through perturbed or manipulated data, we can predict all possible outcomes and guarantee robustness.
  arXiv  Detail & Related papers  (2024-12-13T14:56:39Z)
• An efficient combination of quantum error correction and authentication [1.1602089225841632]
  We study whether it can be done more efficiently by combining the two functionalities in a single code. We show that the threshold code needs polylogarithmically fewer qubits to achieve the same level of security and robustness.
  arXiv  Detail & Related papers  (2022-11-17T17:25:39Z)
• Autoregressive Belief Propagation for Decoding Block Codes [113.38181979662288]
  We revisit recent methods that employ graph neural networks for decoding error correcting codes. Our method violates the symmetry conditions that enable the other methods to train exclusively with the zero-word. Despite not having the luxury of training on a single word, and the inability to train on more than a small fraction of the relevant sample space, we demonstrate effective training.
  arXiv  Detail & Related papers  (2021-01-23T17:14:55Z)
• Robust Encodings: A Framework for Combating Adversarial Typos [85.70270979772388]
  NLP systems are easily fooled by small perturbations of inputs. Existing procedures to defend against such perturbations provide guaranteed robustness to worst-case attacks. We introduce robust encodings (RobEn) that confer guaranteed robustness without making compromises on model architecture.
  arXiv  Detail & Related papers  (2020-05-04T01:28:18Z)

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.