[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Secure Computation with Constant Communication Overhead Using Multiplication Embeddings

  • Conference paper
  • First Online:
Progress in Cryptology – INDOCRYPT 2018 (INDOCRYPT 2018)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11356))

Included in the following conference series:

  • 743 Accesses

Abstract

Secure multi-party computation (MPC) allows mutually distrusting parties to compute securely over their private data. The hardness of MPC, essentially, lies in performing secure multiplications over suitable algebras.

There are several cryptographic resources that help securely compute one multiplication over a large finite field, say \({\mathbb G} {\mathbb F} \left[ 2^n\right] \), with linear communication complexity. For example, the computational hardness assumption like noisy Reed-Solomon codewords are pseudorandom. However, it is not known if we can securely compute, say, a linear number of \(\mathsf {AND}\)-gates from such resources, i.e., a linear number of multiplications over the base field \({\mathbb G} {\mathbb F} \left[ 2\right] \). Before our work, we could only perform o(n) secure \(\mathsf {AND}\)-evaluations.

Technically, we construct a perfectly secure protocol that realizes a linear number of multiplication gates over the base field using one multiplication gate over a degree-n extension field. This construction relies on the toolkit provided by algebraic function fields.

Using this construction, we obtain the following results. We provide the first construction that computes a linear number of oblivious transfers with linear communication complexity from the computational hardness assumptions like noisy Reed-Solomon codewords are pseudorandom, or arithmetic-analogues of LPN-style assumptions. Next, we highlight the potential of our result for other applications to MPC by constructing the first correlation extractor that has 1 / 2 resilience and produces a linear number of oblivious transfers.

The research effort is supported in part by an NSF CRII Award CNS-1566499, an NSF SMALL Award CNS-1618822, and an REU CNS-1724673.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Network latency considerations typically motivate the study of MPC protocols with linear communication complexity.

  2. 2.

    Note that this is exact polynomial multiplication because the degree of A(t) and B(t) are both \(<m\). So, the degree of C(t) is \(<2m-1=n\). This observation, intuitively, implies that “\(\mod \pi (t)\)” does not affect C(t).

References

  1. Applebaum, B., Damgård, I., Ishai, Y., Nielsen, M., Zichron, L.: Secure arithmetic computation with constant computational overhead. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 223–254. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_8

    Chapter  Google Scholar 

  2. Atighehchi, K., Ballet, S., Bonnecaze, A., Rolland, R.: On chudnovsky-based arithmetic algorithms in finite fields. CoRR abs/1510.00090 (2015). http://arxiv.org/abs/1510.00090

  3. Ballet, S., Rolland, R.: Multiplication algorithm in a finite field and tensor rank of the multiplication. J. Algebra 272(1), 173–185 (2004). https://doi.org/10.1016/j.jalgebra.2003.09.031. http://www.sciencedirect.com/science/article/pii/S0021869303006951

    Article  MathSciNet  MATH  Google Scholar 

  4. Ballet, S., Baudru, N., Bonnecaze, A., Tukumuli, M.: On the construction of the asymmetric chudnovsky multiplication algorithm in finite fields without derivated evaluation. Comptes Rendus Mathematique 355(7), 729–733 (2017). https://doi.org/10.1016/j.crma.2017.06.002. http://www.sciencedirect.com/science/article/pii/S1631073X17301577

    Article  MathSciNet  MATH  Google Scholar 

  5. Ballet, S., Bonnecaze, A., Tukumuli, M.: On the construction of elliptic chudnovsky-type algorithms for multiplication in large extensions of finite fields, March 2013

    Google Scholar 

  6. Ballet, S., Pieltant, J., Rambaud, M.: On some bounds for symmetric tensor rank of multiplication in finite fields. CoRR abs/1601.00126 (2016). http://arxiv.org/abs/1601.00126

  7. Beaver, D.: Perfect privacy for two-party protocols. In: Feigenbaum, J., Merritt, M. (eds.), vol. 2, pp. 65–77. American Mathematical Society, Providence (1989)

    Google Scholar 

  8. Beimel, A., Malkin, T., Micali, S.: The all-or-nothing nature of two-party secure computation. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 80–97. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_6

    Chapter  Google Scholar 

  9. Block, A.R., Gupta, D., Maji, H.K., Nguyen, H.H.: Secure computation using leaky correlations (asymptotically optimal constructions). Cryptology ePrintArchive, Report 2018/372 (2018). https://eprint.iacr.org/2018/372

    Chapter  Google Scholar 

  10. Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation based on leaky correlations: high resilience setting. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_1

    Chapter  Google Scholar 

  11. Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation with constant communication overhead using multiplication embeddings. Cryptology ePrint Archive, Report 2018/395 (2018). https://eprint.iacr.org/2018/395

  12. Boyle, E., Gilboa, N., Ishai, Y.: Group-based secure computation: optimizing rounds, communication, and computation. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 163–193. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_6

    Chapter  Google Scholar 

  13. Bürgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, vol. 315. Springer, NewYork (1997). https://doi.org/10.1007/978-3-662-03338-8

    Book  MATH  Google Scholar 

  14. Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation, pp. 494–503 (2002). https://doi.org/10.1145/509907.509980

  15. Cascudo, I.: On asymptotically good strongly multiplicative linear secret sharing. Ph.D. thesis, Tesis doctoral, Universidad de Oviedo (2010)

    Google Scholar 

  16. Cascudo, I., Cramer, R., Xing, C., Yuan, C.: Amortized complexity of information-theoretically secure MPC revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 395–426. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_14

    Chapter  Google Scholar 

  17. Cenk, M., Özbudak, F.: On multiplication in finite fields. J. Complex. 26(2), 172–186 (2010)

    Article  MathSciNet  Google Scholar 

  18. Chandran, N., Goyal, V., Sahai, A.: New constructions for UC secure computation using tamper-proof hardware. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 545–562. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_31

    Chapter  Google Scholar 

  19. Chaumine, J.: Multiplication in small finite fields using elliptic curves, pp. 343–350 (2012). https://doi.org/10.1142/9789812793430_0018. https://www.worldscientific.com/doi/abs/10.1142/9789812793430_0018

  20. Chen, H., Cramer, R.: Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 521–536. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_31

    Chapter  Google Scholar 

  21. Chudnovsky, D.V., Chudnovsky, G.V.: Algebraic complexities and algebraic curves over finite fields. Proc. Nat. Acad. Sci. 84(7), 1739–1743 (1987)

    Article  MathSciNet  Google Scholar 

  22. Crépeau, C., Kilian, J.: Achieving oblivious transfer using weakened security assumptions (extended abstract), pp. 42–52 (1988). https://doi.org/10.1109/SFCS.1988.21920

  23. Damgård, I., Jurik, M.: A generalisation, a simpli.cation and some applications of paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_9

    Chapter  Google Scholar 

  24. Damgård, I., Nielsen, J.B., Wichs, D.: Isolated proofs of knowledge and isolated zero knowledge. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 509–526. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_29

    Chapter  Google Scholar 

  25. Damgård, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_38

    Chapter  Google Scholar 

  26. Dodis, Y., Halevi, S., Rothblum, R.D., Wichs, D.: Spooky encryption and its applications. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 93–122. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_4

    Chapter  Google Scholar 

  27. Garcia, A., Stichtenoth, H.: A tower of artin-schreier extensions of function fields attaining the drinfeld-vladut bound. Inventiones Mathematicae 121(1), 211–222 (1995)

    Article  MathSciNet  Google Scholar 

  28. Garcia, A., Stichtenoth, H.: On the asymptotic behaviour of some towers of function fields over finite fields. J. Number Theory 61(2), 248–273 (1996)

    Article  MathSciNet  Google Scholar 

  29. Gilboa, N.: Two party RSA key generation. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 116–129. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_8

    Chapter  Google Scholar 

  30. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority, pp. 218–229 (1987). https://doi.org/10.1145/28395.28420

  31. Goppa, V.D.: Codes on algebraic curves. Soviet Math. Dokl. 24, 170–172 (1981)

    MathSciNet  MATH  Google Scholar 

  32. Gupta, D., Ishai, Y., Maji, H.K., Sahai, A.: Secure computation from leaky correlated randomness. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 701–720. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_34

    Chapter  Google Scholar 

  33. Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract), pp. 230–235 (1989). https://doi.org/10.1109/SFCS.1989.63483

  34. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A., Wullschleger, J.: Constant-rate oblivious transfer from noisy channels. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 667–684. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_38

    Chapter  Google Scholar 

  35. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead, pp. 433–442 (2008). https://doi.org/10.1145/1374376.1374438

  36. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Extracting correlations, pp. 261–270 (2009). https://doi.org/10.1109/FOCS.2009.56

  37. Ishai, Y., Maji, H.K., Sahai, A., Wullschleger, J.: Single-use OT combiners with near-optimal resilience. In: 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29–July 4 2014, pp. 1544–1548. IEEE (2014). https://doi.org/10.1109/ISIT.2014.6875092

  38. Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer – efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_32

    Chapter  Google Scholar 

  39. Ishai, Y., Prabhakaran, M., Sahai, A.: Secure arithmetic computation with no honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 294–314. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_18

    Chapter  Google Scholar 

  40. Katz, J.: Universally composable multi-party computation using tamper-proof hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 115–128. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72540-4_7

    Chapter  Google Scholar 

  41. Kilian, J.: Founding cryptography on oblivious transfer, pp. 20–31 (1988). https://doi.org/10.1145/62212.62215

  42. Kilian, J.: A general completeness theorem for two-party games, pp. 553–560 (1991). https://doi.org/10.1145/103418.103475

  43. Kilian, J.: More general completeness theorems for secure two-party computation, pp. 316–324 (2000). https://doi.org/10.1145/335305.335342

  44. Kushilevitz, E.: Privacy and communication complexity, pp. 416–421 (1989). https://doi.org/10.1109/SFCS.1989.63512

  45. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_1

    Chapter  Google Scholar 

  46. Moran, T., Segev, G.: David and goliath commitments: UC computation for asymmetric parties using tamper-proof hardware. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 527–544. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_30

    Chapter  Google Scholar 

  47. Naor, M., Pinkas, B.: Oblivious polynomial evaluation. SIAM J. Comput. 35(5), 1254–1281 (2006)

    Article  MathSciNet  Google Scholar 

  48. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16

    Chapter  Google Scholar 

  49. Randriambololona, H.: Bilinear complexity of algebras and the chudnovsky-chudnovsky interpolation method. J. Complex. 28(4), 489–517 (2012)

    Article  MathSciNet  Google Scholar 

  50. Shparlinski, I., Tsfasman, M., Vladut, S.: Curves with many points and multiplication in finite-fields. Lect. Notes Math. 1518, 145–169 (1992)

    Article  MathSciNet  Google Scholar 

  51. Shum, K.W., Aleshnikov, I., Kumar, P.V., Stichtenoth, H., Deolalikar, V.: A low-complexity algorithm for the construction of algebraic-geometric codes better than the gilbert-varshamov bound. IEEE Trans. Inf. Theory 47(6), 2225–2241 (2001)

    Article  MathSciNet  Google Scholar 

  52. Wolf, S., Wullschleger, J.: Oblivious transfer is symmetric. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 222–232. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_14

    Chapter  Google Scholar 

  53. Yao, A.C.C.: Protocols for secure computations (extended abstract), pp. 160–164 (1982). https://doi.org/10.1109/SFCS.1982.38

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Purdue University, West Lafayette, IN, USA

    Alexander R. Block, Hemanta K. Maji & Hai H. Nguyen

Authors
  1. Alexander R. Block
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hemanta K. Maji
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hai H. Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander R. Block .

Editor information

Editors and Affiliations

  1. Indian Statistical Institute, Kolkata, India

    Debrup Chakraborty

  2. Nagoya University, Nagoya, Japan

    Tetsu Iwata

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Block, A.R., Maji, H.K., Nguyen, H.H. (2018). Secure Computation with Constant Communication Overhead Using Multiplication Embeddings. In: Chakraborty, D., Iwata, T. (eds) Progress in Cryptology – INDOCRYPT 2018. INDOCRYPT 2018. Lecture Notes in Computer Science(), vol 11356. Springer, Cham. https://doi.org/10.1007/978-3-030-05378-9_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-05378-9_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-05377-2

  • Online ISBN: 978-3-030-05378-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation