A Study of Arithmetic Codes for Joint Encryption and Compression

利用算術編碼同步加密及壓縮之研究

王景行(King-Hang Wang)

指導教授 ： 孫宏民

國立清華大學/電機資訊學院/資訊工程學系/博士(2010年)

https://doi.org/10.6843/NTHU.2010.00683

摘要

針對多媒體的版權保護問題，愈來愈多學者傾向對資料進行同步壓縮及加密。理由是這樣的設計不但可以增加運算上及儲存上的效率，這樣亦增加了對媒體保護的彈性。算術碼是近年相當受歡迎的壓縮技術法。一些壓縮標準如JPEG 2000及H.264亦採用算術碼為其核心技術。近年來不少學者提出基於算術碼的加密法。其中Kim等在2007年提出了SAC演算法，一直被視為一個有效且安全的重要技術。

在這篇論文中，我們會深入討論SAC的安全性問題。我們發現SAC並沒有達到於原文中所述的安全水平。事實上，SAC會受到選擇性明文攻擊及選擇性密文攻擊。攻擊者可以在有限時間內求得其加密金鑰。

有鑑於此，在論文的下半部會闡述一個新穎的基於算術碼之同步壓縮及加密法，ACE。通過破解SAC的經驗，我們發現演算法對密文的發散性是抵禦差分攻擊的關鍵，於是，我們在ACE的設計裡，針對了密文的發散性作出加強。此外，我們亦為ACE研制了選擇性加密的設計。這樣的設計增加了演算法的彈性；使他適用於如數位廣播的媒體保護上。論文亦包括了一些模擬實驗來驗証ACE的安全性及效率。

關鍵字

密碼 ； 算術碼

並列摘要

The requirements for encrypting multimedia contents are very different from general purpose symmetric encryptions.
Those requirements including low computation power, small data size, and enabling partial encryptions, make neither common block ciphers like DES/AES nor other stream ciphers applicable to protect multimedia contents.
Recently, many works have been proposed to compress and encrypt multimedia contents simultaneously.
Being a compression code adopted in several industrial standards, the arithmetic code is studied in some of these works.
In particular, Kim extit{et al.} proposed a secure compression code called Secure Arithmetic Code (SAC) in 2007.
It had been believed to be an efficient and secure algorithm.
However, we find that SAC is not as secure as the authors have claimed.

In the first part of the thesis, we show that SAC is prone to two attacks.
The first attack completely breaks the code using an adaptive chosen plaintext attack with a polynomial number of queries. The second attack is a ciphertext-only attack, which removes a part of the output permutation.

In the second part of the thesis, we present a novel and efficient scheme called Arithmetic Code Encryption (ACE) to jointly compress and encrypt multimedia contents base on the arithmetic code.
Through the experience in breaking SAC, we realize that the diffusion property offered by the code is the key of defense against differential attacks.
We design ACE by exploring the characteristics of the arithmetic code to provide high security levels that previous schemes fail to deliver.
Experiments have been conducted to help us verify ACE's security properties and select appropriate system parameters.
We also discuss how parital encryptions can be implemented with ACE that provides leverages between security and flexibility.

參考文獻

[1] Data Encryption Standard. Federal Information Processing Standards Publication

46, January 1977.

Telecommunications Standards Institute ETSI, 1997.

[3] Advanced Encryption Standard (AES). Federal Information Processing Standards

[5] I. Agi and L. Gong. An empirical study of secure MPEG video transmissions.