How Not To Design An Efficient FHE-Friendly Block Cipher: Seljuk

With the rapid increase in the practical applications of secure computation protocols, increasingly more research is focused on the efficiency of the symmetric-key primitives underlying them. Whereas traditional block ciphers have evolved to be efficient with respect to certain performance metrics, secure computation protocols call for a different efficiency metric: arithmetic complexity. Arithmetic complexity is viewed through the number and layout of nonlinear operations in the circuit implemented by the protocol. Symmetric-key algorithms that are optimized for this metric are said to be algebraic ciphers. It has been shown that recently proposed algebraic ciphers are greatly efficient in ZK and MPC protocols. However, there has not been many algebraic ciphers proposed targeting Fully Homomorphic Encryption (FHE). In this paper, we evaluate the behavior of Vision when implemented as a circuit in an FHE protocol. To this end, we present a state-of-the-art comparison of AES and Vision implemented using HElib. Counterintuitively, Vision does not deliver a better performance than AES in this setting. Then, by attempting to improve a bottleneck of the FHE implementation evaluating Vision we present a new cipher: Seljuk. Despite the improvement with respect to Vision, Seljuk does not deliver the expected performance.