Abstract
We study the design of efficient and private protocols for polynomial operations in the shared-coefficients setting. We propose efficient protocols for polynomial multiplication, division with remainder, polynomial interpolation, polynomial gcd, and a few other operations. All the protocols introduced in this paper are constant-round, and more efficient than the general MPC. The protocols are all composable, and can be combined to perform more complicated functionalities. We focus on using a threshold additively homomorphic public key scheme due to the applications of our protocols. But, our protocols can also be securely computed in the information-theoretic setting. Finally, we mention some applications of our protocols to privacy-preserving set-operations.
Chapter PDF
Similar content being viewed by others
Keywords
References
Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In: Proceedings of ACM PODC, pp. 201–209 (1989)
Ben-Or, M., Goldwasser, S., Widgerson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of ACM STOC, pp. 1–10 (1988)
Beaver, D., Micali, S., Rogaway, P.: The Round Complexity of Secure Protocols. In: Proceedings of 22nd ACM STOC, pp. 503–513 (1990)
Chaum, D., Crepeau, C., Damgard, I.: Multi-party unconditionally secure protocols. In: Proceedings of ACM STOC, pp. 11–19 (1988)
Cramer, R., Damgård, I.: Secure distributed linear algebra in a constant number of rounds. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 119–136. Springer, Heidelberg (2001)
Cramer, R., Damgård, I., Nielsen, J.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001)
Damgård, I., Fitzi, M., Buus Nielsen, J., Toft, T.: How to split a shared secret into shared bits in constant-round. Cryptology ePrint Archive, Report 2005/140 (2005), http://eprint.iacr.org/
Freedman, M., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005)
Feige, U., Kilian, J., Naor, M.: A Minimal Model for Secure Computation. In: Proceedings of ACM STOC 1994, pp. 554–563 (1994)
Freedman, M., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
Fouque, P., Pointcheval, D.: Threshold cryptosystems secure against chosen-ciphertext attacks. In: Proceedings of Asiacrypt, pp. 573–584 (2000)
Von Zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. University Press, Cambridge (2003)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM symposium on Theory of Computing, pp. 218–229 (1987)
Gennaro, R., Rabin, M., Rabin, T.: Simplified vss and fast-track multiparty computations with applications to threshold cryptography. In: Proceedings of ACM PODC, pp. 101–111 (1998)
Ishai, Y., Kushilevitz, E.: Private Simultaneous Messages Protocols with Applications. In: Proceedings of 5th Israel Symposium on Theoretical Comp. Sc., pp. 174–183 (1997)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A New Paradigm for Round-efficient Secure Computation. In: Proceedings of FOCS (2000)
Kissner, L., Song, D.: Privacy preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of Asiacrypt, pp. 573–584 (2000)
Shamir, A.: How to share a secret. In: CACM, pp. 612–613 (1979)
Yao, A.C.: Protocols for secure computation. In: Proceedings of Focs, pp. 160-164 (1982)
Yao, A.C.: How to generate and exchange secrets. In: Proceedings of 27th FOCS, pp. 162–167 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mohassel, P., Franklin, M. (2006). Efficient Polynomial Operations in the Shared-Coefficients Setting. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11745853_4
Download citation
DOI: https://doi.org/10.1007/11745853_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33851-2
Online ISBN: 978-3-540-33852-9
eBook Packages: Computer ScienceComputer Science (R0)