Abstract 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.

The Recent progress in practical applications of secure computation protocols has also attracted attention to the symmetric-key primitives underlying them. Whereas traditional ciphers have evolved to be efficient with respect to certain performance metrics, advanced cryptographic protocols call for a different focus. The so called arithmetic complexity is viewed through the number and layout of non-linear operations in the circuit implemented by the protocol. Symmetric-key algorithms that are optimized with respect to this metric are said to be algebraic ciphers. Previous work targeting ZK and MPC protocols delivered great improvement in the performance of these applications both in lab and in practical use. Interestingly, despite its apparent benefits to privacy-aware cloud computing, algebraic ciphers targeting FHE did not attract similar attention.