PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Mahdi Cheraghchi, Venkatesan Guruswami

arXiv:1309.1151v2cs.ITcs.CCcs.CRmath.IT

TL;DR

The paper studies non-malleable coding against bit-wise tampering and split-state adversaries, including the challenge of obtaining efficient split-state codes beyond the polynomially small rate of the best known explicit construction. For split-state coding, the paper relates code construction to two-source non-malleable extractors and proves an existence theorem for seedless non-malleable extractors. For all integers n ⩾1, an explicit deterministic bit-tampering code with efficient encoding/decoding achieves rate 1 −o(1) and error at most exp(−nΩ(1)).

  • Problem

    The paper studies non-malleable coding against bit-wise tampering and split-state adversaries, including the challenge of obtaining efficient split-state codes beyond the polynomially small rate of the best known explicit construction.

    Source: §1.1 · p. 4, §1.1.2 · p. 5

  • Method

    For split-state coding, the paper relates code construction to two-source non-malleable extractors and proves an existence theorem for seedless non-malleable extractors.

    Source: §1.1.2 · p. 5

  • Results

    For all integers n ⩾1, an explicit deterministic bit-tampering code with efficient encoding/decoding achieves rate 1 −o(1) and error at most exp(−nΩ(1)).

    Source: §1.1.1 · p. 4

  • Takeaways & Limitations

    The extractor approach provides a route to split-state codes with rates arbitrarily close to 1/5, although it does not provide an explicit construction.

    Source: §1.1.2 · p. 5

    The reduction is not a characterization: split-state codes need not correspond to non-malleable extractors, since the extractors it implies have slightly sub-optimal rates.

    Source: §5 · p. 26

Abstract

from arXiv · show

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Dziembowski et al. show existence of non-malleable codes for any class of tampering functions of bounded size. We consider constructions of coding schemes against two well-studied classes of tampering functions: bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). 1. For bit-tampering, we obtain explicit and efficiently encodable and decodable codes of length $n$ achieving rate $1-o(1)$ and error (security) $\exp(-\tilde{\Omega}(n^{1/7}))$. We improve the error to $\exp(-\tilde{\Omega}(n))$ at the cost of making the construction Monte Carlo with success probability $1-\exp(-\Omega(n))$. Previously, the best known construction of bit-tampering codes was the Monte Carlo construction of Dziembowski et al. (ICS 2010) achieving rate ~.1887. 2. We initiate the study of seedless non-malleable extractors as a variation of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove existence of such extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error. Currently, the best known explicit construction of split-state coding schemes is due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves vanishing (polynomially small) rate.

1 Introduction

Non-malleable coding protects messages against tampering by requiring corrupted codewords to decode either to the original message or to an unrelated one. This paper gives near-rate-1 bit-tampering codes and develops an extractor-based route to split-state codes.

1.1.1 Bit-tampering functions

  • Rate 1-o(1) is achieved by an explicit deterministic bit-tampering code with efficient encoding and decoding and error at most exp(-n^Omega(1)).The paper also reports an improved error of exp(-tildeOmega(n)) with a Monte Carlo construction that succeeds with probability 1-exp(-Omega(n)).Source: §1.1.1 · p. 4
  • Error exp(-tildeOmega(n)) is available for bit-tampering codes through a Monte Carlo construction succeeding with probability 1-exp(-Omega(n)).This strengthens the error guarantee while changing the construction from deterministic to Monte Carlo.Source: §1.1.1 · p. 4

1.1.2 Split-state adversaries

  • A split-state code can be built from a two-source non-malleable extractor by using the extractor as the decoder and choosing an encoding pre-image.The two halves may be tampered independently, with arbitrary functions within each half.Source: §1.1.2 · p. 5
  • The paper proves existence of seedless non-malleable extractors that yield split-state codes with rates arbitrarily close to 1/5.The paper offers no explicit construction, and the polynomially small rate in remains the best known explicit result.Source: §1.1.2 · pp. 5–6
  • For constant-rate split-state codes, two-source non-malleable extractors with source entropy rate .99 and output length Omega(n) suffice.The paper says the ordinary two-source extractor 1/2 entropy-rate barrier does not concern this application.Source: §1.1.2 · p. 6
  • Explicit two-source non-malleable extractors for simultaneous tampering of both inputs remain an open problem.Known constructions discussed here do not tamper both inputs simultaneously.Source: §1.1.2 · p. 6

2 Preliminaries

The preliminaries establish notation and define coding schemes, non-malleability, and limited-independence tools. They also specify the structural properties of LECSS codes used later.

2.2 Definitions

  • A coding scheme uses a randomized encoder and deterministic decoder, with decoding of every valid encoding returning its original message with probability 1.Its rate is message length divided by block length; relative distance describes guaranteed error detection for sufficiently small additive errors.Source: §2.2 · p. 7
  • Non-malleability requires each tampering function's decoded output to be close to a message-independent distribution, allowing the special outcomes same and ⊥.A valid distribution for this definition can be efficiently sampled when the coding scheme has efficient encoding and decoding, with a possible constant-factor error increase.Source: §2.2 · p. 7
  • Limited independence requires every marginal on at most ell coordinates to be delta-close to uniform; for permutations, it compares the selected images with those of a uniform permutation.LECSS codes additionally require minimum distance, t-wise independent encodings, and additive linearity for non-error decoded words.Source: §2.2 · p. 8

3 Existence of optimal bit-tampering coding schemes

The section develops a probabilistic code construction and establishes properties used to obtain bit-tampering codes with near-optimal rate. Its inner codes combine non-malleability, cube, bounded-independence, and error-detection properties.

Construction 1

  • Construction 1 forms each message’s encoding by randomly selecting codewords, while decoding returns the unique message whose assigned set contains the input, or ⊥ if none does.The construction uses t random vectors for each message and removes Hamming balls around previously selected vectors.Source: §3 · p. 9

Lemma 3.5

  • With probability 1−3exp(−n), Construction 1 can provide bit-tampering non-malleability with error exp(−Ω(αn)).The same construction is also shown to satisfy the cube and bounded-independence properties used in the later explicit construction.Source: §3 · pp. 11–13
  • The construction also provides the cube property and makes each message encoding close to an Ω(αn)-wise independent distribution with uniform entries.The bounded-independence approximation has error exp(−Ω(αn)).Source: §3 · p. 12
  • The inner code has an error-detection property for every message against bit-tampering functions that are neither identity nor constant.The stated probability is taken over the encoder’s randomness.Source: §3 · p. 12

4 Explicit construction of optimal bit-tampering coding schemes

The section gives an explicit construction of near-capacity bit-tampering codes. It combines an outer secret-sharing code, inner codes, a pseudorandom permutation, and a separately encoded seed.

4 Explicit construction of optimal bit-tampering coding schemes

  • The explicit construction targets bit-tampering codes with rate close to 1.The final code’s block length is denoted N.Source: §4 · p. 13

4.1 The construction

  • The construction combines an inner code, an existing bit-tampering non-malleable code, a linear error-correcting secret-sharing scheme, and a pseudorandom permutation.The permutation is generated from a uniformly random seed.Source: §4.1 · p. 13

4.1.1 The building blocks

  • Its building blocks have rates 1−γ0 for the inner code and 1−γ2 for the LECSS, while the seed code has rate r and error ϵ1.The permutation mapping is polynomial-time computable and is assumed to produce an ℓ-wise δ-dependent permutation from a uniform seed.Source: §4.1.1 · p. 15

4.1.2 The encoder

  • The encoder encodes a random seed, LECSS-encodes the message, inner-encodes its blocks, permutes the resulting string, and outputs it with the seed codeword.The final encoded length is N=(1+γ1)n.Source: §4.1.2 · p. 15

4.1.3 The decoder

  • The decoder recovers the seed and permutation, reverses the permutation, decodes each inner block, and applies the LECSS decoder to recover the message or output ⊥.It outputs ⊥ if any inner block decodes to ⊥ or if the reconstructed string is not a LECSS codeword.Source: §4.1.3 · p. 16

4.2 Analysis

The analysis proves that the Section 4.1 construction is non-malleable against bit-tampering adversaries at rate at least 1−γ0. It treats excessive freezing separately, using LECSS bounded independence to make the decoded output independent of the message.

4.2 Analysis

  • The Section 4.1 construction is non-malleable against bit-tampering adversaries at rate at least 1−γ0.Its error depends on the rate and error of the assumed seed code C1.Source: §4.2 · p. 16
  • The construction also satisfies strong non-malleability if the seed code C1 satisfies the strong definition.The paper focuses on standard non-malleability; the strong variation requires this additional condition on C1.Source: §4.2 · pp. 16–17

Proof of Theorem 4.3

  • The decoder recovers the original message from an honestly encoded word, so the proof focuses on non-malleability under tampering.The proof considers a non-identity bit-tampering adversary and partitions positions into frozen, flipped, and unchanged bits.Source: Proof of Theorem 4.3 · p. 17

Case 1: Too many bits are frozen by the adversary.

  • When at least n−t2/b bits of C′ are frozen, the tampered decoding distribution is independent of the message, giving zero error for this case.The argument uses the LECSS bounded-independence property.Source: Case 1: Too many bits are frozen by… · pp. 17–18

Case 2: The adversary does not alter Π.

This case analyzes tampering that leaves the induced permutation unchanged and does not freeze too many bits. Bounded independence of the permutation is used to blunt adversarial targeting of the inner-code blocks.

Case 2: The adversary does not alter Π.

Case 2.1: |Id′| > n −δ2nb

In this case, bounded independence makes the tampered coordinates independent of the encoded message. The decoder outputs either the original message or ⊥, with the probability of ⊥ independent of the message.

Case 2.1: |Id′| > n −δ2nb

  • The affected blocks contain fewer than δ2nb blocks, so the LECSS distance property detects any errors in S′ after inner decoding.All but fewer than δ2nb inner blocks decode correctly, leaving fewer than δ2n2 potentially incorrect bits of S′.Source: Case 2.1: |Id′| > n −δ2nb · p. 18
  • Bounded independence makes the tampered coordinates’ distribution independent of the encoded message, supporting the same-or-⊥ decoder outcome.The restriction of S′ to the affected positions is uniformly distributed under the stated bounded-independence condition.Source: Case 2.1: |Id′| > n −δ2nb · p. 18
  • The decoder’s probability of outputting ⊥ is message-independent, yielding zero-error non-malleability with a distribution supported on {same, ⊥}.The decoder outputs only the original message or ⊥ in this case.Source: Case 2.1: |Id′| > n −δ2nb · p. 19
  • In another case branch, parameter choices make the decoder output ⊥ with high probability, giving a non-malleability distribution supported only on ⊥.The resulting error is bounded by (14), whose value is not specified in these passages.Source: Case 2.2: |Id′| ⩽n −δ2nb · p. 20

Case 3: The decoder estimates an independent permutation.

When the decoder’s permutation estimate is independent, the analysis finds many inner blocks touched by non-freezing tampering and bounds their chances of decoding without rejection. Consequently, the decoder outputs ⊥ with high probability.

Case 3: The decoder estimates an independent permutation.

  • At least ⌊ℓ/B⌋ positions are selected from bits not frozen by the adversary, yielding a set of affected inner-code blocks for analysis.The passage assumes ℓ ≤ t2 and selects ⌊ℓ/B⌋ positions.Source: Case 3: The decoder estimates an… · p. 21
  • Conditioned on earlier blocks, bounded independence and a union bound make the source positions for a block distinct with high probability.When distinct, fresh randomness across inner encodings makes the corresponding bits independent; each block then decodes without rejection with probability at most 3/4 under the stated closeness condition.Source: Case 3: The decoder estimates an… · pp. 21–22
  • The decoder outputs ⊥ with high probability, establishing non-malleability with a distribution supported only on ⊥.The error is bounded by the right-hand side of (17), whose value is not given here.Source: Case 3: The decoder estimates an… · p. 22

The general case.

The general analysis uses the non-malleability of the permutation code to reduce arbitrary joint behavior to matching or independent permutation cases. Combining their bounds proves non-malleability for the full construction.

The general case.

  • The joint distribution of the encoder’s and decoder’s permutations is ϵ1-close to a convex combination of matching and independent cases.The reduction follows from non-malleability of C1.Source: The general case · p. 22
  • The analysis defines decoding with an arbitrary estimated permutation, and the natural estimate recovers the ordinary tampered-decoding experiment.Ds,¯P replaces the decoder’s estimate from the codeword with a chosen ¯P; setting it to Perm(¯Z) gives Dec(f(Enc(s)).Source: The general case · pp. 22–23
  • The full construction is non-malleable with error bounded by ϵ′.The decoded tampered codeword distribution is ϵ′-close to copy(Df, s).Source: The general case · p. 23

Setting up the parameters

Parameter choices satisfy the construction’s constraints while preserving a rate arbitrarily close to 1. The resulting error is bounded by ϵ′, and the split-state consequence reaches rates arbitrarily close to 1/5.

Setting up the parameters

  • The final code’s rate can be made arbitrarily close to 1 by choosing γ0 sufficiently small.The parameter setup chooses γ1 and γ2 in [γ0/2, γ0].Source: Setting up the parameters · p. 24
  • The inner-code block size B depends only on γ0, and brute-force search can find an explicit inner code in time depending only on γ0.The stated parameter condition holds for N ≥ N0, where N0 = poly(1/γ0).Source: Setting up the parameters · p. 24
  • The final coding scheme’s error is bounded by ϵ′, with parameter choices setting up the preceding failure-probability bounds.The explicit value of the bound is not present in these passages.Source: Setting up the parameters · pp. 24–25

4.3 Instantiations

Section 4.3 gives two bit-tampering code instantiations: one achieves near-unit rate with error exp(−˜Ω(n)), while the explicit alternative has error exp(−˜Ω(n^1/7)).

4.3 Instantiations

  • The cited Dziembowski et al. construction has rate at least .18 and error exp(−Ω(n)), and is Monte Carlo.Source: §4.3 · p. 25
  • The explicitness guarantee in Theorem 4.6 assumes a large prime p=exp(˜Ω(k + log(1/ϵ))) is available.Source: §4.3 · p. 25
  • Rate at least 1−γ0 and error exp(−˜Ω(n)) are achieved by the efficient bit-tampering scheme; its randomized description succeeds with probability at least 1−exp(−Ω(n)).Source: §4.3 · p. 26
  • An explicit and efficient code achieves rate at least 1−γ0 with error at most exp(−˜Ω(n^1/7)).Source: §4.3 · p. 26

5 Construction of non-malleable codes using non-malleable extractors

The section studies seedless non-malleable extractors, establishing existence bounds and using two-source variants to construct split-state non-malleable codes. The resulting codes achieve constant rates approaching 1/5.

5 Construction of non-malleable codes using non-malleable extractors

  • The section extends seeded non-malleable extractors to structured sources and reduces split-state coding to non-malleable two-source extractors.The reduction is not a characterization: the section notes it can be adapted to multiple blocks or unknown partitions, the latter using mixed-source extractors studied by Raz and Yehudayoff.Source: §5 · p. 26

5.1 Seedless non-malleable extractors

  • For adversaries promised to have no fixed points, a relaxed two-source non-malleable (k1 − log(1/ϵ), k2 − log(1/ϵ), ϵ)-extractor is a two-source non-malleable (k1, k2, 4ϵ)-extractor.Source: §5.1 · pp. 27–28

5.2 From non-malleable extractors to non-malleable codes

  • Rate Ω(1) and error exp(-Ω(n)) are achieved for split-state codes from relaxed two-source extractors with output length m=Ω(n), entropy deficits n−k1,n−k2=Ω(n), and error ε=exp(-Ω(m)).The decoder outputs the first k bits of the extractor; the encoder samples uniformly from the corresponding decoder preimage.Source: §5.2 · p. 32

5.3 Existence bounds on non-malleable extractors

  • Random functions yield seedless non-malleable extractors with high probability for bounded-size source and tampering families, including extraction conditioned on g(X).The existence theorem also guarantees non-malleability with respect to a tampering function f.Source: §5.3 · pp. 32–33
  • The existence theorem applies to bounded source classes and tampering-function families, including functions that may have fixed points.It can also recover the existence result for strong seeded non-malleable extractors.Source: §5.3 · p. 35
  • Strong two-source extractors can provide extraction and non-malleability even when either source is revealed to the distinguisher, but this strength is not needed for the application.Source: §5.3 · p. 35
  • With probability at least 1−γ, a uniformly random function is a two-source non-malleable (k1, k2, ϵ)-extractor when the theorem’s parameter condition holds.The theorem allows sources with min-entropies k1 and k2, respectively.Source: §5.3 · p. 36
  • For every α > 0, a choice of NMExt yields split-state non-malleable codes at rate 1/5 −α with error exp(−Ω(αn)).The construction follows by applying the two-source non-malleable extractor existence result to the coding scheme.Source: §5.3 · p. 36

A Construction of LECSS codes

Construction 2 builds a linear error-correcting secret-sharing scheme from a linear code. Randomized encoding and bounded independence support its error-correcting properties.

A Construction of LECSS codes

  • The construction’s analysis uses a lemma from [12], which is based on, and includes a proof for completeness.The lemma establishes the linear error-correcting coding-scheme parameters used by the construction.Source: A Construction of LECSS codes · p. 38
  • If G spans a code of relative distance at least δ and its first k0 rows span a code of dual relative distance at least τ, the scheme is a (δN/log q, τN/log q)-LECSS.Its linearity follows from the encoder being an injective linear function, and its distance property follows from the underlying code.Source: A Construction of LECSS codes · pp. 38–39
  • Construction 2 encodes a message by appending uniformly random symbols, then applying the generator matrix G and outputting the result in binary.The block length is N := n log q and message length K := (k − k0) log q.Source: A Construction of LECSS codes · p. 39
  • The decoder interprets its input as a vector, recovers the message symbols when they form a codeword under G, and otherwise outputs ⊥.The construction is based on linear error-correcting codes.Source: A Construction of LECSS codes · pp. 38–39
  • For each fixed message, the random first k0 symbols make the encoding τN/log q-wise independent.The dual-distance condition ensures that every τn columns of G0 are linearly independent.Source: A Construction of LECSS codes · pp. 38–39

Instantiation using Reed-Solomon codes

Reed-Solomon codes instantiate Construction 2 with rate close to one and yield explicit LECSS codes for every block length.

Instantiation using Reed-Solomon codes

  • For q = n, k = ⌈n(1 − α/2)⌉, and k0 = ⌊αn/2⌋, the construction has rate at least 1 − α and is an (Ω(αN/log n), Ω(αN/log n))-LECSS.The Reed-Solomon code’s relative distance and the first k0 rows’ dual relative distance are both Ω(α).Source: Instantiation using Reed-Solomon codes · p. 39
  • For every integer n and α in (0, 1), an explicit binary LECSS exists with block length n, message length at least n(1 − α), and parameters (Ω(αn/log n), Ω(αn/log n)).When n is not a power of two, the construction uses the least power of two q ≥ n.Source: Instantiation using Reed-Solomon codes · p. 40

B Useful tools

Appendix B collects distributional and probabilistic tools for analyzing correlated variables, non-malleability, and empirical approximations.

B Useful tools

  • Proposition B.1 reduces bounds conditioned on previous variables to bounds conditioned on a variable Z that determines them.The proposition applies when the stated bounds hold for every possible value of Z.Source: B Useful tools · p. 40
  • A distribution uniform on a set of size at least (1 − ϵ)2^n is within ϵ/(1 − ϵ) of uniform, while conditioning close distributions on an event of probability p gives distance at most ϵ/p.These are Propositions B.2 and B.3, respectively.Source: B Useful tools · p. 40
  • For a non-malleable code, the tampered-message distribution is ϵ-close to a mixture of the original message and an independent message, with mixture weight α on the original.The setup defines α as the probability of the “same” outcome.Source: B Useful tools · p. 41
  • If n independent bits are each ϵ-close to uniform, their joint distribution is O(nϵ)-close to uniform.Source: B Useful tools · p. 41
  • Azuma-based bounds address sums of possibly dependent variables using conditional-expectation bounds, including lower-bound variants.The appendix also frames analysis through chains of correlated variables and prior outcomes.Source: B Useful tools · pp. 40–42
  • When successive conditional distributions are close to D, the empirical distribution of the samples is ϵ-close to D with probability at least 1 − η for n ≥ n0.The result assumes D has finite support of size at most r and γ < ϵ.Source: B Useful tools · p. 42
Loading 1309.1151v2…