Block Ciphers, Homomorphically, And Then Some

Following up on our recent post, Block Ciphers, Homomorphically, we have some new results. In our previous post, we reported on two experiments: a single block-at-a-time evaluation of SIMON 64/128 computed with the HElib homomorphic encryption library, and a parallel, 1800 block-at-a-time evaluation of the same cipher. Our results on the latter have not changed: 1800 blocks in 1 hour and 52 minutes, for 3.1 seconds per block. However, we have improved results for our single block-at-a-time solution, which we report on here.

After discussing the previous single block implementation with Shai Halevi, developer of HElib, we modified our approach to take advantage of an optimization for multiplication by constants of which we were unaware. By doing so, we were able to significantly reduce the multplication overhead of each SIMON round. As a result, with L=45, we were able to reduce the single-block processing time from 14 hours to 3 hours 8 minutes. Exploiting parallelism by ciphertext packing, and choosing nSlots to be a multiple of 32 instead of our current value of 1800, would allow higher throughput by processing blocks in parallel. However, our experiment was designed to understand single block throughput, so we report only that result here.

In summary, our experiments show that SIMON 64/128 implemented under homomorphic encryption using the open-source HElib library achieves performance ranging from 3 hours 8 minutes while processing a single block with no parallelism, to 3.1 seconds per block while processing 1800 blocks at a time using a bit-slice approach.

Questions or comments? Feel free to contact Dave Archer.