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.
From the original article
1 min read at arxiv.orgAdditively 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.
By Yavor Litchev · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.