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

Linear Overhead Optimally-Resilient Robust MPC Using Preprocessing

  • Conference paper
  • First Online:
Security and Cryptography for Networks (SCN 2016)

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

Included in the following conference series:

  • 1095 Accesses

Abstract

We present a new technique for robust secret reconstruction with \(\mathcal {O}(n)\) communication complexity. By applying this technique, we achieve \(\mathcal {O}(n)\) communication complexity per multiplication for a wide class of robust practical Multi-Party Computation (MPC) protocols. In particular our technique applies to robust threshold computationally secure protocols in the case of \(t<n/2\) in the pre-processing model. Previously in the pre-processing model, \(\mathcal {O}(n)\) communication complexity per multiplication was only known in the case of computationally secure non-robust protocols in the dishonest majority setting (i.e. with \(t<n\)) and in the case of perfectly-secure robust protocols with \(t<n/3\). A similar protocol was sketched by Damgård and Nielsen, but no details were given to enable an estimate of the communication complexity. Surprisingly our robust reconstruction protocol applies for both the synchronous and asynchronous settings.

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.

    An MPC protocol is called robust if the honest parties obtain the correct output at the end of the protocol irrespective of the behaviour of the corrupted parties, otherwise it is called non-robust.

  2. 2.

    We stress that we are interested only in the online complexity. Unlike our online phase, our offline phase protocol cannot be executed in a completely asynchronous setting with \(t<n/2\).

References

  1. Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  2. Backes, M., Bendun, F., Choudhury, A., Kate, A.: Asynchronous MPC with a strict honest majority using non-equivocation. In: Halldórsson, M.M., Dolev, S. (eds.) PODC, pp. 10–19. ACM (2014)

    Google Scholar 

  3. Baron, J., J., Defrawy, J., Lampkins, J., Ostrovsky, R.: How to withstand mobile virus attacks, revisited. In: Halldórsson, M.M., Dolev, S. (eds.) PODC, pp. 293–302. ACM (2014)

    Google Scholar 

  4. Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992)

    Google Scholar 

  5. Beerliová-Trubíniová, Z., Hirt, M.: Efficient multi-party computation with dispute control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305–328. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  6. Beerliová-Trubíniová, Z., Hirt, M.: Perfectly-secure MPC with linear communication complexity. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 213–230. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  7. Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: Kosaraju, S.R., Johnson, D.S., Aggarwal, A. (eds) STOC, pp. 52–61. ACM (1993)

    Google Scholar 

  8. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Simon, J. (ed.) STOC, pp. 1–10. ACM (1988)

    Google Scholar 

  9. Ben-Sasson, E., Fehr, S., Ostrovsky, R.: Near-linear unconditionally-secure multiparty computation with a dishonest minority. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 663–680. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  10. Bendlin, R., Damgård, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  11. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. TOCT 6(3), 13:1–13:36 (2014)

    Article  MathSciNet  Google Scholar 

  12. Canetti, R.: Studies in secure multiparty computation and applications. Ph.D. thesis, Weizmann Institute, Israel (1995)

    Google Scholar 

  13. Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  14. Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC, pp. 11–19. ACM (1988)

    Google Scholar 

  15. Choudhury, A., Hirt, M., Patra, A.: Asynchronous multiparty computation with linear communication complexity. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 388–402. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  16. Choudhury, A., Loftus, J., Orsini, E., Patra, A., Smart, N.P.: Between a rock and a hard place: interpolating between MPC and FHE. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 221–240. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  17. Choudhury, A., Patra, A.: Optimally resilient asynchronous MPC with linear communication complexity. In: Das, S.K., Krishnaswamy, D., Karkar, S., Korman, A., Kumar, M., Portmann, M., Sastry, S. (eds.) ICDCN, pp. 5:1–5:10. ACM (2015)

    Google Scholar 

  18. Clement, A., Junqueira, F., Kate, A., Rodrigues, R.: On the (limited) power of non-equivocation. In: Kowalski, D., Panconesi, A. (eds.) PODC, pp. 301–308. ACM (2012)

    Google Scholar 

  19. Damgård, I., Geisler, M., Krøigaard, M., Nielsen, J.B.: Asynchronous multiparty computation: theory and implementation. In: Jarecki, S., Tsudik, G. (eds.) PKC, pp. 160–179 (2009)

    Google Scholar 

  20. Damgård, I., Ishai, Y., Krøigaard, M.: Perfectly secure multiparty computation and the computational overhead of cryptography. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 445–465. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  21. Damgård, I.B., Nielsen, J.B.: Scalable and unconditionally secure multiparty computation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 572–590. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  22. 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)

    Chapter  Google Scholar 

  23. Damgård, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol. 8134, pp. 1–18. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  24. Fitzi, M., Hirt, M.: Optimally efficient multi-valued Byzantine agreement. In: Ruppert, E., Malkhi, D. (eds.) PODC, pp. 163–168. ACM Press (2006)

    Google Scholar 

  25. Genkin, D., Ishai, Y., Polychroniadou, A.: Efficient multi-party computation: from passive to active security via secure SIMD circuits. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 721–741. Springer, Heidelberg (2015)

    Chapter  Google Scholar 

  26. Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fact-track multiparty computations with applications to threshold cryptography. In: Coan, B.A., Afek, Y. (eds.) PODC, pp. 101–111. ACM (1998)

    Google Scholar 

  27. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218–229. ACM (1987)

    Google Scholar 

  28. Hirt, M., Nielsen, J.B.: Robust multiparty computation with linear communication complexity. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 463–482. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  29. Hirt, M., Nielsen, J.B., Przydatek, B.: Cryptographic asynchronous multi-party computation with optimal resilience (extended abstract). In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 322–340. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  30. Hirt, M., Nielsen, J.B., Przydatek, B.: Asynchronous multi-party computation with quadratic communication. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 473–485. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  31. Katz, J., Koo, C.-Y.: On expected constant-round protocols for Byzantine agreement. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 445–462. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  32. Keller, M., Scholl, P., Smart, N.P.: An architecture for practical actively secure MPC with dishonest majority. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 549–560. ACM (2013)

    Google Scholar 

  33. Yao, A.C.: Protocols for secure computations (extended abstract). In: FOCS, pp. 160–164. IEEE Computer Society (1982)

    Google Scholar 

Download references

Acknowledgements

This work has been supported in part by ERC Advanced Grant ERC-2010-AdG-267188-CRIPTO, by EPSRC via grants EP/I03126X and EP/M016803, by DARPA and the US Navy under contract #N66001-15-C-4070, and by the Infosys Foundation.

Author information

Authors and Affiliations

  1. International Institute of Information Technology, Bangalore, India

    Ashish Choudhury

  2. Department of Computer Science, University of Bristol, Bristol, UK

    Emmanuela Orsini & Nigel P. Smart

  3. Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

    Arpita Patra

Authors
  1. Ashish Choudhury
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Emmanuela Orsini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arpita Patra
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nigel P. Smart
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nigel P. Smart .

Editor information

Editors and Affiliations

  1. Rensselaer Polytechnic Institute, Troy, New York, USA

    Vassilis Zikas

  2. University of Salerno, Fisciano, Italy

    Roberto De Prisco

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Choudhury, A., Orsini, E., Patra, A., Smart, N.P. (2016). Linear Overhead Optimally-Resilient Robust MPC Using Preprocessing. In: Zikas, V., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2016. Lecture Notes in Computer Science(), vol 9841. Springer, Cham. https://doi.org/10.1007/978-3-319-44618-9_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-44618-9_8

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-44617-2

  • Online ISBN: 978-3-319-44618-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation