Compressing encrypted data without the encryption key
A method, system and computer program product are disclosed for compressing encrypted data, wherein the data is encrypted by using a block encryption algorithm in a chained mode of operation, and the encrypted data is comprised of a set of N encrypted blocks, C 1 . . . C N . In one embodiment, the method comprises leaving block C N uncompressed, and compressing all of the blocks C 1 . . . C N in a defined sequence using a Slepian-Wolf code. In an embodiment, the data is encrypted using an encryption key K, and the compressing includes compressing all of the blocks C 1 . . . C N without using the encryption key. In one embodiment, the compressing includes outputting the blocks C 1 . . . C N as a set of compressed blocks CmprC 1 . . . CmprC N-1 , and the method further comprises decrypting C N to generate a reconstructed block {tilde over (X)} n , and decrypting and decompressing the set of compressed blocks using {tilde over (X)} n .
1. A method of decompressing and decrypting a message comprised of a set of blocks including n−1 randomized compressed encrypted blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 , and one randomized uncompressed encrypted block E {tilde over (X)} n , the method comprising:
receiving the N−1 randomized compressed encrypted blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)}E 1 and the randomized uncompressed encrypted block E {tilde over (X)} n ; and
decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 , including
using CE {tilde over (X)} n−1 as side information to decode E {tilde over (X)} n to obtain a plaintext block X n-1 and the randomized block E {tilde over (X)} n-1 ;
decrypting E {tilde over (X)} n to generate a randomized decrypted block {tilde over (X)} n , and
decompressing and decoding the randomized blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 to generate decompressed and decrypted plaintext blocks X n-1 , . . . , X 1 , including for each of the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 , using randomized, decrypted output from the decrypting of another block in the decompressing of said each block.
2. The method according to claim 1 , wherein the decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 includes decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 in a defined sequence.
3. The method according to claim 2 , wherein the using randomized, decrypted output from the decrypting of another block includes using output from the decrypting of a preceding block in the defined sequence.
4. The method according to claim 3 , wherein the using output from the decrypting of a preceding block in the defined sequence includes using the output from the decrypting of an immediately preceding block in the defined sequence.
5. The method according to claim 2 , wherein the defined sequence starts with the decrypting E {tilde over (X)} n .
6. The method according to claim 5 , wherein the defined sequence includes CE {tilde over (X)} n-1 , CE {tilde over (X)} n-2 , . . . CE {tilde over (X)} 1 .
7. The method according to claim 1 , wherein the encrypted blocks are encrypted using a key K, and the compressed encrypted blocks are compressed without using K.
8. The method according to claim 6 , wherein the decrypting the set of blocks includes decrypting the set of blocks using the key K.
9. The method according to claim 1 , wherein the decompressing and decoding the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 includes using Slepian-Wolf decoding to decompress the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 .
10. The method according to claim 1 , wherein:
the decompressing and decoding the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 to generate decompressed and decrypted plaintext blocks X n-1 , . . . , X 1 includes generating an associated randomized decrypted block from each of the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 ; and
the using randomized decrypted output from the decrypting of another block in the decompressing of said each block includes using one of the associated randomized decrypted blocks in the decompressing of said each block.
11. A joint decryption and decompression system for decompressing and decrypting a message a set of blocks including n−1 randomized compressed encrypted blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 , and one randomized uncompressed encrypted block E {tilde over (X)} n , the system comprising:
one or more processor units configured for:
receiving the N−1 randomized compressed encrypted blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 and the randomized uncompressed encrypted block E {tilde over (X)} n ; and
decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 , including
using CE {tilde over (X)} n−1 as side information to decode E {tilde over (X)} n to obtain a plaintext block X n-1 and the randomized block E {tilde over (X)} n-1 ;
decrypting E {tilde over (X)} n to generate a randomized decrypted block {tilde over (X)} n , and
decompressing and decoding the randomized blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 to generate decompressed and decrypted plaintext blocks X n-1 , . . . , X 1 , including for each of the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 , using randomized, decrypted output from the decrypting of another block in the decompressing of said each block.
12. The system according to claim 1 , wherein the decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 includes decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 in a defined sequence.
13. The system according to claim 12 , wherein the using randomized, decrypted output from the decrypting of another block includes using output from the decrypting of a preceding block in the defined sequence.
14. The system according to claim 13 , wherein the using output from the decrypting of a preceding block in the defined sequence includes using the output from the decrypting of an immediately preceding block in the defined sequence.
15. The system according to claim 12 , wherein the defined sequence starts with the decrypting E {tilde over (X)} n .
16. An article of manufacture comprising:
at least one tangible computer readable device having computer readable program code logic tangibly embodied therein to execute a machine instruction in a processing unit for decompressing and decrypting a message comprised of a set of blocks including n−1 randomized compressed encrypted blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 , and one randomized uncompressed encrypted block E {tilde over (X)} n , the computer readable program code logic, when executing, performing the following:
receiving the N−1 randomized compressed encrypted blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 and the randomized uncompressed encrypted block E {tilde over (X)} n ; and
decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 , including
using CE {tilde over (X)} n−1 as side information to decode E {tilde over (X)} n to obtain a plaintext block X n-1 and the randomized block E {tilde over (X)} n-1 ;
decrypting E {tilde over (X)} n to generate a randomized decrypted block {tilde over (X)} n , and
decompressing and decoding the randomized blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 to generate decompressed and decrypted plaintext blocks X n-1 , . . . , X 1 , including for each of the blocks CE {tilde over (X)} n-1 , . . . , CE {tilde over (X)} 1 , using randomized, decrypted output from the decrypting of another block in the decompressing of said each block.
17. The article of manufacture according to claim 16 , wherein the decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 includes decrypting the set of blocks CE {tilde over (X)} n-1 , . . . C {tilde over (X)} E 1 in a defined sequence.
18. The article of manufacture according to claim 17 , wherein the using randomized, decrypted output from the decrypting of another block includes using output from the decrypting of a preceding block in the defined sequence.
19. The article of manufacture according to claim 18 , wherein the using output from the decrypting of a preceding block in the defined sequence includes using the output from the decrypting of an immediately preceding block in the defined sequence.
20. The article of manufacture according to claim 17 , wherein the defined sequence starts with the decrypting E {tilde over (X)} n .