Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks Read chapter Read first chapter

2017 | OriginalPaper | Chapter

A New Approach to Round-Optimal Secure Multiparty Computation

Authors : Prabhanjan Ananth, Arka Rai Choudhuri, Abhishek Jain

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present a new approach towards constructing round-optimal secure multiparty computation (MPC) protocols against malicious adversaries without trusted setup assumptions. Our approach builds on ideas previously developed in the context of covert multiparty computation [Chandran et al., FOCS’07] even though we do not seek covert security. Using our new approach, we obtain the following results:
  • A five round MPC protocol based on the Decisional Diffie-Hellman (DDH) assumption.
  • A four round MPC protocol based on one-way permutations and sub-exponentially secure DDH. This result is optimal in the number of rounds.
Previously, no four-round MPC protocol for general functions was known and five-round protocols were only known based on indistinguishability obfuscation (and some additional assumptions) [Garg et al., EUROCRYPT’16].

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Topology-Hiding Computation on All Graphs
next chapter Watermarking Cryptographic Functionalities from Standard Lattice Assumptions
Footnotes
1
Garg et al. also construct a four-round protocol for the coin-tossing functionality. In this work, we are interested in MPC for general functions.
 
2
We use low-depth PRGs to obtain degree-three randomizing polynomials for general functions [2].
 
3
We use a variant of the extractable commitment scheme in [38] for this purpose. This variant has been used in many prior works such as [13, 19, 21] because it is “rewinding secure” – a property that is used in the security proofs.
 
4
Note that the witness for these proofs corresponds to the adversary’s input and random tape which is already fixed in the first round.
 
5
We also use the fact that argument system of [9] allows for simulating multiple proofs executed in parallel.
 
6
We believe that some of the use of complexity leveraging in our hybrids can be avoided by modifications to our protocol. We leave further exploration of this direction for subsequent work.
 
7
A randomized encoding of function f and input x is such that, the output f(x) can be recovered from this encoding and at the same time, this encoding should not leak any information about either f or x.
 
8
The terms randomized encodings and randomizing polynomials are interchangeably used.
 
9
It actually proves that the non-malleable commitment contains the masked witness, where the mask is sent separately. But we ignore this technicality for the discussion.
 
10
While in all other cases, we have required the use of public coins, we can make do with a private coin protocol here. This will become apparent in the proof.
 
Literature
1.
2.
Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Comput. Complex. 15(2), 115–162 (2006)MathSciNetCrossRefMATH
3.
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). doi:10.​1007/​978-3-642-29011-4_​29 CrossRef
4.
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44647-8_​1 CrossRef
5.
Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, California, USA, Proceedings, 21–24 October 2006, pp. 345–354 (2006)
6.
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, USA, 13–17 May 1990, pp. 503–513 (1990)
7.
8.
Chandran, N., Goyal, V., Ostrovsky, R., Sahai, A.: Covert multi-party computation. In: 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, pp. 238–248. IEEE (2007)
9.
Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: 4-round concurrent non-malleable commitments from one-way functions. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10401, pp. 127–157. Springer, Cham (2017)
10.
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Advances in Cryptology: Proceedings of CRYPTO 1982, Santa Barbara, California, USA, 23–25 August 1982, pp. 205–210 (1982)
11.
Garg, S., Gentry, C., Halevi, S., Raykova, M.: Two-round secure MPC from indistinguishability obfuscation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 74–94. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54242-8_​4 CrossRef
12.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40–49 (2013)
13.
Garg, S., Goyal, V., Jain, A., Sahai, A.: Concurrently secure computation in constant rounds. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 99–116. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​8 CrossRef
14.
Garg, S., Mukherjee, P., Pandey, O., Polychroniadou, A.: The exact round complexity of secure computation. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 448–476. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​16 CrossRef
15.
Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications, vol. 2. Cambridge University Press, Cambridge (2009)MATH
16.
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC (1987)
17.
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC, pp. 291–304 (1985)
18.
Goyal, V.: Constant round non-malleable protocols using one way functions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011, pp. 695–704 (2011)
19.
Goyal, V.: Positive results for concurrently secure computation in the plain model. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20–23 October 2012, pp. 41–50 (2012)
20.
Goyal, V., Jain, A.: On the round complexity of covert computation. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 191–200. ACM (2010)
21.
Goyal, V., Jain, A., Ostrovsky, R.: Password-authenticated session-key generation on the internet in the plain model. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 277–294. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​15 CrossRef
22.
Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: STOC, pp. 1128–1141 (2016)
23.
Goyal, V., Richelson, S., Rosen, A., Vald, M.: An algebraic approach to non-malleability. In: FOCS, pp. 41–50 (2014)
24.
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, 2000, Proceedings, pp. 294–304. IEEE (2000)
25.
26.
27.
Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 578–595. Springer, Heidelberg (2003). doi:10.​1007/​3-540-39200-9_​36 CrossRef
28.
29.
Lapidot, D., Shamir, A.: Publicly verifiable non-interactive zero-knowledge proofs. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 353–365. Springer, Heidelberg (1991). doi:10.​1007/​3-540-38424-3_​26 CrossRef
30.
31.
32.
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, Washington, DC, USA, 7–9 January 2001, pp. 448–457 (2001)
33.
34.
Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 13–16 June 2004, pp. 232–241 (2004)
35.
36.
Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent zero knowledge with logarithmic round-complexity. In: FOCS, pp. 366–375 (2002)
37.
Rabin, M.O.: How to exchange secrets with oblivious transfer. IACR Cryptology ePrint Archive 2005, 187 (2005)
38.
39.
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, 17–18 October 1999, pp. 543–553 (1999)
40.
von-Ahn, L., Hopper, N., Langford, J.: Covert two-party computation. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 513–522. ACM (2005)
41.
Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: FOCS, pp. 531–540 (2010)
42.
Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167 (1986)
Metadata
Title
A New Approach to Round-Optimal Secure Multiparty Computation
Authors
Prabhanjan Ananth
Arka Rai Choudhuri
Abhishek Jain
Copyright Year
2017
Book
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-63688-7_16

Premium Partner

    Image Credits