# 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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.ellipticpir.com/technology/why-reply-generation-is-o-n.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.