International Association
for Cryptologic Research

Homomorphic equality operator is essential for many secure computation tasks such as private information retrieval (PIR). However, the folklore homomorphic equality operator is typically considered to be impractical as its multiplicative depth depends on the input bit-length. In Usenix SEC '22, Mahdavi-Kerschbaum propose a homomorphic equality operator with a constant multiplicative depth, based on constant-weight code. On that basis, they propose constant-weight PIR (CwPIR for short); compared with other PIR protocols, CwPIR is more friendly to databases with large payloads and can support keyword query almost for free. Unfortunately, CwPIR cannot support databases with a large number of elements, which limits its real-world impact.

In this paper, we propose a homomorphic constant-weight equality operator that supports batch processing, hence it can perform thousands of equality checks with a much smaller amortized cost. Based on this improved homomorphic equality operator, we propose a novel PIR protocol named PIRANA, which inherits all advantages of CwPIR with a significant improvement in supporting more elements. We further extend PIRANA to support multi-query. To the best of our knowledge, PIRANA is the first multi-query PIR that can save both computation and communication. Our experimental results show that our single-query PIRANA is upto 30.8× faster than CwPIR; our multi-query PIRANA saves upto 163.9× communication over the state-of-the-art multi-query PIR (with a similar computational cost).