Adaptive Chosen-Ciphertext Attack on Secure Arithmetic Coding

The paper "Secure Arithmetic Coding" (in IEEE TRANSACTIONS ON SIGNAL PROCESSING, vol. 55, no. 5, pp. 2263-2272, May 2007) presented a novel encryption scheme called the secure arithmetic coding (SAC) based on the interval splitting arithmetic coding (ISAC) and a series of permutations. In the current work, we study the security of the SAC under an adaptive chosen-ciphertext attack. It is shown that the key vectors used in the codeword permutation step can be recovered with complexity O(N), where N is the symbol sequence length. After getting these key vectors, we can remove the codeword permutation step, and the resulting system has already been shown to be insecure in the original paper. This implies that the SAC is not suitable for the applications where the attacker can have access to the decoder. In addition, we discuss a method to jointly enhance the security and the performance of the SAC