Perfect secrecy via compressed sensing

Abstract

In this paper we consider the compressive sensing based encryption and proposed the conditions in which the perfect secrecy is achievable. We prove that when the measurement matrix holds the Restricted Isometry Property (RIP) and the number of measurements is more than two times of the sparsity level, i.e., M ⩾2k, the Shannon perfect secrecy condition is achievable either i) the cardinality of the message set tends to infinity or ii) the message set does not include the zero message. As an implicit assumption, we suppose that the eavesdropper has not access to the secret key during the transmission.