×
Canetti, Ran; Poburinnaya, Oxana; Venkitasubramaniam, Muthuramakrishnan

Better two-round adaptive multi-party computation. (English) Zbl 1400.94130

Fehr, Serge (ed.), Public-key cryptography – PKC 2017. 20th IACR international conference on practice and theory in public-key cryptography, Amsterdam, The Netherlands, March 28–31, 2017. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-54387-0/pbk; 978-3-662-54388-7/ebook). Lecture Notes in Computer Science 10175, 396-427 (2017).
Summary: The only known two-round multi-party computation protocol that withstands adaptive corruption of all parties is the ingenious protocol of S. Garg and A. Polychroniadou [TCC 2015, Lect. Notes Comput. Sci. 9015, 614–637 (2015; Zbl 1382.94108)]. We present protocols that improve on the GP protocol in a number of ways. First, concentrating on the semi-honest case and taking a different approach than GP, we show a two-round, adaptively secure protocol where:
– Only a global (i.e., non-programmable) reference string is needed. In contrast, in GP the reference string is programmable, even in the semi-honest case.
– Only polynomially-secure indistinguishability obfuscation for circuits and injective one way functions are assumed. In GP, sub-exponentially secure IO is assumed.
Second, we show how to make the GP protocol have only RAM complexity, even for Byzantine corruptions. For this we construct the first statistically-sound non-interactive zero-knowledge scheme with RAM complexity.
For the entire collection see [Zbl 1358.94006].

Cited in 9 Documents

MSC:

94A60 Cryptography

Citations:

Zbl 1382.94108
Cite Review PDF
Full Text: DOI

References:

[1] Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Comput. Complex. 15(2), 115–162 (2006) · Zbl 1143.94009 · doi:10.1007/s00037-006-0211-8
[2] Bitansky, N., Canetti, R., Halevi, S.: Leakage-tolerant interactive protocols. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 266–284. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-28914-9_15 · Zbl 1296.94088 · doi:10.1007/978-3-642-28914-9_15
[3] Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (Parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742–762. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48000-7_36 · Zbl 1352.94027 · doi:10.1007/978-3-662-48000-7_36
[4] Bellare, M., Stepanovs, I., Tessaro, S.: Poly-many hardcore bits for any one-way function and a framework for differing-inputs obfuscation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 102–121. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45608-8_6 · Zbl 1317.94085 · doi:10.1007/978-3-662-45608-8_6
[5] Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). doi: 10.1007/978-3-540-70936-7_4 · Zbl 1129.94014 · doi:10.1007/978-3-540-70936-7_4
[6] Canetti, R., Goldwasser, S., Poburinnaya, O.: Adaptively Secure Two-Party Computation from Indistinguishability Obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 557–585. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46497-7_22 · Zbl 1382.94077 · doi:10.1007/978-3-662-46497-7_22
[7] Canetti, R., Holmgren, J.: Fully succinct garbled RAM. In: Proceedings of the ACM Conference on Innovations in Theoretical Computer Science. Cambridge, MA, USA, 14–16 January, pp. 169–178 (2016) · Zbl 1334.68064 · doi:10.1145/2840728.2840765
[8] Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Succinct garbling and indistinguishability obfuscation for RAM programs. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC. Portland, OR, USA, 14–17 June, pp. 429–437 (2015) · Zbl 1321.94050 · doi:10.1145/2746539.2746621
[9] Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, 19–21 May. Montréal, Québec, Canada, pp. 494–503 (2002) · Zbl 1192.94112 · doi:10.1145/509907.509980
[10] Canetti, R., Poburinnaya, O., Raykova, M.: Optimal-rate non-committing encryption in a CRS model. IACR Cryptology ePrint Archive 2016:511 (2016) · Zbl 1417.94049
[11] Canetti, R., Poburinnaya, O., Venkitasubramaniam, M.: Better two-round adaptive multiparty computation. In: Cryptology ePrint Archive, Report 2016/614 (2016). http://eprint.iacr.org/2016/614 · Zbl 1369.68206
[12] Dachman-Soled, D., Katz, J., Rao, V.: Adaptively secure, universally composable, multi-party computation in constant rounds. IACR Cryptology ePrint Archive 2014, 858 (2014) · Zbl 1382.94086
[13] Damgård, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 144–163. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-19571-6_10 · Zbl 1295.94046 · doi:10.1007/978-3-642-19571-6_10
[14] Gentry, C.: A Fully Homomorphic Encryption Scheme. Ph.D. thesis. Stanford, CA, USA, AAI3382729 (2009) · Zbl 1304.94059
[15] 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 · Zbl 1317.94109 · doi:10.1007/978-3-642-54242-8_4
[16] Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006). doi: 10.1007/11761679_21 · Zbl 1129.94025 · doi:10.1007/11761679_21
[17] Garg, S., Polychroniadou, A.: Two-round adaptively secure MPC from indistinguishability obfuscation. IACR Cryptology ePrint Archive 2014:844 (2014) · Zbl 1382.94108
[18] Groth, J.: Minimizing non-interactive zero-knowledge proofs using fully homomorphic encryption. IACR Cryptology ePrint Archive 2011:12 (2011)
[19] Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002). doi: 10.1007/3-540-45465-9_22 · doi:10.1007/3-540-45465-9_22
[20] Ishai, Y., Kumarasubramanian, A., Orlandi, C., Sahai, A.: Proceedings on invertible sampling and adaptive security. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 466–482. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-17373-8_27 · Zbl 1253.94052 · doi:10.1007/978-3-642-17373-8_27
[21] Khurana, D., Sahai, A., Waters, B.: How to generate and use universal parameters. IACR Cryptology ePrint Archive 2014:507 (2014) · Zbl 1407.94121
[22] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. Baltimore, Maryland, USA, 13–17 May, pp. 427–437 (1990) · doi:10.1145/100216.100273
[23] Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May-03 June, pp. 475–484 (2014) · Zbl 1315.94102 · doi:10.1145/2591796.2591825
[24] Waters, B.: A punctured programming approach to adaptively secure functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 678–697. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48000-7_33 · Zbl 1351.94071 · doi:10.1007/978-3-662-48000-7_33
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.