PaperlayerView exact revision on arXiv

Source-linked AI summary

A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes

Frederick Dehmel, Shilun Li

arXiv:2609.02943v1cs.CRcs.ITmath.IT

TL;DR

Public-key PRCs face an open deletion-tolerance question when channels can inspect both the public key and transmitted codeword. The paper uses LCS-based collisions to prove impossibility thresholds for single-output and bounded-list decoding, including a binary threshold above 0.207334008.

  • Problem

    How much deletion can a fixed-alphabet public-key PRC tolerate when a channel can inspect the public key and transmitted codeword, unlike the better-studied substitution setting?

    Source: §1 · p. 1

  • Method

    The collision argument maps independently sampled codewords to a common subsequence, extending the attack to L + 1 messages against lists of size L.

    Source: §1.1 · p. 2

  • Results

    For binary PRCs, every δ > 0.207334008 is ruled out, and fixed-list-size thresholds are 1 − γ_2^(L+1) when there are at least L + 1 messages.

    Source: §1.1 · p. 2, §6 · p. 14

  • Takeaways & Limitations

    Because γ_2^(m) = 1/2 + Θ(1/√m), the fixed-list-size thresholds approach 1/2 as list size grows.

    Source: §1.1 · p. 2

    The open key-independent-channel deletion threshold remains unresolved in the interval (1 − γ2, 1/2).

    Source: §6 · p. 14

Abstract

from arXiv · show

A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings. We study public-key PRCs over fixed alphabets against adversarial deletions, where the deletion channel may both depend on the public encoding key and the transmitted codeword. Let $\gamma_q^{\mathrm{LCS}}$ denote the asymptotic normalised longest-common-subsequence length of two independent uniform $q$-ary strings. We prove that for every fixed $q\ge2$ no multi-message public-key PRC with a single-output decoder is robust against all such $\delta$-deletion channels for any $\delta>1-\gamma_q^{\mathrm{LCS}}$. For $q=2$, the current rigorous bound $\gamma_2\ge0.792665992$ rules out every constant $\delta>0.207334008$. The proof uses pseudorandomness only to transfer an LCS event from uniform strings to independently sampled codewords and therefore also the resulting collision argument is information-theoretic and requires no secret key. We also extend the argument to list decoding: for every fixed constant $L$, provided the message space contains at least $L+1$ messages, no such PRC with output lists of size at most $L$ is robust for $\delta>1-\gamma_2^{(L+1)}$. Since $\gamma_2^{(m)}=1/2+\Theta(1/\sqrt m)$, these thresholds approach $1/2$. Our bounds are specific to public-key-dependent adversarial channels and do not apply to oblivious edit channels.

1 Introduction

The paper asks how much deletion a fixed-alphabet public-key PRC can tolerate when channels can inspect both the public key and transmitted codeword. It gives LCS-based impossibility thresholds for single-output and bounded-list decoders, with scope distinct from oblivious-channel results.

1 Introduction

  • The deletion question matters because removed symbols destroy positional synchronization, so length-preserving substitution arguments do not apply directly.The study concerns channels that can access the public key and transmitted codeword, but not the secret key.Source: §1 · p. 1

1.1 Our results

  • For every fixed alphabet size q ≥2, no multi-bit, undetectable public-key PRC with a single-valued decoder is robust against Cpk; in binary, impossibility holds for every δ > 0.207334008.q is the asymptotic normalised LCS length of two uniform q-ary strings.Source: §1.1 · p. 2
  • Two independently sampled codewords with a sufficiently long LCS enable public-key-only deletion channels to produce coincident outputs, limiting at least one decoding success probability.The construction uses a public sampler and does not choose the transmitted encoding randomness, unlike the chosen-codeword adaptive game.Source: §1.1 · p. 2
  • The collision argument also rules out binary list decoding of size L for δ > 1 − γ_2^(L+1), when the message space contains at least L + 1 messages.The attack maps L + 1 codewords to a common subsequence that a list of size L cannot decode to all those messages.Source: §1.1 · p. 2

1.2 Related work

  • Prior positive edit-robust PRC results use growing alphabets or oblivious channels, unlike this fixed-alphabet, public-key-dependent, constant-fraction deletion setting.The related work also distinguishes the paper’s deletion setting from substitution-based separations.Source: §1.2 · pp. 2–3

2 Preliminaries and combinatorial input

The preliminaries define the public-key-dependent deletion setting and establish the LCS event used by the impossibility argument. Pseudorandomness transfers that event from uniform strings to independently sampled codewords.

2.1 Adversarial channel models

  • A public-key-dependent channel may base deletions on the public key and input word, but cannot read the secret key and must act on a freshly sampled codeword.The channel is fixed before key generation; key-independent channels ignore the public key, while oblivious channels commit independently of both key and word.Source: §2.1 · p. 3

2.2 Definitions and notation

  • A PRC is a keyed encoding scheme with a single-valued decoder; multi-bit codes have at least two messages, and standard soundness is omitted because it is unused.The syntax bounds encoding and message lengths polynomially in the security parameter.Source: §2.2 · p. 4

2.3 LCS concentration and transfer

  • For independent uniform binary strings, the probability of LCS at least ρn is bounded below for each fixed ρ < γ2, and pseudorandomness transfers this event to independently sampled codewords.The transfer uses a polynomial-time LCS-threshold test and is the main theorem’s sole use of pseudorandomness.Source: §2.3 · pp. 5–6

3 Main collision lemma and deletion ceiling

The collision lemma turns long common subsequences among independently sampled codewords into two public-key-dependent deletion channels with coincident outputs. Applying the lemma to pseudorandom codes yields fixed-alphabet and binary deletion ceilings.

3.1 Collision lemma

  • If independently sampled codewords have LCS at least ρn except with probability ν, then for every δ > 1 − ρ, two public-key-dependent deletion channels force at least one decoding success probability to be at most 1/2 + ν/2.The argument requires a public sampler and a single-valued decoder, but not pseudorandomness.Source: §3.1 · p. 6
  • The paired channels use a canonical common subsequence; on the long-LCS event their outputs coincide, while single-valued decoding prevents both distinct messages from decoding successfully.The public-sampler construction preserves each channel’s standalone distribution under the coupling.Source: §3.1 · p. 7

3.2 Binary adversarial-deletion ceiling

  • For binary PRCs, every constant δ > 0.207334008 is ruled out using the current bound γ2 ≥ 0.792665992.For sufficiently long block lengths, the cited result also gives the stronger winning-probability bound indicated in the theorem passage.Source: §3.2 · p. 8
  • For each fixed alphabet size q ≥ 2, no multi-bit, undetectable public-key PRC over Σq with a single-valued decoder is robust against Cpk.The concentration argument is unchanged, and the transfer argument also applies over Σq.Source: §3.2 · p. 8
  • The chosen-codeword adaptive deletion result uses two sampled encodings and a common subsequence, causing a uniform choice of message to fail decoding with conditional probability at least 1/2 on the collision event.For n = ω(log λ), the collision event holds with probability 1 − negl(λ).Source: §3.2 · p. 9

4 List decoding

The collision argument extends to list decoding: with at least L+1 messages, binary public-key PRCs with lists of size at most L are not robust above the LCS-based deletion threshold. The proof couples channels to a shared common subsequence, where at most L messages can decode successfully.

4 List decoding

  • A permutation-invariant longest-common-subsequence rule supplies the shared output, and pseudorandomness transfers the uniform-string event bounds to independently sampled codewords.The rule and witnessing embeddings are computable in O(nm) time for constant m.Source: §4 · pp. 10–11
  • For constant L and at least L+1 messages, no binary public-key PRC with lists of size at most L is robust for δ > 1−γ(L+1).The theorem considers public-key-dependent deletion channels.Source: §4 · p. 11
  • For n=ω(log λ), the resulting average decoding-success bound sharpens to 1−1/(L+1)+negl(λ).This follows from the theorem’s sharper bound when the LCS-event probability is negligible.Source: §4 · pp. 11–12
  • On the common-subsequence event, all coupled channels output the same string, whose list contains at most L of the L+1 messages; outside it, at most L+1 successes are possible.This event split bounds the sum of the standalone success probabilities.Source: §4 · p. 12

5 Scope of the collision argument

The collision argument has scope limits tied to message count, alphabet size, block length, and channel access. Separate bounds also cover short blocks and key-independent channels at deletion fractions of one half or more.

5 Scope of the collision argument

  • The collision argument requires distinct messages and public-key-dependent resampling.Its scope therefore depends on having distinct messages to collide.Source: §5 · p. 12
  • When k = 0, the two decoding events concern the same message, so the collision argument yields no zero-bit impossibility.The section notes this is consistent with known zero-bit binary PRCs for random deletions [CG24].Source: §5 · p. 12
  • The independent-channel-tape comparison does not constrain marginal-preserving couplings of the channel tapes.For δ < 1/2, the comparison bounds output agreement when channel tapes are independent of encoder tapes.Source: §5 · p. 12
  • For n = O(log λ), a binary multi-bit public-key PRC with a single-valued decoder cannot be robust even against the identity channel.Repeated queries estimate the encoding distributions’ total variation distance: it is at least 1/2 in the real experiment but zero in the ideal experiment.Source: §5 · pp. 12–13
  • For binary multi-bit undetectable public-key PRCs with a single-valued decoder, no constant δ ≥ 1/2 is robust against key-independent channels.The section settles the boundary cases directly: short blocks fail under the identity channel, while above one half key-independent channels suffice.Source: §5 · pp. 12–13
  • The fixed-alphabet ceiling assumes q is independent of λ, and the pairwise-LCS method weakens as q grows.It therefore does not cover alphabets growing with the security parameter, such as those of Golowich and Moitra [GM24].Source: §5 · p. 13

6 Conclusion and open problems

The conclusion gives fixed-alphabet and list-decoding impossibility bounds for public-key-dependent deletions. It leaves sharper finite-m bounds and other channel models as open problems.

6 Conclusion and open problems

  • For q = 2, current bounds rule out every δ > 0.207334008; for each fixed list size L, the same collision argument gives threshold 1 − γ(L+1).The list-size threshold applies when the message space contains at least L + 1 elements for all sufficiently large λ.Source: §6 · p. 14
  • For fixed L, the collision argument gives threshold 1 − γ_2^(L+1) when the message space contains at least L + 1 elements.The proof transfers random-string LCS behavior to codewords and maps distinct messages onto a common subsequence.Source: §6 · p. 14
  • Open problems include the key-independent deletion threshold in (1 − γ_2, 1/2), sharper finite-m bounds on γ(m), and deletion bounds for other natural channel models.Source: §6 · p. 14

AI Disclosure

The authors disclose using ChatGPT/Codex 5.5 for wording and proof checking, and for ideation and discussion of the list-decoding extension.

AI Disclosure

  • ChatGPT/Codex 5.5 assisted with wording and proof checking.Source: AI Disclosure · p. 14
  • The tool was also used in ideation and discussion of the list-decoding extension in section 4.Source: AI Disclosure · p. 14
  • The authors take full responsibility for the manuscript’s correctness, originality, and accuracy.Source: AI Disclosure · p. 14

A Independent-execution comparison

The appendix compares independent channel-tape executions with the collision argument’s coupled executions. Under its stated block-length and deletion conditions, independent executions produce equal outputs only negligibly often.

A Independent-execution comparison

  • For a fixed string z, its probability of being a subsequence of a uniform binary string depends on its length, not its bits; for length above n/2, Hoeffding’s inequality gives a tail bound.Greedy matching makes the number of consumed bits a sum of independent Geom(1/2) variables.Source: A Independent-execution comparison · p. 15
  • The bound assumes channel tapes are independent of the encoder tapes, though the two channel tapes may otherwise be arbitrarily coupled.Each tape retains its usual marginal distribution conditional on the public key.Source: A Independent-execution comparison · p. 15
  • For n = ω(log λ), independent-execution channel outputs agree only negligibly often for every constant δ < 1/2.Source: A Independent-execution comparison · p. 16
  • The proof contains output collision in the event that one channel output is a subsequence of the other independently sampled codeword, then transfers that event by pseudorandomness.Source: A Independent-execution comparison · p. 16
Loading 2609.02943v1…