Secure compression
In embodiments, secure compression algorithms are provided that may be employed as a single operation on raw data to produce compressed and encrypted data. In embodiments, the algorithms described herein may be performed using any type of dictionary based encryption. In one embodiment, upon adding a new prefix to a dictionary table, the dictionary table may be permuted to randomize the entries into the table. The randomization may be based upon a permutation value generated by a deterministic pseudo-random generator and/or pseudo-random function. Other embodiments of randomization may be employed to provide secure compression. For example, instead of permuting the entire table upon adding a prefix, the prefix may be randomly added to the table.
1. A method for performing secure compression, the method comprising:
initializing a dictionary table comprising one or more character strings, wherein each of the one or more character strings is associated with a respective index;
setting a prefix, wherein the prefix is a first character from a file;
reading a second character from the file;
concatenating the second character to the prefix to generate a first concatenated prefix;
determining if the first concatenated prefix is in the dictionary table; and
in response to determining that the first concatenated prefix is not in the dictionary table;
outputting an index of the prefix representing the first character string from the file from the dictionary table,
reinserting the prefix representing the first character string from the file at a random index of the dictionary table; and
randomly inserting the first concatenated prefix into the dictionary table.
2. The method of claim 1 , wherein at least one of the one or more strings comprises a single string character.
3. The method of claim 1 , wherein initializing the dictionary table comprises inserting an end of file (EOF) character into the dictionary table.
4. The method of claim 1 , wherein randomly inserting the first concatenated prefix into the dictionary table does not comprise randomly permuting the dictionary table.
5. The method of claim 1 further comprising:
determining if there is more data in the file; and
when there is more data in the file, performing operations comprising:
setting the prefix to the first concatenated prefix;
reading a third character from the file;
concatenating the third character to the prefix to create a second concatenated prefix;
determining if the second concatenated prefix is in the dictionary table; and
when the second concatenated prefix is not in the dictionary table, randomly inserting the second concatenated prefix into the dictionary table.
6. A computer storage medium comprising computer executable instructions that, when executed by at least one processor, perform a method comprising:
initializing a dictionary table with one or more character strings, each of the one or more character strings associated with a respective index setting a prefix to a first character from a file;
reading a second character from the file;
concatenating the second character to the prefix to create a concatenated prefix;
determining if the concatenated prefix is in the dictionary table;
in response to determining that the first concatenated prefix is not in the dictionary table:
outputting an index of the prefix representing the first character string from the file from the dictionary table,
reinserting the prefix representing the first character string from the file at a random index of the dictionary table; and
randomly inserting the first concatenated prefix into the dictionary table.
7. The computer storage medium of claim 6 , wherein the random index is generated based upon a key.
8. The computer storage medium of claim 7 , wherein the random permutation value is generated using at least one of: a deterministic pseudo-random generator; and a deterministic pseudo-random function.
9. The computer storage medium of claim 6 , wherein at least one of the one or more strings comprises a single string character.
10. The computer storage medium of claim 6 , wherein initializing the dictionary table further comprises inserting an end of file (EOF) character into the dictionary table.