Source-linked AI summary
Rate 1/5 Non-Malleable Codes against Entangled Split-State Tampering
Naresh Goud Boddu
TL;DR
Prior quantum-secure two-split codes protected every classical message only at vanishing inverse-polynomial rate, while rate approaching 1/5 was known only for uniform messages [ABJ24; BBJ23, Section 7]. This paper adapts the permutation-based construction with fresh padding and proves a worst-case reduction, achieving rate at least 1/5−ξ with perfect correctness and error 2^-n^Ω(1).
Problem
Prior quantum-secure two-split NMCs protected every classical message at vanishing inverse-polynomial rate [ABJ24], or achieved rate approaching 1/5 only for a uniform message [BBJ23, Section 7], leaving their combination unresolved.
Source: §1.2 · p. 3Method
The construction retains BBJ’s permutation-based architecture but encodes a prescribed message with fresh uniform padding and uses a new worst-case security reduction [BBJ23, Section 7].
Source: §1.3 · p. 4Results
For every sufficiently small fixed ξ > 0 and sufficiently large first-share length n, the code has rate at least 1/5−ξ, perfect correctness, and error 2^-n^Ω(1) against entangled two-split tampering.
Source: §1.2 · p. 3Takeaways & Limitations
The construction resolves the constant-rate question for worst-case classical messages in the entangled two-split-state model.
Source: §1.2 · p. 3The stated BBJ instantiation does not improve Li’s exponential classical error [Li23].
Source: §7.3 · p. 24
Abstract
from arXiv · showhide
We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations with arbitrary pre-shared entanglement. For every sufficiently small fixed $\xi>0$ and all sufficiently large first-share lengths $n$, the codes have rate at least $1/5-\xi$, perfect correctness, and error $2^{-n^{\Omega(1)}}$. Security holds for every message, with a single message-independent simulator for each attack. This resolves the constant-rate question for worst-case classical messages in the entangled two-split-state model. Our construction builds on the permutation-based two-split construction of Batra, Boddu, and Jain, which achieves rate approaching $1/5$ for uniformly random messages. We retain their architecture but replace the uniform message input to the permutation with a prescribed message concatenated with fresh uniform padding. Our main contribution is a worst-case security reduction for this modification.
1 Introduction
The introduction presents a classical two-split non-malleable code with worst-case message security against entangled local quantum tampering, and situates the prescribed-message reduction within prior work. It distinguishes this setting from post-quantum interactive non-malleability and outlines the paper’s structure.
1.1 Non-malleability under local access
- A non-malleable code uses public encoding and decoding, and requires each allowed attack to admit one message-independent output distribution; split-state attacks act locally on two shares without communicating.The paper’s messages and codewords remain classical, while the local quantum tampering operations may share arbitrary pre-existing entanglement [ABJ24].Source: §1.1 · p. 2
1.2 Our result: worst-case security at rate approaching one-fifth
- For every sufficiently small fixed ξ > 0 and all sufficiently large n, the code achieves rate at least 1/5 − ξ, perfect correctness, and error 2^-n^{Ω(1)} against entangled two-split tampering.The encoder adds fresh uniform padding to the prescribed message within the BBJ permutation-based architecture; for an encoder with error η, the reduction gives O(√η + 2^(-(r-d)/5)) error when r > d. A balanced-share corollary approaches rate 1/8 with the same security error.Source: §1.2 · p. 3
1.3 Closest comparison: what is inherited from BBJ, and what changes
- BBJ’s uniform-message proof relies on permuting a uniform ciphertext, while conditioning on a fixed message can amplify average-case error by 2^ℓ.The authors instead apply BBJ before recovering the ciphertext and use a deficit-based comparison; padding supplies residual randomness, while a continuation identity and permutation second moment yield the worst-case statement.Source: §1.3 · p. 4
1.4 Proof overview I: classical adversaries
- For classical tampering, the proof handles fixed-message conditioning by comparing mean-one scaled distributions through their average deficit rather than their largest likelihood ratio.Padding makes the average deficit small, avoiding the factor-q cost of conditioning on the rare message event.Source: §1.4 · pp. 4–5
1.5 Proof overview II: extending the comparison to entangled adversaries
- Because an entangled attack correlates the right auxiliary register with the other component, selecting an outcome can change its conditional state; scalar probabilities are insufficient, so the complete conditional quantum state must be reconstructed.The continuation map composes to identity on all matrices and survives tensoring with the left attacker’s register E1. The error is O(√η + 2^(-(r-d)/5)), and the one-simulator-for-all-messages quantifier is unchanged.Source: §1.5 · pp. 5–7
1.6 Related work: rate, error, and adversary strength
- Li [Li23, Theorem 1.14] gives efficient constant-rate classical two-split coding with error 2^-Ω(ℓ), which this work’s stretched-exponential error does not improve.The classical balanced two-split capacity 1/2 is existential [CG14a], while BBJ’s near-rate-1/3 worst-case construction uses three splits [BBJ23].Source: §1.6 · p. 7
1.7 Historical development and broader context of non-malleability
- The reduction handles prescribed-message encoding within BBJ’s quantum-secure permutation architecture [BBJ23].The introduction places this approach within information-theoretic non-malleable coding and related construction work.Source: §1.7 · p. 8
- The result keeps messages and codewords classical while allowing arbitrary local quantum computation with pre-shared entanglement in the split-state model.This setting is distinct from post-quantum interactive non-malleability and from work on quantum messages or tamper detection under additional entanglement restrictions.Source: §1.7 · p. 9
- Section 2 gives preliminaries and the BBJ guarantee; Section 3 presents the construction and finite-parameter theorem, Sections 4–6 prove it, and Section 7 gives rates and a balanced-share corollary.Appendix A contains the complete classical proof, Appendix B standard quantum facts, and Appendix C register diagrams.Source: §1.7 · p. 9
2 Preliminaries
The preliminaries define two-split quantum tampering and worst-case non-malleability using classical–quantum states that retain attackers’ auxiliary registers. They also state the BBJ augmented non-malleability guarantee used by the construction.
2.1 Classical distributions and quantum states in registers
- Classical–quantum states encode each classical input’s probability in the trace of its associated quantum block, and trace distance extends total variation to these states.The setup uses joint states rather than normalizing conditional quantum states separately.Source: §2.1 · p. 9
2.2 Two-split quantum tampering and non-malleability
- A local quantum attack applies noncommunicating channels to the two shares, with arbitrary-dimensional pre-shared entanglement and classical output shares.The security error must be independent of auxiliary-register dimensions.Source: §2.2 · p. 10
- Worst-case security requires perfect decoding and, for each attack, one simulator distribution that works for every message.The comparison concerns decoded-message distributions, not a joint simulation of the attackers’ retained quantum registers.Source: §2.2 · p. 11
2.3 The precise BBJ security we invoke
- BBJ’s extractor guarantee has error η = 2^-n^Ω(1), with d = δn + O(1) and output length s0 = (1/2 − δ)n + O(1).The guarantee applies to independent uniform sources against local quantum attacks with arbitrary shared entanglement.Source: §2.3 · p. 11
3 Construction and exact permutation facts
The construction uses a truncated BBJ extractor to seed a total affine permutation, encoding a prescribed message with fresh random padding. An exact uniform-ciphertext hybrid and the main theorem support its worst-case security analysis.
3.1 A total bit-seeded affine family
- The affine seed defines a permutation for every seed, and ideal-key inverse images of distinct ciphertexts are uniform over ordered distinct field pairs.The implemented uniform seed distribution differs from the ideal key distribution by distance 1/N.Source: §3.1 · p. 12
- For each fixed seed and message, the permutation maps the T padded strings with that message prefix bijectively onto its ciphertext fiber.The conditional second prefix under an ideal key differs from uniform by εpair = (q − 1)/(q(N − 1)).Source: §3.1 · p. 13
3.2 Encoding and decoding
- Encoding samples independent X, Y, and padding R, uses the truncated extractor output to choose the affine permutation, and permutes m∥R.The code has perfect correctness, uses n + d + r random bits, and has rate ℓ/(n + d + s).Source: §3.2 · p. 13
3.3 The exact uniform-ciphertext hybrid
- Conditioning the uniform-ciphertext hybrid on latent message M = m exactly recovers the real experiment, including retained quantum output.The hybrid has uniform M independent of X and Y; the reduction avoids the generic factor q from conditioning an average error bound.Source: §3.3 · p. 14
3.4 The main theorem
- Construction 9 is a perfectly correct worst-case two-split quantum-secure non-malleable code under the stated extractor and parameter conditions.The theorem assumes the truncated extractor satisfies Definition 5 and specifies 0 < ζ < 1.Source: §3.4 · p. 14
4 Reordering the attack before message conditioning
The proof reorders each attack within the uniform-ciphertext hybrid before conditioning on a message. Smoothing and an exact continuation preserve the relevant quantum state, enabling the BBJ guarantee to produce a message-independent ideal key.
4 Reordering the attack before message conditioning
- The proof reorders the uniform-ciphertext experiment so BBJ’s guarantee applies to an intermediate state while retaining the right auxiliary register.The factorization is an equality of quantum operations.Source: §4 · p. 14
4.1 Smoothing and invertible probability operators
- Mixing the right operation with a ζ-probability randomized branch makes each aggregated Y′ probability operator invertible, at trace-distance cost at most ζ.Smoothing is used only in the proof and simulator.Source: §4.1 · p. 15
4.2 An exact continuation after the output Y ′
- An exact continuation after the coarse Y′ operation reconstructs the uniform mixture over ciphertexts while preserving the right output state.This reproduces the mixture over original ciphertexts, not the attack on an arbitrary fixed preexisting ciphertext.Source: §4.2 · p. 16
4.3 The actual intermediate state and its ideal key
- Applying BBJ security to the intermediate state yields a comparison with an independent ideal key and retained side state, with distance at most α := η + N^-1.The later message test has not yet been applied; it uses the retained key and ciphertext produced by continuation.Source: §4.3 · p. 17
5 Mean-one scaling and the permutation second moment
The analysis controls message selection through a mean-one scaling comparison and an ideal-state deficit bound. A noncommuting permutation-fiber second moment supplies that deficit without conditioning on a message.
5.1 A positive scaling theorem
- For two states with trace-distance at most α and equal unit output traces under a positive scaling operator, the scaled outputs remain close by the two-state mean-one comparison.The theorem applies to a completely positive map and its output probability operator.Source: §5.1 · p. 18
- The scaling comparison transfers input error at cost at most α, rather than multiplying it by the message count q.The bounded deficit below scaling factor one controls the transfer; ordinary data processing does not apply to the unnormalized selection map.Source: §5 · p. 17, §5.1 · p. 18
5.2 A noncommuting random-fiber calculation
- The permutation-fiber second moment bounds the expected ideal-state deficit by 1/2 √(qκ) while averaging the key and retaining the full side state.The calculation applies to positive matrices summing to identity with each bounded above by κI.Source: §5.2 · pp. 18–19
- The continuation bound and moment calculation leave a security surplus determined by r − d, so padding length r > d suffices for a positive surplus.The ciphertext has s = ℓ + r bits, while message selection costs ℓ bits and the second source length costs d.Source: §5.2 · p. 19
6 Worst-case security and the message-free simulator
The proof turns each fixed-message decoded output into a copy of a symbol, then compares it with one message-independent simulator. Exact normalizations and a common bound make this work for every message without dimension-dependent error.
6.1 Compute the symbol before forgetting the key
- For every execution, the decoded output equals Copy(m, Jm), where Jm is computed before the original key is discarded.The symbol distinguishes unchanged ciphertexts, changed ciphertexts under the original key, and outputs decoded under the tampered key.Source: §6.1 · p. 20
- Message selection defines a completely positive map whose output-scale operator is block diagonal in the coarse register.The selector uses the original Z and C after continuation recovers C while retaining Z; the factor q normalizes complete states, not individual transcripts.Source: §6.1 · p. 20
6.2 The two exact normalizations
- The actual and ideal message-selected experiments both have trace one, and the ideal refined-register marginal is exactly ν for every message.The normalization is global across the full state, including E′2, rather than a separate normalization of each transcript block.Source: §6.2 · p. 21
- The same intermediate states and comparison bound apply to every message, with no union bound or q-fold amplification of the extractor error.The fixed-message output comparison uses the same states µ and σ.Source: §6.2 · p. 21
6.3 One simulator for all messages
- The simulator runs the message-free hybrid and replaces the changed-ciphertext symbol distribution by fresh uniform output.Its cases follow the hybrid flag and whether the ciphertext changes; all scaling factors come from the hybrid, not a choice depending on m.Source: §6.3 · p. 22
- For every message, the decoded-output distance from the same simulator is at most β + εpair + ζ, uniformly over the allowed entanglement dimensions.The smoothed comparison costs at most β + εpair, and returning to the original attack adds at most ζ.Source: §6.3 · p. 22
7 Parameters, rate, and scope
The parameter choices yield rates approaching 1/5 for unequal shares and 1/8 for balanced shares, with perfect correctness and negligible security error. The error bound is governed separately by the padding surplus.
7.1 Finite error and the padding surplus
- The error exponent 1/5 comes from balancing smoothing error against a fourth-root term, and is distinct from the limiting code rate 1/5.For padding surplus g = r − d, the proof bounds the finite error by a constant multiple of 2−g/5.Source: §7.1 · p. 23
7.2 Instantiating the BBJ dimensions
- Rate at least 1/5 − ξ is achieved for every sufficiently small fixed ξ and all sufficiently large n, with perfect correctness and 2−n^Ω(1) error.The construction has polynomial-time online encoding and decoding against every entangled two-split attack.Source: §7.2 · p. 23
7.3 Equal-length components
- Balanced shares of length n achieve limiting rate (1 − 10δ)/8, which approaches 1/8 as the allowed fixed δ decreases.Padding the shorter share preserves perfect correctness and the security error.Source: §7.3 · p. 24
- The stated BBJ instantiation does not improve Li’s exponential classical error.The unbalanced rate, balanced rate, and error exponent are distinct parameters.Source: §7.3 · p. 24
A A complete classical proof of the rate-one-fifth construction
The appendix gives a classical proof of the rate-one-fifth construction using exact posterior distributions and averages of their sizes. It states the split-state security goal and isolates the classical randomness-encoder premise used by the proof.
A A complete classical proof of the rate-one-fifth construction
- The classical proof avoids the quantum scaling theorem and smoothing, using exact posterior distributions and averages of their sizes.Its final error expression is 2(η + 2−s) + 2−(r−d)/2 + 2ℓ−1 2ℓ(2s −1).Source: A A complete classical proof of the… · p. 31
A.1 Probability conventions and the security goal
- Non-malleability requires one distribution on messages, same, or failure that works for every message under local split attacks.Randomized local attacks may use correlated classical tapes independent of the message and encoder coins, but cannot communicate after receiving the shares.Source: §A.1 · p. 31
A.2 The external classical non-malleable randomness encoder
- The proof assumes a classical non-malleable randomness encoder guarantee for local randomized operations; BBJ’s classical result supplies it.The stated parameters include d = δn + O(1), 2s ≤ (1/2 − δ)n + O(1), and η = 2−n^Ω(1).Source: §A.2 · p. 32
A.3 The non-malleable code and the ideal permutation distribution
The construction encodes a prescribed message with fresh uniform padding through a key-dependent permutation, while the decoder inverts the permutation using the recomputed key. Affine counting establishes uniform sampling of the message fiber and quantifies the deviation of a second decoded value from uniform.
A.3 The non-malleable code and the ideal permutation distribution
- The encoder maps m concatenated with fresh padding through πZ, and the decoder applies f2nmExt(X′,Y′) to the tampered ciphertext.The nonzero slope makes inversion of an honest ciphertext recover m concatenated with its padding, giving perfect correctness.Source: §A.3 · p. 32
- For each raw key, exactly T ciphertexts decode to m, and πZ(m∥Ur) samples those ciphertexts uniformly.For distinct ciphertexts, the ideal uniform key gives the second decoded prefix a distribution pm conditional on the first prefix being m.Source: §A.3 · p. 33
- The conditional distribution assigns (T − 1)/(N − 1) to m and T/(N − 1) to each other prefix, with distance εpair = (q − 1)/(q(N − 1)) from uniform.The deficit at m and equal total excess on other prefixes determine the stated variation distance.Source: §A.3 · p. 33
A.4 An exact classical posterior factorization
The classical reduction reconstructs the fixed-message encoding by conditioning an exact message-free hybrid, then controls the security loss through mean-one scaling and average posterior support. A message-independent simulator yields the stated code guarantees.
A.4 An exact classical posterior factorization
- Conditioning the message-free hybrid on M = m reproduces the real encoding, and its exact posterior factorization preserves the tampered key and ciphertext jointly.The ideal comparison replaces only the coarse key-and-side-label distribution; the side-label marginal remains unchanged.Source: §A.4 · pp. 33–34
A.5 A mean-one scaling factor lemma
- Mean-one scaling factors turn nearby input distributions into normalized rescaled distributions, with distance at most 2α + 2d_Q, and a shared conditional channel preserves the comparison.The scaling function need not itself be a probability distribution.Source: §A.5 · pp. 34–35
A.6 The complete fixed-message output scaling factors
- The fixed-message output scaling has mean one in both experiments: its real distribution is the exact decoded-symbol distribution, while the ideal refined marginal is message-independent.The simulator’s output rule covers unchanged, changed, and tampered-decoding cases without an exceptional event.Source: §A.6 · pp. 35–36
A.7 Averaging posterior support sizes
- Averaging posterior support sizes bounds the message-selection deficit uniformly in m, avoiding a qη loss from worst-case conditioning.The bound depends on the number of possible short outputs and average posterior size, not the least positive probability.Source: §A.7 · pp. 36–37
A.8 The classical simulator and its exact ideal distribution
- For each deterministic attack, the classical simulator depends on the attack maps, not the message; the theorem gives perfect correctness and polynomial-time encoding and decoding.Source-independent shared random tapes are handled by averaging deterministic-map simulators.Source: §A.8 · p. 37
A.9 The resulting constant rate, with all limits specified
The specified parameters yield rate approaching 1/5 with negligible error. The remaining passages supply finite-dimensional quantum facts used to justify the reduction and its register diagrams.
A.9 The resulting constant rate, with all limits specified
- For fixed smaller allowed δ, the limiting rate (1 − 10δ)/(5 + 2δ) approaches 1/5, while stretched-exponentially small inner error yields negligible total error.The padding term is 2^(−δn/2+O(1)); the remaining seed and pair terms are 2^(−Ω(n)).Source: §A.9 · p. 38
B Elementary quantum facts used in the reduction
- The quantum reduction’s appendix arguments use finite-dimensional linear algebra, including the spectral theorem, tensor products, and Cauchy–Schwarz.These are stated as the linear-algebra background for the appendix arguments.Source: B Elementary quantum facts used in the… · p. 38
B.1 Kraus representation and probability operators
- A completely positive map admits a Kraus representation, and its probability operator describes outcome probabilities while the full map describes the state update.The distinction matters because equal outcome probabilities need not preserve the same residual state.Source: §B.1 · pp. 38–39
B.2 Variational formula and data processing
- Trace distance cannot increase under positive trace-nonincreasing maps, but selecting an event without renormalizing differs from normalized conditioning.The stated variational identity relies on equal-trace inputs.Source: §B.2 · p. 39
B.3 Purification and the state-scaled trace bound
- Purification and state-scaled trace bounds provide the moment-to-deficit estimate without an extraneous Hilbert-space dimension factor.The appendix identifies these as two distinct steps in that estimate.Source: §B.3 · pp. 39–40
B.4 No signalling versus selected outcomes
- No-signalling preserves the other party’s reduced state only after summing all local outcomes; conditioning on one selected outcome can change it.This is why the classical posterior proof cannot simply replace scalar conditional states with quantum states.Source: §B.4 · p. 40
C Register diagrams and message conditioning
- The register diagrams follow BBJ’s named-register and local-map conventions while adding the paper’s message-selection step.They are original diagrams, not reproductions of BBJ’s figures.Source: C Register diagrams and message… · p. 41
C.1 Notation and the registered tampering experiment
The notation distinguishes source, key, ciphertext, and quantum auxiliary registers in the registered tampering experiment. Figure 1 depicts two local operations without a communication link.
C.1 Notation and the registered tampering experiment
- E1 and E2 are the two auxiliary quantum registers, and E′1 and E′2 denote their outputs; A1 and A2 are channel forms of the local isometries.The coarse operation acts on E2 itself, while continuation produces E′2.Source: §C.1 · p. 41
- Z and C denote the original key and ciphertext used by the message test, while μ and σ name states defined in this paper.A superscript on U_A^k identifies register A rather than a power.Source: §C.1 · p. 41
- The two local quantum channels have no communication link, and the shared input ψ_E1E2 is independent of the encoding inputs.Double lines represent classical registers and single lines quantum registers.Source: Figure 1 · p. 41
C.2 Why a uniform message gives the uniform-ciphertext experiment
A uniform message makes the ciphertext experiment exactly uniform before tampering. The reduction then invokes BBJ before message selection and separates computing, selecting, and normalizing the message event.
C.2 Why a uniform message gives the uniform-ciphertext experiment
- With uniform M and padding R, M∥R is uniform, so the keyed bijection gives uniform ciphertext for every source pair and equivalent preparations before tampering.The equality is of the full joint state, not merely the ciphertext marginal.Source: §C.2 · p. 42, Figure 2 · p. 42
C.3 Exactly where BBJ is invoked
- BBJ is applied to the coarse state before continuation or message selection; only the original key is idealized, while the side state retains its actual marginal.The subsequent conditional prefix test uses Z and C after continuation.Source: Figure 3 · p. 43, §C.3 · p. 43
C.4 Computing a message, selecting it, and normalizing are different maps
- The construction first computes M=f_Z(C), then selects M=m with a trace-nonincreasing map; multiplying by q normalizes the selected complete states.The selection event has probability 1/q in both actual and ideal states, for different stated reasons.Source: §C.4 · p. 44, Figure 4 · p. 44
C.5 The two-state comparison through the same message-selection map
C.5 compares the same states through a message-dependent CP map, yielding a message-independent simulator distribution. C.6 explains the scaling-factor comparison that supports the proof.
C.5 The two-state comparison through the same message-selection map
- Both solid paths compose to the same CP map Φ_m; only that map depends on m, while the compared states and continuation do not.The comparison uses the mean-one scaling factor theorem, not ordinary data processing of T_m.Source: Figure 5 · p. 45, §C.5 · p. 45
- For every attack A, ε_pair is within total variation distance ε of Copy(m,D_A,ζ), with D_A,ζ sampled independently of m.Only the explicitly charged permutation correction remains message-dependent, preserving ∀A ∃D ∀m.Source: §C.5 · p. 45
C.6 The classical scaling factor lemma: one alphabet, then a new alphabet
- For mean-one scalings, the same conditional output channel gives ∆(PA,QA) ≤ ∆(Pw,Qw), though pointwise rescaling itself need not contract total variation.The scaling function need not itself be a probability distribution.Source: §C.6 · pp. 45–46, Figure 6 · p. 46
- The classical lemma factors pointwise scaling through a CP map and then a channel, yielding the rescaled output distributions without treating scaling as trace-preserving.The conditional-output step can map from the input alphabet to a different output alphabet.Source: §C.6 · p. 46, Figure 6 · p. 46