Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?

This post is based on HEAT output http://eprint.iacr.org/2015/889

There are a number of different Ring-LWE based homomorphic encryption schemes. The two most famous being the BGV scheme (due to Brakerski, Gentry and Vaikuntanathan) and a modification of the famous NTRU encryption scheme. Each of these schemes comes in two flavours, in the first (traditional) flavour the messages are held in the lower order bits, whilst in the so-called scale-invariant flavours the messages are held in the upper order bits. The advantage of the scale-invariant systems are that they avoid the need for strong noise control procedures such as modulus switching.

A lot of work has been conducted into optimizing these schemes, but many papers only consider a certain set of parameters (for example some consider characteristic two plaintext spaces only), or some consider only one form of key-switching operation (there are two main variants of key switching in the literature). Generally speaking the usual consensus is that the scale-invariant version of the NTRU scheme (called YASHE) is to be preferred. This consensus is because YASHE offers the benefits of scale-invariance. In addition ciphertexts consist of only one ring element; as opposed to the two needed for the BGV schemes.

This consensus is however based on limited exploration of the design space. In HEAT output "Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?" by Bristol researchers Ana Costache and Nigel P. Smart the authors explore the design space in more detail. They examine all four schemes using a consistent mathematical model of noise growth for the first time; previous work uses a different model for each scheme in each paper. They conclude that whilst YASHE may be preferable for small characteristic plaintext spaces, for large plaintext spaces the BGV scheme (in the non-scale invariant form) comes out being significantly more efficient. This conclusion holds irrespective of the number of levels (i.e. multiplicative depth) which one requires the homomorphic encryption scheme to support.

Such an analysis has important implications for practical applications of homomorphic encryption. Different application domains will place different constraints on the plaintext spaces. For example if one is evaluating binary circuits in an application then a characteristic two plaintext space is to be preferred. However, if one is evaluating a complex arithmetic expression (such as in a statistical analysis) than one may model the plaintext as integers and hence utilize a large characteristic to avoid integer overflow.