Skip to main content
SpringerLink
Log in

Masked Triples

Amortizing Multiplication Triples Across Conditionals

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2021 (PKC 2021)

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

Included in the following conference series:

Abstract

A classic approach to MPC uses preprocessed multiplication triples to evaluate arbitrary Boolean circuits. If the target circuit features conditional branching, e.g. as the result of a IF program statement, then triples are wasted: one triple is consumed per \(\mathtt {AND}\) gate, even if the output of the gate is entirely discarded by the circuit’s conditional behavior.

In this work, we show that multiplication triples can be re-used across conditional branches. For a circuit with b branches, each having n \(\mathtt {AND}\) gates, we need only a total of n triples, rather than the typically required \(b\cdot n\). Because preprocessing triples is often the most expensive step in protocols that use them, this significantly improves performance.

Prior work similarly amortized oblivious transfers across branches in the classic GMW protocol (Heath et al., Asiacrypt 2020, [HKP20]). In addition to demonstrating conditional improvements are possible for a different class of protocols, we also concretely improve over [HKP20]: their maximum improvement is bounded by the topology of the circuit. Our protocol yields improvement independent of topology: we need triples proportional to the size of the program’s longest execution path, regardless of the structure of the program branches.

We implemented our approach in C++. Our experiments show that we significantly improve over a “naïve” protocol and over prior work: for a circuit with 16 branches and in terms of total communication, we improved over naïve by \(12\times \) and over [HKP20] by an average of \(2.6\times \).

Our protocol is secure against the semi-honest corruption of \(p-1\) parties.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.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

Notes

  1. 1.

    We emphasize communication improvement because multiplication triples are often constructed from communication-expensive oblivious transfers (OTs). Silent OT [BCG+19] is an exciting new primitive that largely removes the communication overhead of OT. The trade off is increased computation: the classic OT extension of [IKNP03], which uses relatively little computation, is still preferable to Silent OT in most settings. This said, even if we were to use Silent OT, our improvement would be beneficial: we greatly reduce the needed number of OTs and hence would significantly reduce Silent OT computation overhead.

  2. 2.

    \(\mathtt {MOTIF}\) does not natively support \(\mathtt {NOT}\) gates because they would break the invariant: \(\mathtt {NOT}\) maps \([\![0 ]\!]\) to \([\![1 ]\!]\). \(\mathtt {NOT}\) gates can be implemented by \(\mathtt {XOR}\) gates together with a distinguished wire that holds \([\![1 ]\!]\) on the active branch and \([\![0 ]\!]\) on the inactive branch.

  3. 3.

    We cannot support \(\varPi _{\mathtt {Base}}\) as a black-box because it is possible to implement a protocol that securely handles netlists, but that is insecure when given masked triples. For example, the parties could out-of-band check the validity of triples and reveal all inputs if the triples are found invalid. Therefore, \(\varPi _{\mathtt {Base}}\) is a white-box protocol.

  4. 4.

    One caveat is that broadcasts used to reconstruct the circuit’s outputs must \(\mathtt {XOR}\) to the correct output value. The simulator must arrange the simulated output broadcasts such that they appropriately add up. This is typical in MPC proofs and is easy to set up.

References

  1. Alhassan, M.Y., Günther, D., Kiss, Á., Schneider, T.: Efficient and scalable universal circuits. Cryptology ePrint Archive, Report 2019/348 (2019). https://eprint.iacr.org/2019/348

  2. Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 535–548. ACM Press, November 2013

    Google Scholar 

  3. Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators: silent OT extension and more. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 489–518. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_16

    Chapter  Google Scholar 

  4. 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). https://doi.org/10.1007/978-3-642-20465-4_11

    Chapter  Google Scholar 

  5. Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34

    Chapter  Google Scholar 

  6. Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In: Rudnicki, P. (ed.) 8th ACM PODC, pp. 201–209. ACM, August 1989

    Google Scholar 

  7. Bunn, P., Katz, J., Kushilevitz, E., Ostrovsky, R.: Efficient 3-party distributed ORAM. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 215–232. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_11

    Chapter  Google Scholar 

  8. Cramer, R., Damgård, I., Escudero, D., Scholl, P., Xing, C.: SPD \(\mathbb{Z}_{2^k}\): efficient MPC mod \(2^k\) for dishonest majority. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 769–798. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_26

    Chapter  Google Scholar 

  9. 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). https://doi.org/10.1007/978-3-642-40203-6_1

    Chapter  Google Scholar 

  10. 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 

  11. Frederiksen, T.K., Keller, M., Orsini, E., Scholl, P.: A unified approach to MPC with preprocessing using OT. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 711–735. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_29

    Chapter  Google Scholar 

  12. Günther, D., Kiss,Á., Schneider, T.: More efficient universal circuit constructions. Cryptology ePrint Archive, Report 2017/798 (2017). http://eprint.iacr.org/2017/798

  13. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pages 218–229. ACM Press, May 1987

    Google Scholar 

  14. Heath, D., Kolesnikov, V.: Stacked garbling. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 763–792. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_27

    Chapter  Google Scholar 

  15. Heath, D., Kolesnikov, V.: Stacked garbling for disjunctive zero-knowledge proofs. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 569–598. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_19

    Chapter  Google Scholar 

  16. Heath, D., Kolesnikov, V., Peceny, S.: MOTIF: (almost) free branching in GMW - via vector-scalar multiplication. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. Part III, volume 12493 of LNCS, pp. 3–30. Springer, Heidelberg (2020)

    Chapter  Google Scholar 

  17. Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9

    Chapter  Google Scholar 

  18. Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 54–70. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_4

    Chapter  Google Scholar 

  19. Kolesnikov, V.: FreeIF: how to omit inactive branches and implement \(\cal{S}\)-universal garbled circuit (Almost) for free. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 34–58. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_2

    Chapter  Google Scholar 

  20. Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 830–842. ACM Press, October 2016

    Google Scholar 

  21. Keller, M., Pastro, V., Rotaru, D.: Overdrive: making SPDZ great again. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 158–189. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_6

    Chapter  Google Scholar 

  22. Kolesnikov, V., Schneider, T.: A practical universal circuit construction and secure evaluation of private functions. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 83–97. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85230-8_7

    Chapter  MATH  Google Scholar 

  23. Kiss, Á., Schneider, T.: Valiant’s universal circuit is practical. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 699–728. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_27

    Chapter  Google Scholar 

  24. Lipmaa, H., Mohassel, P., Sadeghian, S.: Valiant’s universal circuit: Improvements, implementation, and applications. Cryptology ePrint Archive, Report 2016/017 (2016). http://eprint.iacr.org/2016/017

  25. Larraia, E., Orsini, E., Smart, N.P.: Dishonest majority multi-party computation for binary circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 495–512. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_28

    Chapter  Google Scholar 

  26. Liu, H., Yu, Y., Zhao, S., Zhang, J., Liu, W.: Pushing the limits of valiant’s universal circuits: simpler, tighter and more compact. IACR Cryptology ePrint Archive 2020, 161 (2020)

    Google Scholar 

  27. Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_40

    Chapter  Google Scholar 

  28. Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms For Computers and Calculators. AP Academic Press, New York (1978)

    MATH  Google Scholar 

  29. Valiant, L.G.: Universal circuits (preliminary report). In: STOC, pp. 196–203, New York, NY, USA, 1976. ACM Press

    Google Scholar 

  30. Wang, X., Malozemoff, A.J., Katz, J.: MP-toolkit: Efficient MultiParty computation toolkit (2016). https://github.com/emp-toolkit

  31. Zhao, S., Yu, Y., Zhang, J., Liu, H.: Valiant’s universal circuits revisited: an overall improvement and a lower bound. Cryptology ePrint Archive, Report 2018/943 (2018). https://eprint.iacr.org/2018/943

Download references

Acknowledgements

This work was supported in part by NSF award #1909769, by a Facebook research award, and by Georgia Tech’s IISP cybersecurity seed funding (CSF) award.

Author information

Authors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    David Heath, Vladimir Kolesnikov & Stanislav Peceny

Authors
  1. David Heath
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vladimir Kolesnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stanislav Peceny
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Heath .

Editor information

Editors and Affiliations

  1. Texas A&M University, College Station, TX, USA

    Juan A. Garay

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Heath, D., Kolesnikov, V., Peceny, S. (2021). Masked Triples. In: Garay, J.A. (eds) Public-Key Cryptography – PKC 2021. PKC 2021. Lecture Notes in Computer Science(), vol 12711. Springer, Cham. https://doi.org/10.1007/978-3-030-75248-4_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75248-4_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-75247-7

  • Online ISBN: 978-3-030-75248-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation