Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Eshan Chattopadhyay; Vipul Goyal; Xin Li

Source-linked AI summary

Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Eshan Chattopadhyay, Vipul Goyal, Xin Li

arXiv:1505.00107v1May 1, 2015cs.CRcs.CC

TL;DR

Explicit non-malleable extractors and codes are difficult to construct, especially when an adversary can tamper with inputs. This paper gives constructions for seeded and seedless settings, including repeated tampering, and establishes related extractor and code results.

Problem
Explicit non-malleable extractor constructions lag behind their non-tampered counterparts, while adversarial tampering makes extractor outputs need to remain independent of tampered outputs.
Source: §1 · pp. 2–3
Method
The paper constructs seeded and seedless non-malleable extractors, extends the seedless construction to repeated tampering, and uses alternating extraction for the latter.
Source: §1 · p. 4, §2.1 · p. 14
Results
For t ≤ n^γ, the paper gives a seedless (2, t)-NM extractor at min-entropy n − n^γ, with error 2^−n^Ω(1) and output length m = n^Ω(1), and one-many codes with relative rate n^Ω(1)/n and error 2^−n^Ω(1).
Source: §1.2 · p. 9
Takeaways & Limitations
The work initiates study of repeated-tampering extractors and codes, which it reports have natural applications in cryptography.
Source: §1 · p. 4
The paper’s 2-split-state non-malleable code results do not improve the already nearly optimal construction of Aggarwal et al..
Source: §1 · p. 4

Abstract

from arXiv · show

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy $k \geq n-n^{\Omega(1)}$, with output size $n^{\Omega(1)}$ and error $2^{-n^{\Omega(1)}}$. (3) We initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. We construct the first explicit non-malleable two-source extractor with tampering degree $t$ up to $n^{\Omega(1)}$, which works for min-entropy $k \geq n-n^{\Omega(1)}$, with output size $n^{\Omega(1)}$ and error $2^{-n^{\Omega(1)}}$. We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree $t$ up to $n^{\Omega(1)}$, relative rate $n^{\Omega(1)}/n$, and error $2^{-n^{\Omega(1)}}$.

1 Introduction

The introduction frames non-malleable extractors and codes as resilient to adversarial tampering, presenting seeded and seedless constructions and extensions from the usual single-codeword setting to one-many and many-many settings. It also discusses implications for privacy amplification and motivates many-many non-malleable secret sharing.

1 Introduction

Explicit seeded non-malleable extractors work for min-entropy k ≥ log2 n, improving on prior constructions that required at least 0.49n entropy.The paper connects seeded non-malleable extractors to privacy amplification against active adversaries.Source: §1 · p. 3
The paper gives the first explicit seedless 2-non-malleable extractors and shows that their pre-images can be sampled uniformly and efficiently.Via the connection in, this also yields explicit non-malleable codes, though it does not improve the nearly optimal construction of Aggarwal et al..Source: §1 · p. 4
The paper initiates the study of seedless (2, t)-non-malleable extractors and one-many non-malleable codes, with explicit extractor constructions for t up to n^δ.The introduced one-many codes have natural cryptographic applications.Source: §1 · p. 4

1.1 Non-malleable codes

One-many non-malleable codes require the joint distribution of an adversary’s multiple decoded outputs to be independent of the encoded message, except where outputs retain that message.The notion addresses tampering that produces multiple codewords, which the conventional one-one setting does not capture.Source: §1.1 · p. 6
One-many non-malleable codes cannot support arbitrary tampering degree with error below 1/4 for a broad class of functions that read an input bit and output a fresh encoding.The class includes most natural tampering functions, including split-state ones.Source: §1.1 · pp. 6–7
One-many non-malleable codes with tampering degree t and error ϵ also satisfy the many-many definition with error uϵ, where u is the number of input codewords.The proof uses a hybrid argument over the independent encoded sources.Source: §1.1 · p. 7
Many-many non-malleable codes directly yield many-many non-malleable secret sharing, addressing settings where an adversary tampers with multiple secrets’ shares and outputs multiple resulting shares.The motivating two-secret, two-device example illustrates that one-one non-malleability does not rule out relationships between the original and resulting secrets.Source: §1.1 · p. 8

1.2 Summary of results

For t ≤ n^γ, the paper constructs an efficient seedless (2, t)-non-malleable extractor at min-entropy n − n^γ, with error 2^−n^Ω(1) and output length n^Ω(1).The authors note that no such construction was previously known even for t = 1 and full min-entropy.Source: §1.2 · p. 9
For t ≤ n^γ, the extractor yields one-many non-malleable codes in the 2-split-state model with relative rate n^Ω(1)/n and error 2^−n^Ω(1).The paper also gives an efficient algorithm to sample almost uniformly from the pre-image of any extractor output.Source: §1.2 · p. 9
The paper constructs an explicit seeded non-malleable extractor at polylogarithmic min-entropy and extends the seeded setting to t-adversarial functions, improving a result of.Combined with, it gives a two-round active-adversary privacy amplification protocol with entropy loss O(log n + log(1/ε)) for k ≥ C(log n + log(1/ε))^2.Source: §1.2 · p. 9

1.3 Other possible approaches to construct one-many non-malleable codes

Existing one-one codes need not be one-many secure: the example code remains one-one non-malleable but allows two adversaries’ outputs to sum to m + 1.The authors explain that known approaches based on reductions, Aggarwal et al.’s construction, or the seedless extractor of [CZ14] do not straightforwardly extend to multiple adversaries, making their new extractors a necessity for this application.Source: §1.3 · pp. 9–10

1.4 Related work on privacy amplification

Seeded non-malleable extractors were introduced for privacy amplification by, while explicit constructions progressed from entropy rates above 1/2 to 1/2 − δ in.[DW09] connected seeded non-malleable extractors to two-round protocols with optimal entropy loss; later used non-malleable condensers for such protocols subject to k ≥ s^2.Source: §1.4 · pp. 10–11

1.5 Related work on non-malleable codes

Prior explicit information-theoretic non-malleable codes were one-one, while recent work gave almost optimal constructions in the C-split-state model for C ≥ 2.Continuous non-malleable codes stop the experiment when an error is detected and rely on computational assumptions, making that model weaker than the one considered here.Source: §1.5 · pp. 11–12

Organization

The paper presents preliminaries and extractor definitions, connects seedless (2, t)-extractors to one-many codes, gives explicit seedless and seeded constructions, and supplies encoding and decoding algorithms.These topics are organized across Sections 2–8.Source: Organization · p. 12

2 Overview of Our Constructions

The overview presents a seedless non-malleable extractor construction and its alternating-extraction mechanism, alongside a related seeded extractor for tampered seeds. It also describes modifications for efficient uniform sampling from extractor pre-images.

2 Overview of Our Constructions

The overview identifies efficient almost-uniform sampling from any extractor pre-image and the connection via Theorem 5.1 to many-many non-malleable codes in the 2-split state model.The seedless non-malleable extractor is the main ingredient in these constructions.Source: §2 · p. 12
A simple modification of the seedless construction gives an explicit seeded non-malleable extractor for min-entropy k ≥ log^2 n.The overview says it will also describe how to achieve this construction.Source: §2 · p. 12

2.1 A Seedless (2, t)-Non-Malleable Extractor

For t = n^γ/C, an explicit nmExt outputs n^Ω(1) bits on independent sources of min-entropy n − n^γ under arbitrary 2-split tamperings, with stated error ε = 2^-n^Ω(1).Each tampering must have at least one component with no fixed points.Source: §2.1 · pp. 12–13
The construction first derives a short string Z that differs from every tampered version, then uses its bits to guide iterative alternating extraction until the output is independent of the tampered outputs.Z is formed from source slices and pseudorandomly sampled bits of error-correcting-code encodings, using an inner-product two-source extractor.Source: §2.1 · pp. 13–14
The second approach uses Cohen’s flip-flop alternating extraction, is simpler and better suited to many-many codes, and receives the formal proof; the first approach’s sketch is not formally proved.The second approach is based on techniques developed in.Source: §2.1 · pp. 14–16
The seedless (2, t)-extractor argument achieves its goal once independence holds, because that condition persists in subsequent steps.Source: §2.1 · p. 16

2.2 An Explicit Seeded Non-Malleable Extractor for Polylogarithmic Min-Entropy

The seeded construction applies snmExt to a source X and uniform seed Y alongside outputs using arbitrary no-fixed-point tamperings A_i(Y).It separates each tampered seed with high probability, then completes extraction while preserving source independence after conditioning on intermediate variables.Source: §2.2 · p. 17

2.3 Efficient Algorithms for Many-Many Non-Malleable Codes

The modified extractor enables efficient uniform sampling from an output pre-image by making pre-image sizes equal across auxiliary choices and mapping each pre-image element to one sequence.The sampling strategy inverts alternating-extraction steps and uses linear equations from sampled codeword bits to generate the remaining input bits.Source: §2.3 · pp. 18, 20
Linear seeded strong extractors enable stepwise inversion, while a new extractor gives equal-size pre-images for each fixed seed and RS-code constraints equalize the remaining pre-image sizes.The RS-code construction preserves distinct sampled encodings with probability 1−2^-n^Ω(1).Source: §2.3 · pp. 18–20

3 Preliminaries

This section establishes notation and summarizes entropy, extractor, and probability tools used in the constructions. It also recalls explicit seeded and two-source extractor constructions.

3.1 Notations

The notation section defines projections, prefixes, coordinate indexing, and uniform distributions used throughout the paper.Source: §3.1 · p. 20

3.2 Min Entropy, Flat Distributions

A source is flat when uniform on a set, and any (n, k)-source is a convex combination of flat sources supported on sets of size 2^k.Source: §3.2 · p. 21

3.3 Statistical Distance, Convex Combination of Distributions and Probability Lemmas

Statistical distance measures closeness of distributions; convex combinations use nonnegative weights, and the section records a bound averaging component distances.Source: §3.3 · p. 21

3.4 Seeded and Seedless Extractors

A strong seeded extractor outputs bits close to uniform jointly with its independent uniform seed; linear seeded extractors are linear in the source for each seed.Source: §3.4 · p. 21

3.5 Conditional Min-Entropy

Average conditional min-entropy supports extraction when side information is given, and the section recalls bounds for conditioning on variables with limited support.Source: §3.5 · p. 22

3.6 Somewhere Random Sources

A somewhere random source has at least one uniform row, while its rows may be arbitrarily correlated.Source: §3.6 · p. 22

3.7 Some Known Extractor Constructions

Strong seeded linear extractors [RRV02], optimal-parameter seeded extractors, and inner-product two-source extractors provide the explicit building blocks reviewed here.The inner-product construction gives output close to uniform even conditioned on either source.Source: §3.7 · pp. 22–23

4 Seeded and Seedless Non-Malleable Extractors

The section recalls seeded and seedless non-malleable extractor definitions, then introduces a seedless two-source version allowing multiple split-state tamperings. Its guarantee compares the original output and all tampered outputs with a uniform string coupled to a source-independent distribution.

The section recalls seeded t-non-malleable extractors, generalizing seeded non-malleability introduced in, and seedless non-malleability introduced in.Source: §4 · p. 24
The seedless 2-non-malleable definition uses independent sources and a 2-split-state tampering function, with a source-independent comparison distribution.Source: §4 · p. 24
The seedless (2, t)-non-malleable extractor generalizes the two-source setting to t arbitrary 2-split-state tampering functions.Source: §4 · pp. 24–25
Its guarantee makes the original and t tampered outputs jointly close to a uniform m-bit string coupled to a source-independent distribution.Source: §4 · p. 25

5 Non-malleable codes via Seedless non-malleable extractors

The section extends the connection between seedless non-malleable extractors and non-malleable codes to one-many codes in the 2-split-state model. It gives code parameters and an encoder based on sampling uniformly from extractor pre-images.

5 Non-malleable codes via Seedless non-malleable extractors

The theorem generalizes the connection between non-malleable codes and seedless non-malleable extractors established in.Source: §5 · p. 25
A seedless (2,t)-non-malleable extractor yields a one-many non-malleable code in the 2-split-state model with an efficient decoder.The code has block length 2n, relative rate m/2n, and error ε2^(mt+1).Source: §5 · p. 25
The encoder samples uniformly from the extractor pre-image of the message, while decoding applies the extractor to the codeword.Efficient encoding therefore requires efficient sampling from each pre-image.Source: §5 · p. 25

6 An Explicit Seedless (2, t)-Non-Malleable Extractor

This section develops the tools and components used to construct an explicit seedless (2, t)-non-malleable extractor, including averaging samplers and alternating extraction. It assembles the construction and proves its tampering resistance, establishing error 2^-n^Ω(1) through a reduction from arbitrary tamperings.

6.1 Averaging Samplers

The section constructs a polynomial-time averaging sampler with distinct samples, using seeded extractors to obtain samples that intersect large subsets with high probability.For constants δSamp and νSamp, the construction has seed length r ≥ n^α and sample count O(n^β), for constants α, β < νSamp.Source: §6.1 · pp. 25–26

6.2 Alternating Extraction

A strong seeded extractor still works when its seed has min-entropy d − λ, addressing the nonuniform initial seed used in the alternating-extraction application.The text notes that using Raz’s extractor instead to generate R1 would achieve error O(uε), but is avoided to ensure final-extractor invertibility.Source: §6.2 · pp. 26, 29
The paper generalizes Li’s alternating-extraction result under stated source conditions: arbitrarily correlated auxiliary variables independent of the main inputs receive per-index error ε_i = O(uε + 2^λε) for each i in [u].Source: §6.2 · p. 27

6.3 Construction of Some Key Components

The 2laExt construction, inspired by Cohen’s local correlation breakers and flip-flop method, produces an almost-uniform output while preserving independence and source entropy with high probability.Lemma 6.8 gives failure probability ε′ = O(2^λ ε); the output is ε′-close to uniform and a deterministic function of Y.Source: §6.3 · p. 29
nmExt1’s output is O(2^λ ε + ℓε)-close to uniform after ℓ iterations under the stated source-independence and tampering conditions.The lemma assumes Y is independent of X and its tampered versions, and each tampered ℓ-bit string differs from z; the X-side tamperings may be arbitrarily correlated with X.Source: §6.3 · p. 33

6.4 An Explict Seedless (2, t)-Non-Malleable Extractor Construction

The construction sets t = n^γ/C and combines parameterized extractors, a look-ahead extractor, and nmExt1 as its components.The setup includes Extq, Extw, Ext, and laExt; nmExt1 uses the 2laExt setup.Source: §6.4 · pp. 33–34
Algorithm 3 outputs n4 bits by computing an inner product, forming z from input slices and sampled codeword coordinates, and applying nmExt1.It forms x2 and y2 from coordinates T of E(x) and E(y), then concatenates x1, x2, y1, and y2 to make z.Source: §6.4 · p. 34
Algorithm 3 computes a seedless (2, t)-non-malleable extractor with error 2^-n^Ω(1).Theorem 6.12 states this guarantee for nmExt.Source: §6.4 · p. 34
For independent (n, n − n^γ)-sources, property Pn handles t arbitrary 2-split-state tamperings when each has a component with no fixed points.Lemma 6.13 establishes property Pn, and Lemma 6.14 derives non-malleability from that property.Source: §6.4 · p. 34
The cited result bounds the quantity Δ_{R,S} uniformly over all choices of R and S: for every R,S ⊆ [t], Δ_{R,S} ≤ 2^-n^γ + ε.With probability at least 1 − 2^-n^Ω(1), Z ≠ Z(i) for each i ∈ [t].Source: §6.4 · pp. 35–36

7 An Explict Seeded Non-Malleable Extractor at Polylogarithmic Min-entropy

The section constructs a seeded non-malleable extractor and proves security against multiple fixed-point-free seed tamperings. Its theorem covers min-entropy k≥C log^(2+γ) n with error O(ε), subject to the stated parameter restriction.

Subroutines and Parameters

The parameter setup restricts the tampering degree to t≤k^(γ/2).The theorem's guarantee applies to the t fixed-point-free tampering functions under this stated parameter condition.Source: Subroutines and Parameters · pp. 36–37
The construction's setup combines strong seeded extractors with a look-ahead extractor and a two-step alternating-extraction protocol.The protocol uses m=n4-bit communicated variables, with Extq and Extw as its strong seeded extractors.Source: Subroutines and Parameters · p. 37
For min-entropy k≥C log^(2+γ) n, the constructed extractor satisfies the stated non-malleability guarantee with error O(ε).The theorem considers a uniform independent seed and t tampering functions, each with no fixed points.Source: Subroutines and Parameters · pp. 36–37

8 Efficient Encoding and Decoding Algorithms for One-Many NonMalleable Codes

This section develops a linear seeded extractor with equal-size pre-images to support efficient uniform sampling, then uses modified extractor components to construct one-many non-malleable codes. The construction supports efficient pre-image sampling and achieves the stated non-malleability parameters.

8 Efficient Encoding and Decoding Algorithms for One-Many NonMalleable Codes

The construction yields one-many non-malleable codes with tampering degree t = n^Ω(1), relative rate n^Ω(1)/n, and error 2^-n^Ω(1).The section combines the modified extractor with efficient pre-image sampling.Source: §8 · p. 38

8.3 Efficiently Sampling from the Pre-Image of inmExt

The modified extractor components are designed to simplify analysis as functions and enable efficient sampling from their pre-images.The section introduces the modified construction before presenting the sampling algorithms.Source: §8 · p. 38, §8.2 · p. 41, §8.3 · p. 43

8.1 A New Linear Seeded Extractor

The new strong linear seeded extractor for high min-entropy sources has seed length close to its output length and equal-size pre-images across seed fixings.The preceding sampling approach requires ε = o(2^-m), which would force seed length O(m^2) and leave seeds too short for alternating extraction.Source: §8.1 · p. 39
For a 0.9n-min-entropy source, iExt extracts with an independent uniform seed and gives every output pre-image size 2^n-m for every seed.This equal-size property supports efficient uniform sampling from the pre-image.Source: §8.1 · pp. 40–41

8.2 A Modified Construction of the Seedless (2, t)-Non-Malleable Extractor

To enable uniform pre-image sampling, the construction uses a Reed-Solomon code and unused source blocks so sampling constraints remain independent of alternating-extraction constraints.The unused blocks provide variables for the constraints imposed by the initial sampling step.Source: §8.2 · pp. 41–42
The modified seedless (2, t)-non-malleable extractor has error 2^-n^Ω(1), with alternating extraction using new source blocks across rounds.The construction uses iExt in place of seeded extractors and divides the sources into blocks that retain near-full min-entropy after conditioning.Source: §8.2 · pp. 41, 43

13 end

The section establishes that the extractor's pre-images can be efficiently sampled uniformly. Its component pre-images are subspaces whose sizes do not depend on the sampler inputs, enabling the final sampling procedure.

13 end

Each 2ilaExt pre-image is an F2-subspace of dimension d1, with size independent of Samp2's inputs.The result applies to the component sampler's pre-image for the specified output pair.Source: §13 · p. 44
For fixed auxiliary variables, inmExt's pre-image is an F2-subspace whose size is independent of the inputs to Sampnm.This property supports composing the component samplers into a uniform sampler for the full pre-image.Source: §13 · p. 46
Fixing sampled Reed-Solomon coordinates restricts the source to a subspace of dimension n4 − n5 over F.The code's generator matrix uses distinct non-zero field elements.Source: §13 · p. 46
An efficient procedure samples uniformly from the full pre-image of inmExt for any given output pair.It samples auxiliary variables and then uses Sampnm to generate an input pair from the corresponding pre-image.Source: §13 · p. 47