Complete Communications Engineering

In most cryptographic methods, the security of the message is based on the fact that we have transformed the message into something that is not immediately decipherable. When attempts are made to break the code, if a message is extracted that makes sense, i.e. is not just gibberish, it is assumed that the message has been successfully decoded. When using Compressed Sensing (CS) as an encryption scheme, this is not necessarily a valid assumption.

We compress the message x into a coded message y by y = Φ x. Where Φ is the compressed samplingmatrix. In order to decrypt the message, an attacker would need to find both Φ and x that gives y. So, the question becomes does there exist Φ‘ and x‘ such that y = Φx‘. Assuming that any compressed sampling matrix is possible, we see that

Φ‘ = ‖x‘‖-2Φ x (x‘)T

is a possible solution for any other message x‘. This means that it is possible to encrypt one image and an attempt to break the encryption will result in decrypting a different image. This is possible because the system is under-determined, i.e. we know fewer variables than we need to find.

Enhanced Security Based on Under-Determination

The important part of this is Φ‘ being a valid sampling matrix. This is certainly the case if we assume that we communicate the entire sampling matrix. This would be possible for short lived machines such as Unmanned Aerial Vehicles (UAVs) where the matrix could be hard coded and the short life guarantees that there is no need to change the matrix over its lifespan. If we use a smaller key that generates Φ, this will still occur as long as the key is large enough that y = Φkey x is still under-determined.