Paper 2020/1340

Homomorphic Evaluation of the SM4

Yu Xue

Abstract

We report the homomorphic evaluation of the SM4 symmetric block-cipher based on BGV homomorphic encryption scheme. We implement bootstrapping and non-bootstrapping homomorphic evaluation of the 32-rounds SM4 based on HELib with about 128-bit security level. Our ways refer to and are similar as the AES homomorphic evaluation. The implementation uses packed ciphertexts and bytes in slots. The S-Box evaluation is similar as the AES evaluation method, and the Linear Transform layer uses the permutation of the bytes in states. Since the rounds are more than the AES and the SM4's feistel structer is different with the AES, the depths and levels of homomorphic evaluation of the SM4 are much more than AES, so need larger parameter(non-bootstrapping) and more bootstrapping. Our bootstrapping implementaion(3 ciphertexts, 360 blocks) runs about 1.5 hours on Macbook Pro(MacOS catalina 10.15, 16G), and the non-bootstrapping(1 ciphertext, 480 block) implementation runs about 6 hours on Macbook Pro(MacOS catalina 10.15, 16G).