Tsunami: Massively parallel homomorphic hashing on many-core GPUs

Homomorphic hash functions play a key role in securing distributed systems that use coding techniques such as erasure coding and network coding. The computational complexity of homomorphic hash functions remains a main challenge. In this paper, we present a massively parallel solution, named Tsunami, by exploiting the widely available many-core graphic processing units (GPUs). Tsunami includes the following optimization techniques to achieve the highest ever hashing throughput: (1) using Montgomery multiplication and precomputation to speed up modular exponentiations; (2) using a clean implementation of Montgomery multiplication in order to decrease the demand of registers and shared memory and increase the utilization ratio of GPU processing cores; (3) using our own assembly code to implement the 32-bit integer multiplication, which outperforms the assembly codes generated by the native compiler by 20%; and (4) exploiting memory alignment and constant memory on GPUs to improve the efficiency of memory access. Integrating the above techniques, our Tsunami achieves a significant improvement over existing results. Specifically, the hashing throughput achieved by Tsunami on a GTX295 GPU (NVIDIA, Santa Clara, CA, US) is about 33 times that of the existing solution on a quad-core CPU. We also show that the hashing throughput grows almost linearly with the number of GPU cores.