Cryptanalysis of randomized arithmetic codes based on markov model

An improvement of arithmetic coding based on Markov model (ACMM) has been proposed in the paper (Duan L.L., Liao X. F., Xiang T., Communications in Nonlinear Science and Numerical Simulation, 2011, 16(6):2554-2562). Though, a methodology to construct the ACMM is proposed in the above mentioned paper, it really lacks the formal definition of the ACMM. In the current paper, we not only investigate the security analysis of the ACMM, but also put forward formal definitions of the ACMM as well as its different security notions. Based on those definitions, a chosen-plaintext attack is proposed to reveal the used pseudorandom bit sequence for the encryption under the condition that the same pseudorandom bit sequence is used to encrypt the different messages. We also show that the ACMM does not have indistinguishable encryptions under the ciphertext-only attack (i.e., does not have indistinguishable encryptions in the presence of an eavesdropper) even if the different pseudorandom bit sequences are used to encrypt the different messages. Moreover, when the ACMM is combined with the randomized arithmetic code (RAC) (Grangetto M., Magli E., Olmo G., IEEE Trans. Multimedia, 2006 8(5):905-917), we also explore the insecurity of this combined encryption scheme. The analysis demonstrates that the ACMM+RAC is also insecure. Finally, the simulated experimental results show the correctness of all the proposed attacks.