Query Composition

The database elements in EllipticPIR is arranged as a hypercube with dimension d. For instance, if d = 3 and the number of database elements n = 1,000,000, the dataset is arrange as 3-d cube with 100 x 100 x 100 elements for each edge.

The query will select the position on that hypercube. For d = 3 case, you should select the x, y and z coordinates of the hypercube in your query.

Once you determine the (x, y, z) tuble, next you should create an encrypted query.

You will generate a private key sk that can be ephemeral per query (you can reuse the private key for multiple queries, but there are no such requirement). You don't have to submit your public key to the server. There is no such API.

Then, create an array of EC-ElGamal encrypted message array for each coordinates. For x-coordinate, you will create an array of EC-ElGamal encrypted messages with the length equal to the element count on the x-edge of the hypercube. The encrypted array is

[Enc(0), .., Enc(0), Enc(1), Enc(0), .., Enc(0)]

where only the x-th message is one and zeros for non x-th.

This will continue to y, z, .. to reach to the dimension. Thus the final query is

[ [Enc(0), .., Enc(0), Enc(1), Enc(0), .., Enc(0)], .., [Enc(0), .., Enc(0), Enc(1), Enc(0), .., Enc(0)] ].

The total number of encrypted messages will be O(n^(1/d)). This will be both the computational complexity of the query generation process and the outbound network traffic to the server.