Masta: An HE-Friendly Cipher Using Modular Arithmetic
Jincheol Ha, Seongkwang Kim, Wonseok Choi, Jooyoung Lee, Dukjae Moon, Hyo‐Jin Yoon, Jihoon Cho
Abstract
The Rasta cipher, proposed by Dobraunig et al. (CRYPTO 2018), is an HE-friendly cipher enjoying the fewest ANDs per bit and the lowest ANDdepth among the existing ciphers. A novel feature of Rasta is that its affine layers are freshly and randomly generated for every encryption. In this paper, we propose a new variant of Rasta, dubbed Masta. Similarly to Rasta, Masta takes as input a (master) secret key and a nonce, and generates a keystream block for each counter. On the other hand, Masta has two main differences from Rasta: Masta uses modular arithmetic to support HE schemes over a non-binary plaintext space, and it uses a smaller number of random bits in the affine layers by defining them with finite field multiplication. In this way, Masta outperforms Rasta in a transciphering framework with BGV/FVstyle HE schemes. Our implementation shows that Masta is 505 to 592 times faster in terms of the throughput on the client-side, while 4792 to 6986 times faster on the server-side.