Why Reply Generation is O(n)

All PIR protocol requires O(n) computation without no exception where n is the number of database elements.

If the server-side computation is below O(n), which means some database elements are not accessed in reply generation. Which leads the fact that those elements are not included in the reply and leaks knowledge. Thus it is mandatory to require O(n) computation complexity for all PIR protocols.

The computation in EllipticPIR is almost consumed by tensor product between encrypted query and data, and has Θ(n) of computational complexity which is optimal at least in a computational complexity context.

LWE (learning with errors) encryptions has relatively small computational footprint for homomorphic addition because addition in LWE encryption is just an addition of two polynomials. LWE ciphertext is high dimensional polynomial containing multiple plaintexts (vector). If we use LWE encrytion as our backend, it is required to rotate plaintext vector in a LWE ciphertext which consumes relatively high computational resources. Thus we concluded that simpler homomorphic encryption schemes like EC-ElGamal best fit for efficient parallelization.

We continue to research to find more efficient algorithm all time and there is a chance that we find a better way.