跳到主要內容

臺灣博碩士論文加值系統

(44.192.67.10) 您好!臺灣時間:2024/11/09 18:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:梁尹蓁
研究生(外文):Yin-Chen Liang
論文名稱:具加密功能之整數型算術編碼的設計與分析
論文名稱(外文):Design and Analysis on Secure Integer Arithmetic Coding
指導教授:黃育銘劉震昌
指導教授(外文):Yuh-Ming HuangJen-Chang Liu
口試委員:林家禎謝孫源洪政欣
口試委員(外文):Chia-Chen LinSun-Yuan HsiehJen-Shin Hong
口試日期:2014-07-30
學位類別:博士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:90
中文關鍵詞:算術編碼隨機算術編碼安全性算術編碼安全雜湊演算法偽亂數產生器可調式安全性整數型算術編碼
外文關鍵詞:Arithmetic CodingRandomized Arithmetic CodingSecure Arithmetic CodingSHA-256Pseudorandom Bit GeneratorAdjustable Integer Arithmetic Coding
相關次數:
  • 被引用被引用:0
  • 點閱點閱:309
  • 評分評分:
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
隨著數位時代的來臨與資訊技術的進步,網際網路 (Internet) 已成為我們日常生活上的必須工具,利用高科技智慧型的相關產品,透過網路廣泛地傳播、散佈與獲取任何的資訊,享受著數位科技上所帶來的便利,但相對地,也浮現出一些潛在性的問題,如:機密資料文件的竊取、偽造或竄改;在秘密視訊會議上的監聽、偷窺…等相關的問題。因此,數位多媒體的資料也伴隨著資訊安全上的重要性,保護數位資料安全的機制是必然探討的研究。此外,由於網路頻寬有限的問題,對於在即時傳輸的訴求下,如何設計有效的資料加密及壓縮機制,儼然成為一重要研究課題。

近年來,許多研究學者致力於將資料加密與資料壓縮做整合;在設計具安全性的算術編碼相關研究上,除了考量較小壓縮失真 (Compression Loss),並對其所提出的方法於安全性上做詳細的分析,如:隨機算術編碼 (Randomized Arithmetic Coding, RAC)及具安全性算術編碼 (Secure Arithmetic Coding, SAC) 。上述研究著重在實數型算術編碼,基於計算複雜度的考量,工業界實作大多採用整數型算術編碼,因此本論文主要探討整數型算術編碼。本論文共分三部份,首先我們提出二種具安全性的算術編碼方法,也就是資料在進行算術編碼的過程中,將資訊安全的機制同步整合於系統中;接者深入探討有關整數型算術編碼的最佳壓縮效能,用來佐證所提之二種具安全性的算術編碼方法,其在壓縮效能上損失相當些微。

第一部份,我們提出具安全性整數型算術編碼 (Modified Integer Arithmetic Coding, MIAC),在編碼之前,先利用安全雜湊演算法 (Secure Hash Algorithm, SHA-256) 產生秘密金鑰,它將用於決定是否對於最大出現頻率的符號所對應的編碼區間長度增加,或對於最小出現頻率的符號所對應的編碼區間長度減少的運作;完成編碼後的碼文,為了提高安全性,我們再將碼文與偽亂數產生器 (Pseudorandom Bit Generator, PRBG)-BBS作XOR運算產生密文;實驗結果顯示,MIAC不僅同時擁有壓縮及加密的功能,且在壓縮效能上往往會比傳統整數型算術編碼 (Traditional Integer Arithmetic Coding, TIAC) 來得佳;對於本論文所用到的測試檔案,當壓縮效能變差時,所增加的壓縮大小都在1個位元以內。

第二部份,我們發現,針對每個符號所對應的編碼區間其長度大小作調整得以減小瞬時熵 (Instantaneous Entropy)。因此,我們進一步提出了第二種方法稱為安全整數算術編碼 (Secure Integer Arithmetic Coding, SIAC),相較於MIAC,其具有較高的安全性,且幾乎所有壓縮效能都比TIAC來得好。缺點是演算法的計算複雜度變高了。

第三部份,我們提出了一個可調節式整數型算術編碼 (Adjustable Integer Arithmetic Coding, AIAC),在所有可能整數型算術編碼實作中,其擁有最好的壓縮效能。 根據理論分析,AIAC採用最佳區間分割技巧得以將因整數型算術編碼實作所衍生的冗餘 (Redundancy) 降到最低,所以可以達到最好壓縮效能。

With the advance of technologies in digital communication and digital storage, a variety of multimedia information can be spread easily to all corners of the world over the internet. But relatively, many potential problems emerge, such as: stealing, forging, or tampering for confidential documents, monitoring in video conference, and so on. Thus, once we deal with the digital multimedia data, the issue of information security will consequently emerge. In addition, due to the constraint of limited network bandwidth for transmitting real-time multimedia data, how to design an effective mechanism for data encryption and compression, has become an important research topic.

Current research in multimedia security has recently focused on improving the cryptanalysis of randomized arithmetic coding (RAC) and secure arithmetic coding (SAC). The above approaches are applied to floating-point arithmetic coding. Integer implementation is more popular than the floating-point arithmetic implementation since it can decrease the computational cost of arithmetic coding without inducing significant compression loss. Taking a different approach, we present two novel multimedia security approaches based on a modification of integer arithmetic coding.

In the first proposed approach, we apply the Secure Hash Algorithm (SHA-256) to construct the key vector. Using the key vector, every time a symbol is encoded, the source intervals associated with different symbols are adjusted accordingly. We then use the Pseudorandom Bit Generator (PRBG) - BBS to generate a key stream to enhance security through the bitwise XOR operation. In terms of coding efficiency, theoretical analysis and experimental results indicate that our proposed code not only provides security, but also often offers better compression efficiency when compared with traditional integer arithmetic coding (TIAC).

Next, we find that it is possible to decrease the instantaneous entropy through the alternate adjustment of source intervals. Hence, we further propose the second approach called integer arithmetic coding (SIAC) with higher security, and the compression efficiency of this code is almost the same or even higher relative to TIAC.

Finally, we propose an adjustable integer arithmetic coding (AIAC) scheme with the best compression performance on integer arithmetic coding. AIAC applies an optimal interval partition scheme to enhance the compression efficiency. Instead of traditional interval partition method, this algorithm can reduce the redundancy induced by integer arithmetic coding to the lowest. AIAC can also be used to verify that both algorithms, MIAC and SIAC, have quite slight loss on the compression performance even in the case of compression loss.
Acknowledgement I

Chinese Abstract III

English Abstract V

Contents VII

List of Figures X

List of Tables XII

Chapter 1 Introduction 1
1.1 Direct Encryption ...............2
1.2 Partial Encryption ...............3
1.3 Encryption-embedded Compression ...............7
1.4 Goals and Contributions ...............8
1.5 Organization of Thesis ...............9

Chapter 2 Related Research 10
2.1 Arithmetic Coding ...............10
2.1.1 Real arithmetic coding ...............10
2.1.2 Integer arithmetic coding ...............12
2.2 Attacks on Encryption Schemes ...............17
2.3 Randomized Arithmetic Coding ...............18
2.4 Binary Arithmetic Coding With Key-based Interval Splitting ...............22
2.5 Secure Arithmetic Coding ...............26
2.5.1 Input Permutation (IP) ...............26
2.5.2 Output Permutation (OP) ...............27
2.5 Summary ...............30

Chapter 3 Modified Integer Arithmetic Coding 31
3.1 Introduction ...............31
3.2 The Algorithm of Modified Integer Arithmetic Coding ...............33
3.2.1 Key Scheduler ...............33
3.2.2 Encoding Processing ...............35
3.2.3 Decoding Processing ...............43
3.3 Analysis of MIAC Coding Efficiency ...............46
3.3.1 Traditional Integer Arithmetic Coding (TIAC) ...............46
3.3.2 Modified Integer Arithmetic Coding (MIAC) ...............47
3.4 Instantaneous Coding Gain ...............48
3.5 Analysis of MIAC Security ...............54
3.5.1 Security analysis of key scheduler 1 ...............55
3.5.2 Security analysis of key scheduler 2 ...............56
3.5.3 MIAC under two kinds of well-known attacks ...............56
3.6 Comparisons of Computational Complexity ...............61
3.7 Summary ...............61

Chapter 4 Secure Integer Arithmetic Coding with Adjustable Interval Size 62
4.1 Introduction ...............62
4.2 Motivation ...............63
4.3 The Interval Partition Algorithm ...............64
4.4 The Encoding Algorithm ...............66
4.5 The Decoding Algorithm ...............68
4.6 Analysis of Coding Efficiency ...............69
4.6.1 Analysis of instantaneous entropy ...............71
4.7 Analysis of Security ...............73
4.7.1 Ciphertext-Only Attack ...............73
4.7.2 Chosen-Plaintext Attack ...............73
4.8 Comparisons of Computational Complexity ...............74
4.9 Summary ...............74

Chapter 5 Adaptive Integer Arithmetic Coding Algorithm 75
5.1 Introduction ...............75
5.2 Adjustable Integer Arithmetic Coding ...............75
5.3 Analysis of Coding Efficiency ...............78
5.4 Comparisons of Coding Gain ...............81
5.5 Comparisons of Computational Complexity ...............84
5.5 Summary ...............84

Chapter 6 Conclusions 85

References 86

List of Figures
Figure 1.1 Direct encryption and decryption...............2
Figure 1.2 The structures of precompression partial encryption................4
Figure 1.3 The structures of incompression partial encryption...............5
Figure 1.4 The structures of partial encryption and decryption...............6
Figure 1.5 The diagram of joint compression and encryption...............7
Figure 2.1 The illustration of arithmetic coding...............12
Figure 2.2 The illustration of randomized arithmetic coding............... 20
Figure 2.3 Four possible values of the interval I(BB)...............21
Figure 2.4 The illustration of interval splitting; (a) before splitting; (b) splitting I(A) with k1=1/3; (c) before splitting for k2=1/2; (d) after splitting...............24
Figure 2.5 The diagram of secure arithmetic coding...............26
Figure 2.6 Input sequence permutation...............27
Figure 2.7 Output sequence permutation...............29
Figure 3.1 The diagram of our proposed MIAC algorithm...............32
Figure 3.2 The correct key is changed 16 bits in the front side: 74268 Bytes difference, 5475 Bytes match, Matching: 3.5%...............38
Figure 3.3 The correct key is changed 16 bits in the middle side: 70929 Bytes difference, 81160 Bytes match, Matching: 53.3%...............39
Figure 3.4 The correct key is changed 16 bits in the posterior: 9 Bytes difference, 152080 Bytes match, Matching: 99.9%...............40
Figure 3.5 Adjustment of intervals: (a) the size of the interval associated with a1 is increased by one, the size of the interval associated with aM is decreased by one; (b) the size of each of the intervals respectively allocated to a1 and a2 is increased by one, the size of the interval associated with aM-1 is decreased by two...............42
Figure 3.6 Classical separate compression-encryption schemes: AC concatenated with a stream cipher...............55
Figure 3.7 Four cases of splitting for encoding the 1st symbol of the input sequence...............58
Figure 3.8 Four cases of splitting for encoding the 2nd symbol of the input sequence..............59
Figure 3.9 Interval AC: (a) Traditional interval AC (b) Modified interval AC with KV[1]= 1 and KV[2]=1..............60
Figure 4.1 The source intervals which are adjusted according to the decimal value DKn of the sub-key bit vector kn...............67
Figure 5.1 The plot of log2(x)..............83

List of Tables
Table 2.1 Values of the parameters for integer arithmetic coding example..............14
Table 2.2 The interval I(BB)..............21
Table 2.3 Eight different adjustment policies used in MIAC.............. 25
Table 3.1 Eight different adjustment policies used in MIAC.............. 41
Table 3.2 Coding efficiency with one symbol adjusted..............51
Table 3.3 Coding efficiency of Key = “100”..............52
Table 3.4 Coding efficiency of Key = “111”..............53
Table 4.1 Compression Efficiency..............70
Table 5.1 Compression efficiency for TIAC and AIAC..............80
[1] D. Kundur and K. Karthik, “Video fingerprinting and encryption principles for digital rights management,” in Proc. IEEE, vol. 92, pp. 918-932, 2004.
[2] Data Encryption Standard (DES), Federal Information Processing Standards Publication 46, Jan. 1977.
[3] Advanced Encryption Standard (AES), Federal Information Processing Standards Publication 197, Nov. 26, 2001.
[4] M. Grangetto, A. Grosso, and E. Magli, “Selective encryption of JPEG2000 images by means of randomized arithmetic coding,” in Proc. IEEE 6th Workshop on Multimedia Signal Process., Siena, Italy, Sep. 2004, pp. 347-350.
[5] M. Grangetto, E. Magli, and G. Olmo, “Multimedia selective encryption by means of randomized arithmetic coding,” IEEE Trans. Multimedia, vol. 8, no. 5, pp. 905-917, Oct. 2006.
[6] J. Meyer and F. Gadegast, “Security mechanisms for multimedia data with the example MPEG-1 video,” in Project Description of SECMPEG. Berlin, Germany: Technical Univ. Berlin, 1995.
[7] G. A. Spanos and T. B. Maples, “Performance study of a selective encryption scheme for the security of networked, real-time video,” in Proc. 4th Int. Conf. Computer Communications and Networks, Las Vegas, NV, Sep. 20-23, 1995.
[8] L. Tang, “Methods for encrypting and decrypting MPEG video data efficiently,” in Proc. 4th ACM Int. Multimedia Conf., Boston, MA, Nov. 18-22, 1996, pp. 219-230.
[9] L. Qiao and K. Nahrstedt, “A new algorithm for MPEG video encryption,” in Proc. 1st Int. Conf. Imaging Science, Systems and Technology (CISST ’97), Las Vegas, NV, Jul. 1997, pp. 21-29.
[10] C. Shi and B. Bhargava, “A fast MPEG video encryption algorithm,” in Proc. 6th Int. Multimedia Conf., Bristol, U.K., Sep. 12-16, 1998.
[11] A. M. Alattar, G. I. Al-Regib, and S. A. Al-Semari, “Improved selective encryption techniques for secure transmission of MPEG video bit-streams,” in Proc. 1999 Int. Conf. Image Processing (ICIP ’99), Kobe, Japan, Oct. 24-28, 1999, Vol. 4, pp. 256-260.
[12] C. Shi, S. -Y. Wang, and B. Bhargava, “MPEG video encryption in realtime using secret key cryptography,” in 1999 Int. Conf. Parallel and Distributed Processing Techniques and Applications (PDPTA’99), Las Vegas, NV, Jun. 28-Jul. 1, 1999.
[13] H. Cheng and X. Li, “Partial encryption of compressed images and video,” IEEE Trans. Signal Process., vol. 48, pp. 2439-2451, 2000.
[14] M. Van Droogenbroeck and R. Benedett, “Techniques for a selective encryption of uncompressed and compressed images,” in Proc. Advanced Concepts for Intelligent Vision Systems (ACIVS) 2002, Ghent, Belgium, Sep. 9-11, 2002.
[15] A. Servetti and J. C. De Martin, “Perception-based partial encryption of compressed speech,” IEEE Trans. Speech Audio Process., vol. 10, no. 8, pp. 637-643, 2002.
[16] M. Podesser, H. -P. Schmidt, and A. Uhl, “Selective bitplane encryption for secure transmission of image data in mobile environments,” in Proc. 5th Nordic Signal Processing Symp., Oct. 4-7, 2002.
[17] A. Pommer and A. Uhl, “Selective encryption of wavelet-packet encoded image data,” Multimedia Syst. J., vol. 9, no. 3, pp. 279-287, 2003.
[18] W. Zeng and S. Lei, “Efficient frequency domain selective scrambling of digital video,” IEEE Trans. Multimedia, vol. 5, pp. 118-129, 2003.
[19] T. Lookabaough and D. C. Sicker, “Selective encryption for consumer applications,” IEEE Commun. Mag., pp. 124-129, 2004.
[20] S. Lian, Multimedia Content Encryption: Techniques and Applications, Auerbach Publication, Taylor & Francis Group, 2008.
[21] A. Massoudi, F. Lefebvre, C. De Vleeschouwer, B. Macq, and J. -J. Quisquater, “Overview on Selective Encryption of Image and Video: Challenges and Perspectives,” EURASIP J. Inform. Security, vol. 2008, Article ID 179290, pp. 1-18, 2008.
[22] R. G. Gallager, “Variations on a Theme by Huffman, ” IEEE Trans. on Information Theory, vol. IT-24, no. 6, pp. 668-674, Nov. 1978.
[23] C. -P. Wu and C. -C. J. Kuo, “Fast encryption methods for audiovisual data confidentiality,” in Proc. SPIE Int. Symp. Information Technologies 2000, Boston, MA, Nov. 2000, pp. 284-295.
[24] C. -P. Wu and C. -C. J. Kuo, “Efficient multimedia encryption via entropy codec design,” in Proc. SPIE Security and Watermarking of Multimedia Content III, Jan. 2001, Vol. 4314.
[25] C. -P. Wu and C. -C. J. Kuo, “Design of integrated multimedia compression and encryption systems,” IEEE Trans. Multimedia, vol. 7, pp. 828-839, 2005.
[26] J. Zhou, Z. Liang, Y. Chen, and O. C. Au, “Security analysis of multimedia encryption schemes based on multiple Huffman table,” IEEE Signal Process. Lett., vol. 14, no. 3, pp. 201-204, Mar. 2007.
[27] G. Jakimoski and K. P. Subbalakshmi, “Cryptanalysis of some multimedia encryption schemes,” IEEE Trans. Multimedia, vol. 10, no. 3, pp. 330-338, Apr. 2008.
[28] J. Rissanen, “Generalised Kraft inequality and arithmetic coding,” IBM J. Res. Develop. vol. 20, pp. 198-203, 1976.
[29] J. Rissanen, and G. G. Langdon, “Arithmetic coding,” IBM J. Res. Develop. vol. 23, no. 2, pp. 149-162, Mar. 1979.
[30] X. Ruan and R. S. Katti, “A new source coding scheme with small expected length and its application to simple data encryption,” IEEE Trans. Computers, vol. 55, no. 10, pp. 1300-1305, Oct. 2006.
[31] H. Kim, J. Villasenor, and J. Wen, “Secure arithmetic coding using interval splitting,” in Proc. Thirty-Ninth Asilomar Conf. Signals, Systems and Computers, 2005, Oct. 28-Nov. 1, 2005, pp. 1218-1221.
[32] J. Wen, H. Kim, and J. D. Villasenor, “Binary arithmetic coding with key-based interval splitting,” IEEE Signal Process. Lett., vol. 13, no. 2, pp. 69-72, Feb. 2006.
[33] H. Kim, J.Wen, and J. D. Villasenor, “Secure arithmetic coding,” IEEE Trans. Signal Process., vol. 55, no. 5, pp. 2263-2272, May 2007.
[34] I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression,” Commun. Assoc. Comp. Mach., vol. 30, no. 6, pp. 520-540, 1987.
[35] P. G. Howard and J. S. Vitter, “Arithmetic coding for data compression,” in Proc. of the IEEE, vol. 82, no. 6, pp. 857-865, Jun., 1994.
[36] D. S. Taubman and M. W. Marcellin, JPEG2000: Image Compression Fundamentals, Standards and Practice. Norwell, MA: Kluwer Academic, 2002.
[37] T. Wiegand, G. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560-576, Jul. 2003.
[38] K. Sayood, Introduction to Data Compression, 3rd ed. San Diego, CA: Morgan Kaufmann, 2005.
[39] R. S. Katti, S. K. Srinivasan, and A. Vosoughi, “On the security of randomized arithmetic codes against ciphertext-only attacks,” IEEE Trans. Inform. Forensics security, vol. 6, no. 1, pp. 19-27, Mar. 2011.
[40] H. M. Sun, K. H. Wang, and W. C. Ting, “On the security of the secure arithmetic code,” IEEE Trans. Inform. Forensics Security, vol. 4, no. 4, pp. 781-789, Dec. 2009.
[41] J. Zhou, O. Au, X. Fan, and P. Wong, “Joint security and performance enhancement for secure arithmetic coding,” in Proc. 15th IEEE Int. Conf. on Image Processing, Oct. 2008, pp. 3120-3123.
[42] J. Zhou, O. C. Au, P. H. Wong, and X. Fan, “Cryptanalysis of secure arithmetic coding,” in Proc. of the IEEE Int. Conf. on Acoustics, Speech and Signal Process., 2008, pp. 1769-1772.
[43] J. Zhou, O. C. Au, and P. H. Wong, “Adaptive chosen-ciphertext attack on secure arithmetic coding,” IEEE Trans. Signal Process., vol. 57, no. 5, pp. 1825-1838, May 2009.
[44] R. S. Katti, S. K. Srinivasan, and A. Vosoughi, “On the Security of Key-Based Interval Splitting Arithmetic Coding With Respect to Message Indistinguishability,” IEEE Trans. Inform. Forensics security, vol. 7 no. 3, pp. 895-903, June 2012.
[45] Secure Hath Standard (SHS), Federal Information Processing Standards Publication 180-3, Oct. 2008.
[46] A. Menezes, P. V. Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.
[47] C. E. Shannon, “Communication theory of secrecy systems,” Bell System Technical J., vol. 28, pp. 656-715, 1949.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top