Thus, when the database size is 2 25, 2 30 and 2 35 bits, Kushilevitz's protocol would need 277.46, 8878.19.04 seconds respectively. The time for a single operation is 8.269 × 10 −6 second. This is done by averaging the time for 1 million operations. We measured time for a 3072-bit modular multiplication using the GMP library. For 128-bit security, the modulus size needs to be at least 3072-bit. We then compare our protocol with Kushilevitz's protocol. So the modular multiplication operation is slower in those protocols than in Kushilevitz's protocol. Cachin's, Lipmaa's (and the BDD-based), and Chang's, require larger moduli. Another factor that makes Kushilevitz's protocol the most efficient one is the modulus size. Although the number of operations in Gentry's protocol is similar to Kushilevitz's protocol, in practice it would be less efficient due to the large exponent which is twice as big as the database. The most efficient protocol of all above ones is Kushilevitz's protocol that requires n modular multiplications. Because the exponent size l e is larger than 2 log n, the total cost is larger than n modular multiplications.-Chang's protocol requires n modular multiplications and 2 log n modular exponentiations. The computational cost is approximately l e n/(2 log n) modular multiplications. Lipmaa's BDD based protocol requires O(n/(log n)) modular exponentiations. n modular multiplications for some c depending on log n.The computational cost is approximately l e n/2 modular multiplications, where l e is the bit length of the exponent.-Lipmaa's protocol requires for each 2 ≤ j ≤ log n, 2 log n −j exponentiations. The computational cost is approximately n modular multiplications.-Cachin's protocol requires n modular exponentiations. We report on the performance of our protocol based on the prototype and compare it with the current most efficient protocols.Ĭommunication Cost Comparison-Gentry's protocol requires only one modular exponentiation but the exponent is 2n-bit. We have built a prototype of the protocol.
Our protocol can be further accelerated by utilising hardware parallelism. This significantly reduces the server side computational overhead and makes our protocol much faster than the existing protocols. We show how we design the protocol to exploit the internal parallelism of the BGV scheme. The other major building block is the BGV fully homomorphic encryption scheme. This compression scheme enables us to lower the communication complexity to O(loglogn). A major building block of the PIR protocol in this paper is a tree-based compression scheme, which we call folding/unfolding. In this paper, we present a single server PIR protocol that has low communication cost and is much faster than existing protocols. To be practical, a single server PIR protocol has to be both communicationally and computationally efficient. Existing single server Private Information Retrieval (PIR) protocols are far from practical.
0 kommentar(er)
