Secure and efficient compressed sensing based encryption with sparse matrices

Abstract

In this thesis, we study the security of a compressed sensing (CS) based cryptosystem called a sparse one-time sensing (S-OTS) cryptosystem, which encrypts each plaintext with a sparse measurement matrix. To generate the secret matrix and renew it at each encryption, a bipolar keystream and a random permutation pattern are employed as cryptographic primitives, which are obtained by a keystream generator of stream ciphers. With a small number of nonzero elements in the measurement matrix, the S-OTS cryptosystem achieves an efficient CS encryption process in terms of data storage and computational cost. For security analysis, we show that the S-OTS cryptosystem can be computationally secure against ciphertext only attacks (COA) in terms of the indistinguishability, as long as each plaintext has constant energy. Also, we consider a chosen plaintext attack (CPA) against the S-OTS cryptosystem, which consists of two stages of keystream and key recovery attacks. Then, we show that the S-OTS cryptosystem can achieve the security against the CPA of keystream recovery with overwhelmingly high probability, as an adversary needs to distinguish a prohibitively large number of candidate keystreams. Finally, we conduct an information-theoretic analysis to demonstrate that the S-OTS cryptosystem has sufficient resistance against the CPA of key recovery by guaranteeing the extremely low probability of success. In conclusion, the S-OTS cryptosystem can be indistinguishable and secure against a CPA, while providing efficiency in CS encryption.