Measuring the strength of partial encryption schemes

Partial encryption (PE) of compressed multimedia can greatly reduce the computational complexity by encrypting only a fraction of the data bits. It can also easily provide users with low-quality versions, while maintaining the high-quality version inaccessible to unauthorized users. However, it is necessary to realistically evaluate its security strength. Some of the cryptanalysis done for these techniques ignored important characteristics of the multimedia files, and used overly optimistic assumptions. We demonstrate potential weaknesses of such techniques studying attacks that exploit the information provided by non-encrypted bits, and the availability of side information (e.g., from analog signals). We show that a more useful measure of encryption strength is the complexity to reduce distortion, instead of recovering the encryption key. We consider attacks on PE that avoid error propagation (standard-compliant PE), and PE that try to exploit that property for security. In both cases we show that attacks that require complexity much lower than exhaustive enumeration of encrypted/key bits can successfully yield good quality content. Experimental results are shown for images, but the conclusions can be extended to partial encryption of video and other types of media.