Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings

A carry-separated encoding and GPU-accelerated Paillier client achieving 43k encryptions/s and 29k Hamming-distance decodes/s on 512-bit embeddings

Yavor Litchev; Liwen Ouyang· 2026· DOI 10.48550/arXiv.2609.21364

The core problem

Additively homomorphic encryption enables outsourced computation on encrypted binary embeddings, but large-integer arithmetic and data movement often limit throughput. The authors address this by designing 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. The work establishes the encoding's correctness and characterizes four CPU and GPU client configurations. The lookup configuration uses a 280-bit exponent-size parameter. The study distinguishes warm-batch performance from isolated-request latency and identifies remaining costs of initialization, transport, and retrieval integration.

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 per encryption and 0.0345 ms per decode, corresponding to speedup factors of 453.8 and 200.9 relative to the measured CPU baseline. These results were obtained across 3 warm-state trials on batches of 10,000 random 512-bit embeddings. The study reports that the GPU configurations significantly outperform CPU-only implementations, with the lookup variant providing the highest throughput. The authors note that warm-batch performance differs from isolated-request latency, and they identify initialization, transport, and retrieval integration as remaining cost factors.

Additively homomorphic encryption enables outsourced computation on encrypted binary embeddings, but large-integer arithmetic and data movement often limit throughput. The authors address this by designing 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. The work establishes the encoding's correctness and characterizes four CPU and GPU client configurations. The lookup configuration uses a 280-bit exponent-size parameter. The study distinguishes warm-batch performance from isolated-request latency and identifies remaining costs of initialization, transport, and retrieval integration.

The client architecture integrates several optimizations. The carry-separated binary encoding ensures that each bit of a binary embedding is encoded as a separate ciphertext component, enabling correct Hamming-distance computation under Paillier encryption. Table-based encryption precomputes powers of the public key to accelerate encryption. Reduced-exponent decryption lowers the exponent size to 280 bits for the lookup configuration, balancing security and performance. CUDA/CGBN arithmetic leverages GPU parallelism for large-integer operations. Persistent device state avoids repeated initialization overhead across batches. Batched retrieval integration processes multiple vectors simultaneously.

The results demonstrate the throughput benefits of combining cryptographic precomputation, batched accelerator execution, and persistent runtime state. The carry-separated encoding ensures correctness while enabling efficient homomorphic operations. Table-based encryption and reduced-exponent decryption reduce computational overhead. CUDA/CGBN arithmetic and persistent device state minimize data movement and initialization costs. The batched retrieval integration allows the system to handle multiple vectors efficiently. The study distinguishes warm-batch performance from isolated-request latency, highlighting that the reported throughputs are achieved under sustained batch processing. The remaining costs of initialization, transport, and retrieval integration suggest avenues for further optimization. The authors establish the encoding's correctness and characterize four client configurations, providing a foundation for future work on encrypted binary embedding computations. The approach is particularly relevant for privacy-preserving machine learning and secure biometric matching, where binary embeddings are common. The use of Paillier encryption ensures semantic security, while the optimizations make the system practical for large-scale applications. The taxonomy candidates (Architecture, Cybersecurity, Network, Cryptography) reflect the interdisciplinary nature of the work.

CS practitioners and researchers

Opening member content…