Paillier encryption speeds up processing of large batches of binary data
Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings
Cryptography and Security
Summary
Working with encrypted data can be slow because of complicated math and data movement. The authors show how to use special math tricks and GPUs to speed up calculations on encrypted binary data. Their method processes tens of thousands of encrypted data points quickly, much faster than a typical CPU. This shows how to combine clever encoding, hardware, and precomputation to make secure data processing more efficient, especially when working with many items at once.
What this means in practice
- •For cloud service providers: Run large-scale encrypted similarity searches on binary data efficiently by batching and GPU acceleration to reduce computational overhead and latency.
- •For embedded systems engineers: Improve throughput for secure binary data comparison in resource-constrained environments by using carry-separated encoding combined with GPU processing.
Authors
Yavor Litchev, Liwen Ouyang
Abstract
Additively homomorphic encryption supports outsourced computation on encrypted binary embeddings, but large-integer arithmetic and data movement can limit throughput. We describe a Paillier-based client that combines a carry-separated binary encoding, table-based encryption, reduced-exponent decryption, CUDA/CGBN arithmetic, persistent device state, and batched retrieval integration. We establish the encoding's correctness and characterize four CPU and GPU client configurations. The lookup configuration uses a 280-bit exponent-size parameter. Across 3 warm-state trials on batches of 10,000 random 512-bit embeddings, the lookup GPU configuration achieved median-batch throughputs of 43,091 encryptions/s and 28,983 Hamming- distance decodes/s. Its amortized costs were 0.0232 ms and 0.0345 ms per vector, corresponding to factors of 453.8 and 200.9 relative to the measured CPU baseline. These implementation- specific results demonstrate the throughput benefits of combining cryptographic precomputation, batched accelerator execution, and persistent runtime state. The study distinguishes warm-batch performance from isolated-request latency and identifies the remaining costs of initialization, transport, and retrieval integration.