On Known-Plaintext Attacks to a Compressed Sensing-based Encryption: A Quantitative Analysis
arXiv:1311.1363 · doi:10.1109/TIFS.2015.2450676
Abstract
Despite the linearity of its encoding, compressed sensing may be used to provide a limited form of data protection when random encoding matrices are used to produce sets of low-dimensional measurements (ciphertexts). In this paper we quantify by theoretical means the resistance of the least complex form of this kind of encoding against known-plaintext attacks. For both standard compressed sensing with antipodal random matrices and recent multiclass encryption schemes based on it, we show how the number of candidate encoding matrices that match a typical plaintext-ciphertext pair is so large that the search for the true encoding matrix inconclusive. Such results on the practical ineffectiveness of known-plaintext attacks underlie the fact that even closely-related signal recovery under encoding matrix uncertainty is doomed to fail. Practical attacks are then exemplified by applying compressed sensing with antipodal random matrices as a multiclass encryption scheme to signals such as images and electrocardiographic tracks, showing that the extracted information on the true encoding matrix from a plaintext-ciphertext pair leads to no significant signal recovery quality increase. This theoretical and empirical evidence clarifies that, although not perfectly secure, both standard compressed sensing and multiclass encryption schemes feature a noteworthy level of security against known-plaintext attacks, therefore increasing its appeal as a negligible-cost encryption method for resource-limited sensing applications.
arXiv commentIEEE Transactions on Information Forensics and Security, accepted for publication. Article in press
References in corpus (7)
- Sparsity and Incoherence in Compressive Sampling
- High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
- Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling
- General Deviants: An Analysis of Perturbations in Compressed Sensing
- Low-complexity Multiclass Encryption by Compressed Sensing
- Rakeness in the design of Analog-to-Information Conversion of Sparse and Localized Signals
- Statistical Mechanics of an NP-complete Problem: Subset Sum
Cited by in corpus (7)
- Bi-level Protected Compressive Sampling
- Robust Coding of Encrypted Images via Structural Matrix
- Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data
- Restricted Structural Random Matrix for Compressive Sensing
- Secure and efficient compressed sensing based encryption with sparse matrices
- Energy Concealment based Compressive Sensing Encryption for Perfect Secrecy for IoT
- Minimizing Acquisition Maximizing Inference -- A demonstration on print error detection