Analysis of the Security of Compressed Sensing with Circulant Matrices

Recent results have shown that the compressed sensing (CS) framework can provide a form of data confidentiality when the signals are sensed by a fully random matrix. In this paper, we extend those results by considering the security achievable by partially circulant sensing matrices generated from a vector of random variables. Circulant matrices, having similar CS recovery performance as fully random matrices and admitting a fast implementation by means of a fast Fourier transform, are more suitable for practical CS systems. Compared to fully random Gaussian matrices, which leak only the energy of the sensed signal, we show that circulant matrices leak also some information on the autocorrelation of the sensed signal. In order to characterize the above information leakage, we propose an operational definition of security linked to the difficulty of distinguishing equal energy signals and we propose practical attacks to test this definition. The results provide interesting insights on the security of such matrices, showing that a properly randomized partially circulant matrix can provide a weak encryption layer if the signal is sparse in the sensing domain.