Skip to main content
Springer Nature Link
Log in

A Note on Low-Communication Secure Multiparty Computation via Circuit Depth-Reduction

  • Conference paper
  • First Online:
Theory of Cryptography (TCC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15367))

Included in the following conference series:

  • 196 Accesses

Abstract

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth “chunks”. This approach was however previously limited to circuits with a “layered” structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions:

  • Fractionally linear-communication MPC in the correlated randomness model. We provide an N-party protocol for computing an n-input, m-output \(\mathbb {F}\)-arithmetic circuit with s internal gates (over any basis of binary gates) with communication complexity \((\frac{2}{3}s + n + m)\cdot N\cdot \log |\mathbb {F}|\), which can be improved to \(((1+\epsilon )\cdot \frac{2}{5}s+n+m)\cdot N\cdot \log |\mathbb {F}|\) (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than \(s\cdot N\cdot \log |\mathbb {F}|\) bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold.

  • Sublinear-Communication MPC. Assuming the existence of N-party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure N-party computation for all \(\log ^{1+o(1)}\)-depth (resp. \((\log \log )^{1+o(1)}\)-depth) circuits. Previously, this result was limited to \((\mathcal {O}(\log ))\)-depth (resp. \((\mathcal {O}(\log \log ))\)-depth) circuits, or to circuits with a specific structure (e.g. layered).

  • The \(\boldsymbol{{N\atopwithdelims ()1}}\)-OT complexity of MPC. We introduce the “\(N\atopwithdelims ()1\)-OT complexity of MPC” of a function f, denoted \(C_N(f)\), as the number of oracle calls required to securely compute f in the \(N\atopwithdelims ()1\)-OT hybrid model. We establish the following upper bound: for every \(N\ge 2\), \(C_N(f) \le (1+g(N))\cdot \frac{2 |f|}{5}\), where g(N) is an explicit vanishing function.

We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.

P. Meyer—Most of this work was done while P. Meyer was a PhD student jointly at Reichman University, Herzliya, ISRAEL and Université Paris Cité, CNRS, IRIF, Paris, FRANCE.

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
€32.70 /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
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 77.03
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 94.94
Price includes VAT (France)
  • 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.

    If we lift this restriction, Beaver, Feigenbaum, Kilian, and Rogoway [BFKR91] showed that any function from \(\{0,1\} ^n\) to \(\{0,1\} \) can be securely computed in the presence of up to t corruptions by \(N = \mathcal {O}(t \cdot n/ \log n)\) computationally unbounded parties (which the protocol indeed requires to use an exponential amount of computation) using \(\textsf{poly}(n + N)\) communication. In addition, the protocol of [IKM+13], which we state as a result for securely computing functions with a polynomial-size look-up table, can be applied to general functions if the parties are computationally unbounded (and have access to a doubly exponential amount of correlated randomness).

  2. 2.

    These HSS schemes support bounded-integer computation, which translates to low-communication secure computation over arbitrary fields using hybrid encryption.

  3. 3.

    Note that this class is somewhat related to logarithmic-depth branching programs.

  4. 4.

    The complexity we provide here is for when the depth is at most \((\log \log s)/4\), not \((\log \log s-\log \log \log s)\); this is done in order to simplify the expression and absorb some negligible terms.

  5. 5.

    A synchronous circuit is a layered circuit whose input gates are all in the first layer.

  6. 6.

    We note there is some inconsistency in the literature in how the vertex cover problem is extended to directed graphs.

  7. 7.

    To obtain these bounds, observe that the undirected underlying graphs of fan-in two DAGs have average degree no more than 4. We do not formally state these results (which are direct corollaries of [BKKS11]) in the body however, as we provide improved bounds in Sect. 4.2.

  8. 8.

    In order to simplify the expressions of M, we assume none of the input gates are also outputs.

  9. 9.

    We note that Valiant’s algorithm was previously applied in essentially the same way to other—yet incomparable—notions of depth-reduction and pebbling games, in the study of memory-hard functions [AB16, ABH17].

  10. 10.

    Beware that the literature is inconsistent on whether the length of a path should be counted in vertices or edges.

  11. 11.

    We refer to Sect. 2.2 for what we mean by “output nodes of a DAG”.

References

  1. Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, Part II, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_9

    Chapter  Google Scholar 

  2. Alwen, J., Blocki, J., Harsha, B: Practical graphs for optimal side-channel resistant memory-hard functions. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1001–1017. ACM Press, October/November 2017

    Google Scholar 

  3. Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, Part III, vol. 10212, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_1

    Chapter  Google Scholar 

  4. Abram, D., Damgård, I., Orlandi, C., Scholl, P.: An algebraic framework for silent preprocessing with trustless setup and active security. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, Part IV, vol. 13510, pp. 421–452 (2022). Springer, Cham. https://doi.org/10.1007/978-3-031-15985-5_15

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

    Chapter  Google Scholar 

  6. Abram, D., Roy, L., Scholl, P.: Succinct homomorphic secret sharing. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024. LNCS, vol. 14656, pp. 301–330. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-58751-1_11

  7. Boyle, E., Couteau, G., Meyer, P.: Sublinear secure computation from new assumptions. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. LNCS, Part II, vol. 13748, pp. 121–150. Springer, Cham. (2022). https://doi.org/10.1007/978-3-031-22365-5_5

  8. Boyle, E., Couteau, G., Meyer, P.: Sublinear-communication secure multiparty computation does not require FHE. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, Part II, vol. 14005, pp. 159–189. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30617-4_6

  9. Borowiecki, M., Drgas-Burchardt, E., Sidorowicz, E.: A feedback vertex set of 2-degenerate graphs. Theor. Comput. Sci. 557, 50–58 (2014)

    Article  MathSciNet  Google Scholar 

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

  11. Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Security with low communication overhead. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 62–76. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_5

    Chapter  Google Scholar 

  12. Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, Part I, vol. 9814, pp. 509–539. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_19

    Chapter  Google Scholar 

  13. Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1292–1303. ACM Press, October 2016

    Google Scholar 

  14. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309–325. ACM, January 2012

    Google Scholar 

  15. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1–10. ACM Press, May 1988

    Google Scholar 

  16. Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317–342. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_14

    Chapter  Google Scholar 

  17. Brešar, B., Kardoš, F., Katrenič, J., Semanišin, G.: Minimum k-path vertex cover. Discrete Appl. Math. 159(12), 1189–1195 (2011)

    Article  MathSciNet  Google Scholar 

  18. Boyle, E., Kohl, L., Scholl, P.: Homomorphic secret sharing from lattices without FHE. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, Part II, vol. 11477, pp. 3–33. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_1

    Chapter  Google Scholar 

  19. Benhamouda, F., Lepoint, T., Mathieu, C., Zhou, H.: Optimization of bootstrapping in circuits. In: Klein, P.N. (ed.) 28th SODA, pp. 2423–2433. ACM-SIAM, January 2017

    Google Scholar 

  20. Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, pp. 97–106. IEEE Computer Society Press, October 2011

    Google Scholar 

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

    Google Scholar 

  22. Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86(2), 243–266 (1991)

    Article  MathSciNet  Google Scholar 

  23. Couteau, G., Meyer, P.: Breaking the circuit size barrier for secure computation under quasi-polynomial LPN. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, Part II, vol. 12697, pp. 842–870. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_29

    Chapter  Google Scholar 

  24. Chillotti, I., Orsini, E., Scholl, P., Smart, N.P., Van Leeuwen, B.: Scooby: improved multi-party homomorphic secret sharing based on FHE. In: SCN 2022 (2022). https://eprint.iacr.org/2022/862

  25. Couteau, G.: A note on the communication complexity of multiparty computation in the correlated randomness model. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, Part II, vol. 11477, pp. 473–503. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_17

    Chapter  Google Scholar 

  26. Damgård, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 54–74. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_4

    Chapter  Google Scholar 

  27. Dao, Q., Ishai, Y., Jain, A., Lin, H.: Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 315–348. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_11

  28. Damgård, I., Nielsen, J.B., Nielsen, M., Ranellucci, S.: The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, Part I, vol. 10401, pp. 167–187. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_6

    Chapter  Google Scholar 

  29. Erdös, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Mathematica Academiae Scientiarum Hungarica 17, 61–99 (1966)

    Article  MathSciNet  Google Scholar 

  30. Fazio, N., Gennaro, R., Jafarikhah, T., Skeith, W.E.: Homomorphic secret sharing from Paillier encryption. In: Okamoto, T., Yu, Y., Au, M.H., Li, Y. (eds.) ProvSec 2017. LNCS, vol. 10592, pp. 381–399. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68637-0_23

    Chapter  Google Scholar 

  31. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press, May/June 2009

    Google Scholar 

  32. Gál, A., Jang, J.-T.: The size and depth of layered Boolean circuits. Inf. Process. Lett. 111(5), 213–217 (2011)

    Article  MathSciNet  Google Scholar 

  33. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: 27th FOCS, pp. 174–187. IEEE Computer Society Press, October 1986

    Google Scholar 

  34. 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, pp. 218–229. ACM Press, May 1987

    Google Scholar 

  35. Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., Paskin-Cherniavsky, A.: On the power of correlated randomness in secure computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 600–620. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_34

    Chapter  Google Scholar 

  36. Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th ACM STOC, pp. 723–732. ACM Press, May 1992

    Google Scholar 

  37. Lepoint, T., Paillier, P.: On the minimal number of bootstrappings in homomorphic circuits. In: Adams, A.A., Brenner, M., Smith, M. (eds.) FC 2013. LNCS, vol. 7862, pp. 189–200. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41320-9_13

    Chapter  Google Scholar 

  38. Lick, D.R., White, A.T.: k-degenerate graphs. Can. J. Math. 22(5), 1082–1096 (1970)

    Article  MathSciNet  Google Scholar 

  39. Matula, D.W.: A min-max theorem for graphs with application to graph coloring. In: SIAM 1968 National Meeting, SIAM Review, vol. 10, no. 4, pp. 481–482 (1968)

    Google Scholar 

  40. Naumann, U.: Dag reversal is NP-complete. J. Discrete Algorithms 7(4), 402–410 (2009)

    Article  MathSciNet  Google Scholar 

  41. Orlandi, C., Scholl, P., Yakoubov, S.: The rise of Paillier: homomorphic secret sharing and public-key silent OT. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, Part I, vol. 12696, pp. 678–708. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_24

    Chapter  Google Scholar 

  42. Paindavoine, M., Vialla, B.: Minimizing the number of bootstrappings in fully homomorphic encryption. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 25–43. Springer, Heidelberg (2016)

    Google Scholar 

  43. Roy, L., Singh, J.: Large message homomorphic secret sharing from DCR and applications. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, Part III, vol. 12827, pp. 687–717. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_23

    Chapter  Google Scholar 

  44. Schnitger, G.: On depth-reduction and grates. In: 24th Annual Symposium on Foundations of Computer Science (SFCS 1983), pp. 323–328 (1983)

    Google Scholar 

  45. Tu, J.: A survey on the k-path vertex cover problem. Axioms 11(5) (2022)

    Google Scholar 

  46. Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol. 53, pp. 162–176. Springer, Heidelberg (1977). https://doi.org/10.1007/3-540-08353-7_135

    Chapter  Google Scholar 

  47. Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In:27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986

    Google Scholar 

  48. Yu, Yu., Zhang, J., Weng, J., Guo, C., Li, X.: Collision resistant hashing from sub-exponential learning parity with noise. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, Part II, vol. 11922, pp. 3–24. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_1

    Chapter  Google Scholar 

Download references

Acknowledgments

We thank Mikaël Rabie and Elette Boyle for helpful discussions and pointers to respectively degenerate graphs and memory-hard functions.

Geoffroy Couteau was supported by the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE39-0001 (project SCENE), and by the France 2030 ANR Project ANR22-PECY-003 SecureCompute. Pierre Meyer was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreements numbers 852952 (HSS) and 803096 (SPEC).

Author information

Authors and Affiliations

  1. Université Paris Cité, CNRS, IRIF, Paris, France

    Pierre Charbit, Geoffroy Couteau & Reza Naserasr

  2. Aarhus University, Aarhus, Denmark

    Pierre Meyer

Authors
  1. Pierre Charbit
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Geoffroy Couteau
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pierre Meyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Reza Naserasr
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pierre Charbit .

Editor information

Editors and Affiliations

  1. NTT Research, Sunnyvale, CA, USA

    Elette Boyle

  2. University of Virginia, Charlottesville, VA, USA

    Mohammad Mahmoody

Rights and permissions

Reprints and permissions

Copyright information

© 2025 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Charbit, P., Couteau, G., Meyer, P., Naserasr, R. (2025). A Note on Low-Communication Secure Multiparty Computation via Circuit Depth-Reduction. In: Boyle, E., Mahmoody, M. (eds) Theory of Cryptography. TCC 2024. Lecture Notes in Computer Science, vol 15367. Springer, Cham. https://doi.org/10.1007/978-3-031-78023-3_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-78023-3_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-78022-6

  • Online ISBN: 978-3-031-78023-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation