PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-complexity Multiclass Encryption by Compressed Sensing

Valerio Cambareri, Mauro Mangia, Fabio Pareschi, Riccardo Rovatti, Gianluca Setti

arXiv:1307.3360v4cs.ITmath.IT

TL;DR

The paper examines whether compressed sensing can provide privacy for acquired data where a low-cost encryption mechanism is appealing. It proposes sharing the same measurements with receiver classes holding differently corrupted encoding matrices. Its analysis finds limited, non-perfect security, including asymptotic indistinguishability for equal-energy signals and finite-dimension detection of small energy differences.

  • Problem

    The paper asks how compressed sensing can address privacy for acquired and distributed data when an almost-zero-cost encryption mechanism is appealing.

    Source: §I · p. 2

  • Method

    The scheme distributes the same CS measurements to receiver classes with partially corrupted encoding matrices, producing different levels of signal recovery quality.

    Source: §V · p. 18

  • Results

    Same-energy signals encoded with an i.i.d. Bernoulli matrix become statistically indistinguishable as n grows, while finite-n hypothesis testing detects even small energy differences.

    Source: §V · p. 18

  • Takeaways & Limitations

    The simple encoding offers a limited, zero-cost form of encryption while allowing different receiver classes different reconstruction capabilities.

    Source: §V · p. 18

    Because CS encoding is linear, it cannot completely hide information.

    Source: A. Security Limits · p. 10

Abstract

from arXiv · show

The idea that compressed sensing may be used to encrypt information from unauthorised receivers has already been envisioned, but never explored in depth since its security may seem compromised by the linearity of its encoding process. In this paper we apply this simple encoding to define a general private-key encryption scheme in which a transmitter distributes the same encoded measurements to receivers of different classes, which are provided partially corrupted encoding matrices and are thus allowed to decode the acquired signal at provably different levels of recovery quality. The security properties of this scheme are thoroughly analysed: firstly, the properties of our multiclass encryption are theoretically investigated by deriving performance bounds on the recovery quality attained by lower-class receivers with respect to high-class ones. Then we perform a statistical analysis of the measurements to show that, although not perfectly secure, compressed sensing grants some level of security that comes at almost-zero cost and thus may benefit resource-limited applications. In addition to this we report some exemplary applications of multiclass encryption by compressed sensing of speech signals, electrocardiographic tracks and images, in which quality degradation is quantified as the impossibility of some feature extraction algorithms to obtain sensitive information from suitably degraded signal recoveries.

I. INTRODUCTION

The paper uses compressed sensing (CS) encoding to add low-cost security at acquisition and give receiver classes different recovery quality. It analyzes the security trade-offs and relates the approach to prior work on CS secrecy and matrix perturbations.

I. INTRODUCTION

  • CS with Bernoulli random encoding matrices is proposed as a low-cost way to embed security in acquisition while balancing security properties against resource requirements.The scheme aims to provide different access levels by varying receivers’ knowledge of the true encoding matrix.Source: §I · p. 2
  • Receivers share measurements but receive complete or incomplete keys, so partial matrix corruption limits recovery quality while unknown matrices leave the signal fully encrypted.The scheme alters signs of randomly selected entries in the true ±1-valued Bernoulli matrix.Source: §I · p. 2
  • CS is not perfectly secure, but the paper reports that statistical analysis of measurements reveals only limited information, chiefly signal power, with sharp convergence at finite dimensions.The authors leave more threatening non-statistical attacks to future work.Source: §I · p. 3
  • Applications to images, electrocardiographic tracks, and speech assess whether degraded recoveries prevent feature-extraction algorithms from revealing sensitive information.The paper frames this as a way to hide selected signal features from certain receiver classes.Source: §I · p. 3

A. Relation to Prior Work

  • The paper extends prior CS security analyses with an asymptotic secrecy notion for equal-power signals and hypothesis testing of finite-dimensional measurements.It also adapts perturbation-recovery results to bound lower-class users’ worst-case recovery and develops best-case bounds to distinguish user classes.Source: A. Relation to Prior Work · p. 3

II. MULTICLASS COMPRESSED SENSING

The section sets out compressed sensing, its private-key interpretation, and the signal assumptions used in the security analysis. It describes sparse recovery from fewer measurements and models signals and their encoded measurements.

A. Brief Review of Compressed Sensing

  • CS represents a signal sparsely in a suitable basis and maps it to fewer measurements, from which the signal can be recovered under suitable assumptions.The section describes recovery even when m < n.Source: A. Brief Review of Compressed Sensing · p. 4

B. A Cryptographic Perspective

  • In the cryptographic interpretation, the signal is plaintext, its CS measurements are ciphertext, and a shared seed can generate the encoding matrices used by the decoder.The seed is expanded by a pseudorandom number generator, assumed to have a sufficiently long sequence period.Source: B. A Cryptographic Perspective · p. 4

C. Signal Models and Assumptions

  • The security analysis uses general moment assumptions for random-vector or random-process plaintexts and maps them through the encoding matrix to measurement ciphertexts.When no signal model is specified, the analysis considers a single realization in the standard CS framework.Source: C. Signal Models and Assumptions · p. 5

D. Multiclass Encryption by Compressed Sensing

The scheme gives receivers different recovery quality by sharing measurements while varying how much of the encoding matrix each receiver knows. It creates this mismatch by randomly flipping matrix signs, then extends the two-class design to multiple classes.

1) Two-Class Scheme:

  • The two-class design flips a random subset of encoding-matrix signs; the resulting matrices are statistically indistinguishable within the same i.i.d. Bernoulli ensemble.The perturbation density η controls the recovery-performance bounds and can be chosen to set the desired quality range.Source: 1) Two-Class Scheme · pp. 5–6
  • A receiver using a corrupted encoding matrix treats the mismatch as signal-dependent additive noise, while a receiver with the true matrix can recover the exact sparse solution under the stated noise-free and sampling conditions.The perturbation is ε = ∆Ax; the first-class decoder can recover exactly when m is sufficiently larger than k.Source: 1) Two-Class Scheme · p. 6

2) Multiclass Scheme:

  • The scheme extends to w classes by applying sign flips to disjoint index subsets, giving receivers different partial knowledge of the encoding and thus different recovery quality.The highest-class receiver knows the complete encoding matrix; lower and intermediate classes know less complete versions.Source: 2) Multiclass Scheme · pp. 6–7

3) A System Perspective:

The system implements class-specific access through shared keys that let higher-class decoders reconstruct the true encoding matrix while lower-class decoders cannot. The lower-class recovery analysis bounds the error caused by this mismatch, subject to stated assumptions.

3) A System Perspective:

  • Multiclass compressed sensing has small computational overhead: the encoder and high-class decoder use the same matrix-generation scheme, while lower-class decoders lack keys needed to reconstruct the true matrix.Sign-flipping is a post-processing step using the same PRNG architecture, with minimal computational cost.Source: 3) A System Perspective · p. 7
  • The matrix-reuse period must be sufficiently large to avoid attacks using multiple plaintext-ciphertext pairs to recover all or part of the encoding matrix.The text notes that the PRNG values are not exposed, allowing cryptographically secure generators to be avoided under this reuse condition.Source: 3) A System Perspective · p. 7

1) Second-Class Recovery Error – Lower Bound:

  • With high probability, the second-class decoder's recovery error exceeds a lower bound determined by perturbation density, undersampling rate, and signal energy or power.The asymptotic corollary gives a probability-one bound under mild assumptions on the random process; these bounds are reference best cases absent other noise sources.Source: 1) Second-Class Recovery Error – Lower… · pp. 8–9
  • At η = 0.1594, the stated example gives a minimum recovery-error norm of 19.61 dB with probability 0.98 for signals of average energy 1.The example uses m = 512 and n = 1024.Source: 1) Second-Class Recovery Error – Lower… · pp. 8–9

2) Second-Class Recovery Error – Upper Bound:

The paper adapts a perturbed-matrix recovery bound to estimate an upper bound for second-class recovery error. Its RIP-based conditions are restrictive, so the authors also turn to a less rigorous least-squares analysis for average performance.

2) Second-Class Recovery Error – Upper Bound:

  • The upper bound adapts perturbed-encoding recovery theory to basis pursuit denoising for plaintexts with exactly k-sparse representations and no other noise.It models the mismatched decoder matrix as A(0) = A(1) − ∆A.Source: 2) Second-Class Recovery Error – Upper… · p. 9
  • The cited singular-value estimates would hold only for the identity basis, and their universal constants require numerical evaluation.This motivates estimating the required quantities directly by Monte Carlo simulation.Source: 2) Second-Class Recovery Error – Upper… · p. 9
  • Monte Carlo estimates of the required constants use 10^4 matrix-submatrix instances with m = 512, k = 2, 4, …, 64, and η from 5 · 10^-4 to 10^-2.The encoding basis is a random orthonormal basis.Source: 2) Second-Class Recovery Error – Upper… · pp. 9–10, Figure 2 · p. 10
  • The RIP-based bound applies only over a small η range and when solving (P2); typical recovery errors are substantially smaller than this bound.The reported compliance with Proposition 1 occurs only when η ≤ 8 · 10^-3; the authors therefore use a less rigorous least-squares approach to bound average recovery quality.Source: 2) Second-Class Recovery Error – Upper… · p. 10

III. A CRYPTANALYSIS OF COMPRESSED SENSING

Compressed sensing’s linear encoding cannot completely hide plaintext information, but random measurements provide asymptotic spherical secrecy: ciphertexts conceal plaintexts with equal power. Finite-sample tests show that equal-energy orthogonal plaintexts are statistically indistinguishable, while even a small energy difference can be detected.

A. Security Limits

  • Statistical analysis of ciphertexts can reveal a plaintext’s scaling factor, so compressed sensing cannot provide perfect secrecy.The paper states that scaling is all that can be inferred from this statistical analysis.Source: A. Security Limits · p. 10
  • Linearity propagates scaling and continuity, so scaling relationships and nearby plaintexts can remain visible in their ciphertexts.For a fixed encoding matrix, nearby plaintexts map to nearby ciphertexts; the paper also notes that this weakens the analog diffusion property.Source: A. Security Limits · pp. 10–11

1) Asymptotic Security:

  • With universal random encoding matrices, measurements are asymptotically independent and spherical-secret given plaintext power, concealing other plaintext information.The result applies to bounded-value plaintexts of finite power and gives convergence to a Gaussian distribution with variance determined by plaintext power.Source: 1) Asymptotic Security · pp. 11–12
  • For n = 256, plaintexts with the same energy had ciphertext distributions that were statistically indistinguishable; a 1% energy difference caused statistically detectable deviations and correct inference of the true plaintext.The comparison used ex′ = ex′′ = 1 versus ex′′ = 1.01, with P = 5000 p-values.Source: 1) Asymptotic Security · pp. 12–13

2) Non-Asymptotic Security:

The paper bounds how quickly random measurements approach their limiting Gaussian behavior and empirically evaluates the bound. It concludes that straightforward statistical attacks reveal only limited plaintext information beyond its power.

2) Non-Asymptotic Security:

  • With probability exceeding 1 − ρ, random measurements converge at rate O(n^-1) to N(0, e_x).The bound applies to random matrices with i.i.d. zero-mean, unit-variance entries and finite fourth moment.Source: 2) Non-Asymptotic Security · p. 13
  • For the example evaluated, when ρ ≥ 10^-3, Proposition 3 holds with C(ρ) = 1.34 · 10^-2.C(ρ) was empirically evaluated using plaintexts sampled on the sphere.Source: 2) Non-Asymptotic Security · p. 13, Figure 4 · p. 14
  • Straightforward statistical attacks on a compressed-sensing ciphertext may extract only very limited plaintext information, beyond its energy.The paper identifies known-plaintext attacks as a next level of threat and leaves their robustness analysis for future work.Source: 2) Non-Asymptotic Security · pp. 13–14

IV. APPLICATION EXAMPLES

The application experiments compare first-class and lower-class recovery and assess whether feature extraction can recover sensitive content. Across the explored settings, GAMP achieved the highest lower-class average recovery SNR.

A. Experimental Framework

  • The framework compares first-class recovery with second-class recovery at fixed perturbation density and uses feature extraction to test recovered signals for sensitive content.The examples target English speech, ECG PQRST peaks, and printed text in images.Source: A. Experimental Framework · p. 14

1) Recovery Algorithms:

  • GAMP achieved the highest lower-class average recovery SNR in all explored settings.The tested algorithms were BPDN, CoSaMP, and GAMP; tests were genie-aided and tuned to optimize recovery performance.Source: 1) Recovery Algorithms · p. 15
  • The perturbation density η is the main design parameter and is chosen against a reference lower-class recovery algorithm.The authors evaluated algorithms that jointly identify the signal and perturbation matrix separately as explicit attacks.Source: 2) Average Signal-to-Noise Ratio Bounds · p. 15, 1) Recovery Algorithms · p. 15

2) Average Signal-to-Noise Ratio Bounds:

The paper derives average recovery-SNR bounds and illustrates multiclass recovery on speech and ECG signals. Increasing perturbation degrades lower-class recovery, with speech recognition and ECG peak detection providing task-specific measures of the degradation.

2) Average Signal-to-Noise Ratio Bounds:

  • The derived bounds provide criteria to estimate the range of lower-class average recovery performances, though the rigorous error bound applies only for small (k, η).The authors use an additional typical-recovery approximation to cover a larger range.Source: 2) Average Signal-to-Noise Ratio Bounds · p. 15

B. Speech Signals

  • At η = 0.03, first-class speech recovery had RSNR = 36.58 dB, while second-class recovery had RSNR = 8.42 dB and a corresponding word-recognition ratio of 14 against 8 14.The second-class signal was sufficiently corrupted to avoid straightforward ASR, although both example sentences remained intelligible to a human listener.Source: B. Speech Signals · p. 17

C. Electrocardiographic Signals

  • For ECG, first-class recovery had ARSNR = 25.36 dB; at η = 0.03, second-class recovery had ARSNR = 11.08 dB.Second-class R-peak displacement was 4.4 ms_rms, while displacement of the other P,Q,S,T peaks was 55.3 ms_rms; these displacements increased as η varied from 0 to 0.05.Source: C. Electrocardiographic Signals · pp. 17–18

D. Sensitive Text in Images

The sensitive-text image example tests whether perturbing the encoding matrix degrades second-class image recovery enough to frustrate OCR. The conclusion presents compressed sensing as a limited, zero-cost encryption option and summarizes its statistical leakage findings.

D. Sensitive Text in Images

  • The image example applies two-class compressed sensing to identification text in a selected area of each image.Images are encoded in 64×64-pixel blocks; the strategy covers a relevant 3×4-block area.Source: D. Sensitive Text in Images · p. 18
  • As perturbation density η increases, OCR recognizes fewer consecutive characters, progressively impeding second-class users from extracting text.The images were preprocessed before Tesseract OCR; recovery SNR also degrades rapidly as η increases.Source: D. Sensitive Text in Images · p. 18

V. CONCLUSION

  • The conclusion describes compressed sensing as a limited, zero-cost form of encryption with no additional computational complexity.The authors suggest it may interest designers of secure, resource-limited sensing interfaces.Source: §V · p. 18
  • With i.i.d. Bernoulli encoding matrices, statistical leakage is limited to plaintext power asymptotically, with an O(1/n) convergence rate.The conclusion also reports statistically indistinguishable ciphertexts for equal-energy plaintexts, while small energy differences can be detected at finite n.Source: §V · p. 18
  • The conclusion presents multiclass encryption as giving receivers the same measurements but recovery quality that depends on their class and private key.The examples include speech, electrocardiographic signals, and images.Source: §V · pp. 18–19

APPENDIX A

Appendix A develops probabilistic bounds used to establish recovery-error results. Its proof uses moments of the perturbation term and considers both finite-dimensional and asymptotic settings.

APPENDIX A

  • A probabilistic lemma bounds the Euclidean norm of the mismatch term using its first and second moments.The moment calculation assumes independence between the signal-related variable and the perturbation matrix.Source: RECOVERY ERROR LOWER BOUND · pp. 19–20
  • The proof relates a second-class decoder's reconstruction error to the encoding-matrix mismatch acting on the signal.It writes the received measurements using the true matrix and equates them to reconstruction under the corrupted matrix.Source: RECOVERY ERROR LOWER BOUND · pp. 21–22
  • The asymptotic argument assumes an α-mixing random process with uniformly bounded fourth moments.The appendix uses these assumptions in the proof leading to the stated asymptotic recovery-error result.Source: RECOVERY ERROR LOWER BOUND · pp. 21–22

APPENDIX B

Appendix B verifies distributional results for measurements formed by random encoding. It uses a central limit theorem argument and states the resulting normal-distribution conclusions.

APPENDIX B

  • The proof verifies the Lindeberg–Feller central limit theorem for measurement variables formed from independent random-matrix entries.The entries are described as zero-mean, unit-variance random variables with finite fourth moments.Source: OF COMPRESSED SENSING · p. 22
  • Conditioned on a plaintext, the measurement variable is normally distributed in the stated limiting result.The appendix identifies its variance in the following result passage.Source: OF COMPRESSED SENSING · p. 22
  • The proof distinguishes the fourth-moment parameter δ for Bernoulli and standard normal encoding matrices: 1 and 3, respectively.For Bernoulli matrices, the argument scales the normal density to the plaintext energy to obtain the stated proposition.Source: OF COMPRESSED SENSING · pp. 22–23
Loading 1307.3360v4…