Tsunami: Massively parallel homomorphic hashing on many-core GPUs

Xiaowen CHU*, Kaiyong Zhao, Zongpeng Li

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)2028-2039
Number of pages12
JournalConcurrency Computation Practice and Experience
Issue number17
Publication statusPublished - 10 Dec 2012

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Computer Science Applications
  • Computer Networks and Communications
  • Computational Theory and Mathematics

User-Defined Keywords

  • CUDA
  • GPU
  • homomorphic hash function


Dive into the research topics of 'Tsunami: Massively parallel homomorphic hashing on many-core GPUs'. Together they form a unique fingerprint.

Cite this