Abstract View

An Experimental Study of Encrypted Polynomial Arithmetics for Private Set Operations

"Recent studies on the performance of private set operations have examined the use of homomorphic public-key encryption and the technique of representing sets as polynomials in a cryptographic model. These polynomial-based solutions require intensive polynomial arithmetic that exhibit quadratic computational complexity. In an effort to develop practical algorithms for private set operations, various well-known techniques such as Karatsuba¡¯s algorithm or the fast Fourier transform (FFT) can be used to reduce the complexity of polynomial computations. The FFT appears to be the obvious best choice; however, the use of FFTs in the implementation of polynomial-based set operations may lead to certain subtle technical problems. These problems become particularly serious when the cardinality of the sets is dynamic. Furthermore, our experiment shows that Karatsuba¡¯s algorithm delivers higher performance than the FFT in our application, provided that a reasonable response time is important. In addition, our experimental implementation demonstrates the heuristic bound on cardinality for which Karatsuba¡¯s algorithm outperforms the FFT. This value can be used to determine the superior optimization techniques and settings in the deployment of private set operation schemes."