Introduction

EllipticPIR is a Private Information Retrieval (PIR) implementation that scales and runs on GPUs.

What is Private Information Retrievals (PIRs)?

A private information retrieval is a cryptographic building block which enables clients to retrieve data from a server without revealing any information about the query.

Suppose that you want to go to the nearest McDonald's. You will search it for finding the location on the Map, which will query to the map server with the text like "McDonald's New York". In that case the server will learn that you're going to go to one of the McDonald's located in New York city, which leaks your privacy.

With PIRs, you can search any keywords without disclosing any information about your query and in the above case the server learn nothing about your query.

The difficulties with traditional PIRs

In principle, PIR implementations should traverse all the database elements and compute them to create an encrypted reply. Thus the server-side procedure requires huge amount of computational resources.

The traditional PIR implementations (like SealPIR) does not support parallel computation of query and cannot be scaled with multi-core CPUs or many-core GPUs. In our implementation, the server side computation is highly parallelizable and can be run on any GPUs.

What is EllipticPIR?

EllipticPIR is a new instantiation and an implementation of PIRs which is highly parallelizable and can run on GPUs.

The traditional PIR implementation (SealPIR) can reply to the query with ~1M database elements in 2 secs, whereas our implementation can reply with ~100M database elements in 2.6 secs using single consumer GPU, which is x77 faster! Please note that if we utilize multiple GPUs or use pro GPUs (like NVIDIA Tesla) our practical computation time easily can be faster than the above experiment.

In addition, SealPIR uses Learning With Errors (LWE) homomorphic encryption which is NOT widely battle-tested, but EllipticPIR only uses Elliptic Curve (EC)-ElGamal encryption (ElGamal encryption was invented in 1984) which is already technically matured well.

Thus our invention is highly practical and secure compared to the traditional ones.