Paper 2025/782

AES Is Not Enough: the Block Ciphers Zoo Goes Homormorphic (over TFHE)

Abstract

The dream of achieving data privacy during external computations has become increasingly concrete in recent years. Indeed, since the early days of Fully Homomorphic Encryption (FHE) more than a decade ago, new cryptosystems and techniques have constantly optimized the efficiency of computation on encrypted data. However, one of the main disadvantages of FHE, namely its significant ciphertext expansion factor, remains at the center of the efficiency bottleneck of FHE schemes. To tackle the issue of slow uplink FHE data transmission, we use transciphering. With transciphering, the client naturally encrypts its data under a symmetric scheme and sends them to the server with (once and for all) an FHE encryption of the symmetric scheme’s key. With its larger computing power, the server then evaluates the symmetric scheme’s decryption algorithm within the homomorphic domain to obtain homomorphic ciphertexts that allow it to perform the requested calculations. Since the first use of this method a bit more than ten years ago, papers on the homomorphic evaluation of AES have been numerous. And as the AES execution is the application chosen by NIST in the FHE part of its recent call for proposals on threshold encryption, the stakes of such work go up another level. But what about other standardized block ciphers? Is the AES the more efficient option? In this work, we leverage on two methods which have successfully been applied to the homomorphic evaluation of AES to study several state-of-the-art symmetric block ciphers (namely CLEFIA, PRESENT, PRINCE, SIMON, SKINNY). That is to say, we implement a representative set of symmetric block ciphers using TFHE. These implementations allow us to compare the efficiency of this set of symmetric schemes and to categorize them. We highlight the characteristics of block ciphers that are fast to execute in the homomorphic domain and those that are particularly costly. Finally, this classification of operation types enables us to sketch out what the ideal block cipher for transciphering homomorphic data in integer mode might look like.