Lightweight compression with encryption based on asymmetric numeral systems

Duda, Jarosław ; Niemiec, Marcin

International Journal of Applied Mathematics and Computer Science, Tome 33 (2023) no. 1, pp. 45-55.

Résumé

Data compression combined with effective encryption is a common requirement of data storage and transmission. Low cost of these operations is often a high priority in order to increase transmission speed and reduce power usage. This requirement is crucial for battery-powered devices with limited resources, such as autonomous remote sensors or implants. Well-known and popular encryption techniques are frequently too expensive. This problem is on the increase as machine-to-machine communication and the Internet of Things are becoming a reality. Therefore, there is growing demand for finding trade-offs between security, cost and performance in lightweight cryptography. This article discusses asymmetric numeral systems-an innovative approach to entropy coding which can be used for compression with encryption. It provides a compression ratio comparable with arithmetic coding at a similar speed as Huffman coding; hence, this coding is starting to replace them in new compressors. Additionally, by perturbing its coding tables, the asymmetric numeral system makes it possible to simultaneously encrypt the encoded message at nearly no additional cost. The article introduces this approach and analyzes its security level. The basic application is reducing the number of rounds of some cipher used on ANS-compressed data, or completely removing an additional encryption layer when reaching a satisfactory protection level.

Détail

Keywords: symmetric cryptography, lightweight cryptography, data compression, entropy coding
Mots-clés : kryptografia symetryczna, kryptografia lekka, kompresja danych, kodowanie entropijne

Bibliographie

[1] [1] Alakuijala, J., Van Asseldonk, R., Boukortt, S., Bruse, M., Coms, a, I.-M., Firsching, M., Fischbacher, T., Kliuchnikov, E., Gomez, S., Obryk, R. et al. (2019). JPEG XL next-generation image compression architecture and coding tools, Applications of Digital Image Processing XLII, San Diego, USA, pp. 112-124.

[2] [2] ALC (2017). Apple LZFSE compressor, https://github. com/lzfse/lzfse.

[3] [3] Baptista, M. (1998). Cryptography with chaos, Physics Letters A 240(1): 50-54.

[4] [4] Bassham, L., Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Leigh, S., Levenson, M., Vangel, M., Heckert, N. and Banks, D. (2010). A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST SP 800-22 Rev 1a, National Institute of Standards and Technology, Gaithersburg, https://www .nist.gov/publications/statistical-tes t-suite-random-and-pseudorandom-number-generators-cryptographic.

[5] [5] Buzidi, H. (2014). LzTurbo compressor, https://sites.g oogle.com/site/powturbo/.

[6] [6] Camtepe, S., Duda, J., Mahboubi, A., Morawiecki, P., Nepal, S., Pawłowski, M. and Pieprzyk, J. (2021). CompCrypt-lightweight ANS-based compression and encryption, IEEE Transactions on Information Forensics and Security 16: 3859-3873.

[7] [7] Cole, P.H. and Ranasinghe, D.C. (2008). Networked RFID Systems and Lightweight Cryptography, Springer, London.

[8] [8] Collet, Y. (2013a). New generation entropy codecs: Finite state entropy and Huff 0, https://github.com/Cyan49 73/FiniteStateEntropy.

[9] [9] Collet, Y. (2013b). Zhuff compressor, http://fastcompre ssion.blogspot.com/p/zhuff.html.

[10] [10] Duda, J. (2009). Asymmetric numerical systems, arXiv: 0902.0271.

[11] [11] Duda, J. (2014a). ANS toolkit, https://github.com/Jar ekDuda/AsymmetricNumeralSystemsToolkit.

[12] [12] Duda, J. (2014b). Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv: 1311.2540.

[13] [13] Duda, J., Tahboub, K., Gadgil, N.J. and Delp, E.J. (2015). The use of asymmetric numeral systems as an accurate replacement for Huffman coding, 31st Picture Coding Symposium, Cairns, Australia, pp. 65-69.

[14] [14] Eisenbarth, T., Kumar, S., Paar, C., Poschmann, A. and Uhsadel, L. (2007). A survey of lightweight-cryptography implementations, IEEE Design Test of Computers 24(6): 522-533.

[15] [15] El-Douh, A.A.-R., Lu, S.F., Elkouny, A.A. and Amein, A.S. (2022). Hybrid cryptography with a one-time stamp to secure contact tracing for COVID-19 infection, International Journal of Applied Mathematics and Computer Science 32(1): 139-146, DOI: 10.34768/amcs-2022-0011.

[16] [16] FZC (2016). Facebook Zstandard compressor, https://git hub.com/facebook/zstd.

[17] [17] Francesco, N. (2014). LZA compressor, http://heartofc omp.altervista.org/.

[18] [18] Giesen, F. (2014). Simple rAns encoder/decoder, https://g ithub.com/rygorous/ryg_rans.

[19] [19] Gillman, D.W., Mohtashemi, M. and Rivest, R.L. (1996). On breaking a Huffman code, IEEE Transactions on Information Theory 42(3): 972-976.

[20] [20] Huang, Z., Liu, S., Qin, B. and Chen, K. (2015). Sender-equivocable encryption schemes secure against chosen-ciphertext attacks revisited, International Journal of Applied Mathematics and Computer Science 25(2): 415-430, DOI: 10.1515/amcs-2015-0032.

[21] [21] Huffman, D. (1952). A method for the construction of minimum redundancy codes, Proceedings of the IRE 40(9): 1098-1101.

[22] [22] Jakimoski, G. and Kocarev, L. (2001). Chaos and cryptography: Block encryption ciphers based on chaotic maps, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 48(2): 163-169.

[23] [23] Kelley, J. and Tamassia, R. (2014). Secure compression: Theory practice, Cryptology ePrint Archive, Report 2014/113, https://eprint.iacr.org/2014/113.

[24] [24] Kim, H., Wen, J. and Villasenor, J.D. (2007). Secure arithmetic coding, IEEE Transactions on Signal Processing 55(5): 2263-2272.

[25] [25] Külekci, M.O. (2012). On scrambling the Burrows-Wheeler transform to provide privacy in lossless compression, Computers Security 31(1): 26-32.

[26] [26] Mahboubi, A., Ansari, K., Camtepe, S., Duda, J., Morawiecki, P., Pawłowski, M. and Pieprzyk, J. (2022). Digital immunity module: Preventing unwanted encryption using source coding, TechRxiv, (preprint).

[27] [27] Marpe, D., Schwarz, H. and Wiegand, T. (2003). Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard, IEEE Transactions on Circuits and Systems for Video Technology 13(7): 620-636.

[28] [28] Martin, G. (1979). Range encoding: An algorithm for removing redundancy from a digitized message, Institution of Electronic and Radio Engineers International Conference on Video and Data Recording, Southampton, UK.

[29] [29] Najmabadi, S.M., Wang, Z., Baroud, Y. and Simon, S. (2015). High throughput hardware architectures for asymmetric numeral systems entropy coding, 9th IEEE International Symposium on Image and Signal Processing and Analysis (ISPA), Zagreb, Croatia, pp. 256-259.

[30] [30] Pieprzyk, J., Pawlowski, M., Morawiecki, P., Mahboubi, A., Duda, J. and Camtepe, S. (2022). Pseudorandom bit generation with asymmetric numeral systems, Cryptology ePrint Archive, Report 2022/005, https://ia.cr/20 22/005.

[31] [31] Poschmann, A.Y. (2009). Lightweight cryptography: Cryptographic engineering for a pervasive world, Cryptology ePrint Archive, Paper 2009/516, https://e print.iacr.org/2009/516.

[32] [32] Rissanen, J.J. (1976). Generalized Kraft inequality and arithmetic coding, IBM Journal of Research and Development 20(3): 198-203.

[33] [33] Tseng, K.-K., Jiang, J.M., Pan, J.-S., Tang, L.L., Hsu, C.-Y. and Chen, C.-C. (2012). Enhanced Huffman coding with encryption for wireless data broadcasting system, IEEE International Symposium on Computer, Consumer and Control (IS3C), Taichung, Taiwan, pp. 622-625.

[34] [34] Witten, I.H. and Cleary, J.G. (1988). On the privacy afforded by adaptive text compression, Computers Security 7(4): 397-408.

[35] [35] Xie, D. and Kuo, C.-C. (2005). Secure Lempel-Ziv compression with embedded encryption, Electronic Imaging 2005, San Jose, USA pp. 318–327, DOI: 10.1117/12.590665.