Secure Compressed Sensing over Finite Fields

Abstract

In this paper, we analyze the security of compressed sensing (CS) defined over finite fields. First, we prove that acquiring signals using dense sensing matrices may provide almost perfect secrecy. Then, we prove that using sparse sensing matrices, which admit efficient recovery algorithms mutuated by coding theory, reveals information only on the sparsity of the sensed signal, and that such information is conveyed only by the sparsity of the measurements. Finally, we introduce an operational definition of security, based on the error probability in estimating the signal sparsity, and show that there is a tradeoff between the sparsity of the sensing matrix and the security of the CS system.