In this study, the authors proposed a new scheme which performs both lossless compression and encryption of images. Lossless compression is done by arithmetic coding (AC) while encryption is based on a chaos-based pseudorandom bit generator. Hence, they proposed to incorporate recent results of chaos theory into AC in order to shuffle the cumulative frequency vector of input symbols chaotically to make AC secure and the decoding process completely key-dependent. Many other techniques based on varying the statistical model used by AC have been proposed in literature, however, these techniques suffer from losses in compression efficiency that result from changes in entropy model statistics and are weak against known attacks. The proposed compression–encryption techniques were developed and discussed. The numerical simulation analysis indicates that the proposed scheme is highly satisfactory for image encryption without any AC compression efficiency loss. In addition, it can be incorporated into any image compression standard or algorithm employing AC as entropy coding stage, including static, adaptive and context-based adaptive models, and at any level, including bit, pixel and predictive error pixel levels.