Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings
A batched GPU Paillier client computes Hamming distance on encrypted 512-bit embeddings at high throughput.
The paper describes a Paillier client for outsourced Hamming-distance computation over encrypted binary embeddings, combining carry-separated encoding, table-based encryption, reduced-exponent decryption, and CUDA/CGBN batching. Across three warm trials of 10,000 random 512-bit embeddings, the lookup GPU configuration reached median throughputs of 43,091 encryptions per second and 28,983 decodes per second. Amortized costs were 0.0232 ms and 0.0345 ms per vector, about 453.8x and 200.9x the measured CPU baseline, using a 280-bit exponent-size parameter.
- Lookup GPU client uses a 280-bit exponent-size parameter.
- Median throughput: 43,091 encryptions/s and 28,983 decodes/s.
- Amortized GPU cost is about 201–454 times the CPU baseline.
- Measurements cover warm batches, not isolated-request latency.
Full article152 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.21364