PaperlayerView exact revision on arXiv

Source-linked AI summary

Semantically Secure Lattice Codes for the Gaussian Wiretap Channel

Cong Ling, Laura Luzzi, Jean-Claude Belfiore, Damien Stehlé

arXiv:1210.6673v3cs.IT

TL;DR

The paper tackles semantic security and strong secrecy for Gaussian wiretap channels without assuming a message distribution. It uses the flatness factor and secrecy-good lattices, with discrete Gaussian coding achieving secrecy capacity within 1/2 nat under mild conditions.

  • Problem

    The problem is achieving strong secrecy and semantic security when plaintext messages need not be uniformly random.

  • Method

    The method uses the flatness factor to characterize conditional-output convergence and leakage, then applies secrecy-good lattices with discrete Gaussian coding over lattice cosets.

  • Results

    The proposed Gaussian-wiretap scheme achieves secrecy capacity within 1/2 nat under very mild assumptions using MMSE-renormalized Euclidean lattice decoding.

  • Takeaways & Limitations

    The flatness factor provides a design criterion for secrecy-good lattices, while the schemes require neither an a priori message distribution nor dither.

Abstract

from arXiv · show

We propose a new scheme of wiretap lattice coding that achieves semantic security and strong secrecy over the Gaussian wiretap channel. The key tool in our security proof is the flatness factor which characterizes the convergence of the conditional output distributions corresponding to different messages and leads to an upper bound on the information leakage. We not only introduce the notion of secrecy-good lattices, but also propose the {flatness factor} as a design criterion of such lattices. Both the modulo-lattice Gaussian channel and the genuine Gaussian channel are considered. In the latter case, we propose a novel secrecy coding scheme based on the discrete Gaussian distribution over a lattice, which achieves the secrecy capacity to within a half nat under mild conditions. No \textit{a priori} distribution of the message is assumed, and no dither is used in our proposed schemes.

I. INTRODUCTION

The paper addresses the need for strong secrecy and semantic security in continuous Gaussian wiretap channels without assuming uniformly random messages. It develops lattice-based schemes using flatness-factor analysis, including a discrete-Gaussian construction approaching secrecy capacity within 1/2 nat.

  • Motivation: Weak secrecy can permit unbounded total leakage, motivating strong secrecy, which requires mutual information to vanish as block length grows.Strong secrecy is expressed as lim n→∞ I(M; Z^n) = 0.
  • Motivation: Semantic security removes the assumption that plaintext messages are uniformly random by protecting arbitrary message distributions.The paper extends the equivalence between strong secrecy for all message distributions and semantic security to continuous wiretap channels.
  • Main Contributions: The proposed codes achieve strong secrecy and semantic security over continuous Gaussian wiretap channels using secrecy-good lattices and the flatness factor.The flatness factor characterizes conditional-output convergence and information leakage, while secrecy-goodness becomes a lattice design criterion.
  • Main Contributions: The Gaussian-wiretap construction uses discrete Gaussian distributions over cosets of a secrecy-good coarse lattice and MMSE lattice decoding.The scheme applies lattice Gaussian coding and uses MMSE-renormalized Euclidean lattice decoding at the legitimate receiver.
  • Main Contributions: The Gaussian-wiretap scheme approaches secrecy capacity within 1/2 nat under very mild assumptions.The stated gap is measured in nats, consistent with the paper’s logarithm convention.
  • Main Contributions: The approach assumes no plaintext-message distribution and uses no dither, which may simplify implementation.Security is claimed for any particular message rather than only a uniformly distributed message.

C. Equivalence

For continuous wiretap channels, the paper establishes equivalence between semantic security and strong secrecy for all message distributions. It supports this connection with variational-distance bounds and uses lattice and theta-series tools in the broader coding analysis.

  • C. Equivalence: Semantic security and strong secrecy for all message distributions are equivalent for continuous wiretap channels.The paper presents this as an extension of earlier discrete-channel results.
  • C. Equivalence: Distinguishing security implies strong secrecy for every message distribution through bounds on conditional-output variational distances.The argument bounds leakage using the maximum variational distance between conditional eavesdropper-output distributions.
  • C. Equivalence: Strong secrecy for all message distributions implies distinguishing security by applying Pinsker’s inequality and the triangle inequality.The proof specializes the message distribution to point masses and then converts relative-entropy control into variational-distance control.
  • C. Equivalence: Approximating every conditional output distribution by a message-independent density yields an upper bound on mutual information.If each conditional output is within ε_n in variational distance, the average distinguishing advantage is at most 2ε_n.
  • C. Equivalence: The paper uses lattice codes to achieve semantic security over the wiretap channel.The subsequent analysis introduces mathematical tools for describing and analyzing these codes.
  • A. Preliminaries on Lattices: An n-dimensional lattice is generated by linearly independent basis vectors, with quantization, modulo-lattice operations, Voronoi cells, and nested-lattice cosets supporting coding analysis.The fine/coarse lattice pair has quotient order equal to the ratio of their Voronoi-cell volumes.
  • B. Lattice Theta Series: Construction-A mod-p lattices are formed from linear codes over Z_p, with scaled-lattice volume determined by block length and code dimension.For a scaled lattice aΛ_C, the fundamental volume is V(aΛ_C) = a^n p^(n-k).
  • B. Lattice Theta Series: For balanced code ensembles, Lemma 3 characterizes the average behavior of the theta series at fixed volume and parameter τ.The lemma applies when 0 < k < n.

C. Lattice Gaussian Distribution

This section defines lattice Gaussian distributions and the flatness factor, then characterizes the factor through theta-series and VNR properties. It establishes a phase transition and identifies lattices whose flatness factors vanish or grow exponentially.

  • Flatness factor: The flatness factor measures the maximum variation of the lattice Gaussian density from the uniform distribution over a fundamental region.It lies within 1 ± ǫΛ(σ) of uniformity and can be expressed using the dual lattice and theta series.
  • Flatness factor: The flatness factor decreases with σ, is ordered oppositely under lattice inclusion, and is invariant under simultaneous scaling of lattice and σ.For Λ2 ⊂ Λ1, ǫΛ1(σ) ≤ ǫΛ2(σ), while ǫΛ(σ) = ǫaΛ(aσ).
  • Relation to smoothing parameter: The flatness factor has communication-specific advantages over the smoothing parameter because it supports theta-series bounds and both large and small values of ε.The paper notes that ε, rather than the smoothing parameter, is more directly relevant to communications.
  • Uniformity: If ǫΛ(σ) → 0, the lattice Gaussian density converges uniformly to the uniform distribution on a fundamental region.The same factor also bounds the variational distance between a Gaussian reduced modulo a fundamental region and the uniform distribution.
  • Phase transition: Theorem 1 exhibits a phase transition at γΛ(σ) = 2π, with lattice sequences whose flatness factors vanish or diverge exponentially on opposite sides.For γΛ(n)(σ) < 2π, one sequence has exponentially vanishing flatness factor; for γΛ′(n)(σ) > 2π, another has exponentially growing flatness factor.
  • Phase transition: For γΛ(n)(σ) < π/2, the flatness factor can vanish exponentially with probability higher than 1 − 2^-n over the mod-p lattice ensemble.This ensemble result is slightly weaker than the theorem’s bound but is stated to make construction potentially more practical.

E. Properties of the Flatness Factor

This section derives consequences of a small flatness factor for nested-lattice distributions, Gaussian approximation, and discrete-Gaussian moments and entropy. These properties support the later secrecy analysis.

  • Nested-lattice distributions: When the coarse lattice has small flatness factor, a discrete Gaussian over the fine lattice induces nearly uniform cosets.The corresponding converse reconstructs a discrete Gaussian by combining a uniformly selected coset with a shifted discrete Gaussian on the coarse lattice.
  • Moments: When the flatness factor is small, the discrete Gaussian’s variance per dimension is close to σ2.The paper notes that the corresponding bound improves a prior lemma by removing an additional factor n and relaxing a condition involving ǫΛ(σ/2).
  • Moments: The variance condition can use ǫΛ(σ/c) < 1 with c arbitrarily close to 1, at the cost of a growing constant C.The displayed sufficient condition uses the coefficient π−1/e ≈ 1.06.
  • Entropy: A small flatness factor makes the discrete Gaussian entropy approach the differential entropy of a continuous Gaussian with variance σ2 per dimension, minus log V(Λ).The comparison is made against the entropy of a uniform distribution over the lattice’s fundamental region.
  • Gaussian approximation: Adding a continuous Gaussian to a discrete Gaussian produces a distribution close in L1 distance to a continuous Gaussian.The resulting Gaussian has variance combining the discrete and continuous Gaussian variances.

IV. MOD-Λ GAUSSIAN WIRETAP CHANNEL

The mod-Λ Gaussian wiretap model uses nested lattices, coset-based message encoding, and random fine-lattice points. A small eavesdropper-lattice flatness factor yields strong secrecy, including exponentially vanishing leakage under a sufficient SNR condition.

  • Channel model: The mod-Λs wiretap channel has nested lattices Λs ⊂ Λe ⊂ Λb, with Λs shaping the input while Bob and Eve receive modulo-lattice Gaussian outputs.The transmitted codebook must also satisfy an average power constraint, with separate noise variances and SNRs for Bob and Eve.
  • Encoding: Each message is mapped to a coset in Λb/Λe, while Alice randomizes within the corresponding Λe coset using a discrete uniform distribution over Λe ∩ V(Λs).She transmits the sum of the randomized lattice point and the message’s coset representative.
  • Secrecy analysis: The secrecy condition depends on the flatness factor of Λe, even though the channel is reduced modulo Λs.The conditional output distributions at Eve are compared through variational distance, which then bounds leaked mutual information.
  • Scope: The mod-Λ channel discussion does not consider MMSE filtering, although filtered lattice sequences are known to approach AWGN capacity.This scope boundary concerns the channel-capacity comparison rather than the secrecy construction itself.
  • Secrecy guarantees: If Eve’s generalized SNR γΛe(σe) is smaller than 1, suitable mod-p lattice codes achieve strong secrecy with mutual information vanishing exponentially fast.Theorem 1 supplies lattice sequences with exponentially small eavesdropper flatness factor for this regime.
  • Secrecy-good lattices: The paper defines secrecy-good lattices as lattice sequences with sufficiently small flatness factor to make information leakage exponentially small.The definition is generalized to include lattices whose theta series are close to, but not strictly below, the Minkowski–Hlawka bound.

D. Existence of Good Wiretap Codes from Nested Lattices

The paper establishes nested lattice sequences that jointly provide reliability for the legitimate receiver and strong secrecy for the eavesdropper. The achievable strong secrecy rate approaches the relevant upper bound within a half nat under high-SNR conditions.

  • D. Existence of Good Wiretap Codes from Nested Lattices: Nested lattice sequences can guarantee both strong secrecy rates and reliability for the legitimate receiver.The construction adds secrecy-goodness while maintaining the coding properties needed for reliable transmission.
  • D. Existence of Good Wiretap Codes from Nested Lattices: Exponentially vanishing decoding error is achievable at Bob when R + R′ < 1/2 log SNR_b.This follows from using AWGN-good lattices without MMSE filtering.
  • D. Existence of Good Wiretap Codes from Nested Lattices: A half nat separates the achieved high-SNR strong secrecy rate from the lower bound on secrecy capacity.The same half-nat proximity is stated for the infinite-constellation limit.
  • D. Existence of Good Wiretap Codes from Nested Lattices: Each bin approaches the eavesdropper’s output under a uniform input in variational distance, so bins act as resolvability codes.The bin rate must exceed Eve’s channel capacity when the target output distribution is capacity-achieving.
  • D. Existence of Good Wiretap Codes from Nested Lattices: The genuine Gaussian wiretap channel removes the restriction that Eve use a modulo operation at the receiver front end.The channel has Gaussian outputs at Bob and Eve and imposes an average power constraint P.

B. Lattice Gaussian Coding

Lattice Gaussian coding assigns messages to lattice cosets and samples a discrete Gaussian within each coset. The flatness factor makes the resulting conditional distributions at Eve converge, yielding an information-leakage bound and strong secrecy under suitable conditions.

  • B. Lattice Gaussian Coding: Each message is mapped one-to-one to a coset of Λ_b/Λ_e, with encoding performed by sampling a discrete Gaussian over that coset.The scheme does not assume an a priori distribution for the message.
  • B. Lattice Gaussian Coding: Coset distributions share the same zero-centered continuous Gaussian profile, helping conditional outputs for different messages converge.For Λ_e = 2Z and σ_s = 2, the distributions over 2Z and 2Z+1 illustrate this construction.
  • C. Achieving Strong Secrecy: Suitable hypotheses make Eve’s conditional output distributions converge in variational distance to one continuous Gaussian distribution.An upper bound on leaked information follows from this convergence through the flatness-factor analysis.
  • C. Achieving Strong Secrecy: If ε_n = ϵ_Λe(σ̃_e) < 1/2 for all n, Theorem 4 bounds the mutual information between the confidential message and Eve’s signal.The resulting sufficient condition is that the relevant flatness factor tends to zero, implying I(M; Z^n) → 0.
  • C. Achieving Strong Secrecy: At high SNR, the genuine Gaussian and modulo-Λ secrecy requirements become equally demanding as σ̃_e → σ_e when σ_s → ∞.The condition σ̃_e < σ_s requires the flatness factor at the relevant power to be small, so a minimum power is needed.
  • C. Achieving Strong Secrecy: The bin rate can be chosen close to Eve’s channel capacity because each bin functions as a resolvability code.This requirement is the continuous-channel counterpart of the strong-secrecy construction described for the modulo-Λ case.

D. Achieving Reliability

The section establishes reliability for lattice Gaussian coding using MAP or MMSE-renormalized lattice decoding. Under AWGN-good and secrecy-good lattice conditions, strong secrecy rates near the Gaussian wiretap secrecy capacity are achievable, with a gap within a half nat under stated SNR conditions.

  • Decoding rule: MAP decoding for discrete Gaussian lattice inputs is equivalent to Euclidean lattice decoding with a renormalized metric asymptotically close to the MMSE metric.The nonuniform prior on lattice points makes MAP decoding distinct from standard ML decoding.
  • Equivalent noise: The equivalent noise becomes asymptotically independent of the message and close to a continuous Gaussian distribution.This removes the need for dither in the reliability analysis.
  • Achievable rates: If Λ_b is AWGN-good and Λ_e is secrecy-good, rates satisfying the theorem’s SNR-dependent bound are achievable with discrete Gaussian coding and MMSE-renormalized decoding.The theorem assumes SNR_b > e and (1 + SNR_b)/SNR_e > e.
  • Reliability: The decoding error probability is bounded by a message-independent Gaussian-noise error probability, up to a factor 1 + 4ε′′.AWGN-goodness then makes the error probability tend to zero exponentially fast when the associated effective-noise condition holds.
  • Capacity gap: The resulting rate is within a half nat of the secrecy capacity when SNR_b · SNR_e > 1.MAP decoding or MMSE estimation improves the first logarithmic term by a constant 1 relative to conventional minimum-distance decoding.
  • Encoding: Efficient encoding samples lattice points from a coset discrete Gaussian using Klein’s algorithm, which has polynomial complexity under a sufficiently large σ_s and a suitably short basis.A short basis may be obtained through lattice reduction such as LLL.

VI. DISCUSSION

The discussion identifies the flatness factor as a lattice parameter for measuring information leakage and designing secrecy-good lattices. It also notes a remaining half-nat gap to secrecy capacity and highlights implementation advantages of coset-based message mapping.

  • Discussion: The flatness factor measures information leakage, indicates whether a lattice is suitable for secrecy coding, and provides a design criterion for wiretap lattice codes.Messages are encoded by cosets rather than particular coset leaders, supporting low-complexity mapping and demapping.
  • Discussion: The half-nat gap to secrecy capacity remains an open direction for understanding intermediate performance and relations among lattice parameters.The authors specifically identify further exploration between the achieved rate and capacity as future work.

APPENDIX I PROOF OF CSISZ ´AR’S LEMMA FOR CONTINUOUS

The appendices prove continuous-channel secrecy relations and construct nested lattices with the required goodness properties. The construction combines random linear codes, Construction A, and asymptotic existence arguments.

  • Continuous secrecy proof: The continuous-channel proof relates mutual-information expressions to variational distance through densities and Jensen’s inequality.The derivation integrates the variational-distance quantity against the output distribution to obtain the information bound.
  • Shaping lattice: The shaping lattice is scaled so that its second moment satisfies σ²(Λ_s) = P, while quantization goodness controls its normalized second moment.The construction uses a scaled Construction-A lattice for power-constrained shaping.
  • Existence proof: The secrecy lattice is secrecy-good under the stated ensemble conditions, and the intersection of goodness events proves existence of a sequence with the required properties.The relevant ensemble has a set of measure greater than 1/2 for secrecy-goodness and a measure tending to 1 for shaping and AWGN goodness.
  • Nested construction: Nested Construction-A lattices satisfy Λ_s ⊆ Λ_e ⊆ Λ_b, with the fine lattice chosen from an AWGN-good ensemble and the secrecy lattice constructed from a nested random code.The code dimensions and field size are selected to maintain the target asymptotic rate.

APPENDIX III PROOFS OF TECHNICAL LEMMAS

The appendix analyzes average theta-series behavior for Construction-A lattices. It establishes conditions under which the relevant asymptotic bounds hold for broad classes of test functions.

  • Theta-series analysis: The average Construction-A lattice behavior is controlled by selecting the scaling and prime parameters so that the lattice volume remains fixed asymptotically.The argument uses superexponential growth of p^n−k and a Minkowski-Hlawka-type average bound.
  • Generalization: The average bound applies beyond the theta series whenever the function satisfies the stated conditions.The authors note that this generality may be independently useful.

B. Proof of the second part of Lemma 5

The proof tightens bounds involving the flatness factor and analyzes convergence rates for the sequence defined by (42). It also notes that scaling handles the general Gaussian parameter case.

  • Flatness-factor bounds: The proof sets ε = ǫΛ′(σ) and applies a bound involving the quotient size |Λ/Λ′| and the flatness factor of Λ′.These quantities enter the conditional bounds used in the proof of Lemma 5.
  • Normalization and scaling: The argument assumes s := √2πσ = 1 for convenience, with the general case obtained by scaling the lattice by s.The proof then uses componentwise bounds for samples from a discrete Gaussian distribution.
  • Bound tightening: A linearity-based overall bound avoids introducing an additional factor n on the right-hand side.The proof further bounds the numerator in expression (53) using the inequality y ≤ ey/e.
  • Bound tightening: For 0 < t ≤ 1/e, the larger solution Y of y = e^ty is used to bound the numerator in (53).For small fixed t, the resulting coefficient approaches 1, but the constant t^-4 + 1 becomes large.
  • Convergence rate: The sequence ˜p(n, k) defined by (42) guarantees convergence faster than exponentially.The proof studies this rate by returning to expression (48) from Lemma 3 and rewriting it together with a lower bound.
Loading 1210.6673v3…