This paper here specified that symmetric ciphers like AES is not a good choice for Hybrid Homomorphic Encryption due to large multiplicative depth. How is the multiplicative depth of AES computed here, is it while homomorphic evaluation (decrypting AES homomorphically and change it to FHE ciphertext) is conducted? And why is it not compatible for this reason?
I tried looking into other papers but every other paper says the same line without any details into it.
Yes, this is what is implied. If the input ciphertexts are given to you encrypted under AES, and you then want to perform computations on those inputs, you first need to convert from AES to FHE. This means you have to run the AES decryption circuit homomorphically. The AES decryption circuit is non-polynomial, and if you want to write it as a leveled polynomial computation, it will have a large depth.
Thank you so much. That was very helpful!
When you say converting into leveled polynomial operations, do you mean writing the operation m= (C)^d mod N in the form of multiplication? And due to the number of multiplication involved, the depth is therefore very large?
The operation you mentioned seems to be RSA, not AES. For AES https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197-upd1.pdf operations such as the Sbox, which is a look-up table, would need to be transformed to polynomial evaluation if you use larger plaintext FHE schemes.