Low-Complexity Multiclass Encryption by Compressed Sensing

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

The idea that compressed sensing may be used to encrypt information from unauthorized 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 analyzed: first, 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.

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 knownplaintext attacks, therefore increasing its appeal as a negligible cost encryption method for resource-limited sensing applications.

Publication Status:
Part I: Cambareri, V.; Mangia, M.; Pareschi, F.; Rovatti, R.; Setti, G., "Low-Complexity Multiclass Encryption by Compressed Sensing," IEEE Transactions on Signal Processing, vol.63, no.9, pp.2183,2195, May 1, 2015, doi: 10.1109/TSP.2015.2407315
Available on IEEE Xplore.

Part II: Pending peer review on the IEEE Transactions on Information Forensics and Security.
Draft available upon request.

BibTeX Entries:

author={Cambareri, V. and Mangia, M. and Pareschi, F. and Rovatti, R. and Setti, G.},
journal={IEEE Transactions on 
Signal Processing}, 
title={Low-Complexity Multiclass Encryption by Compressed Sensing},
keywords={Channel coding;Compressed sensing;Decoding;Encryption;Receivers;Compressed sensing;encryption;secure communications;security},

The supporting code is hosted at Google Code due to the variety of experiments proposed in the two papers.