Abstract
A secure two-party computation (S2PC) protocol allows two parties to compute over their combined private inputs, as if intermediated by a trusted third party. In the malicious model, this can be achieved with a cut-and-choose of garbled circuits (C&C-GCs), where some GCs are verified for correctness and the remaining are evaluated to determine the circuit output. This paper presents a new C&C-GCs-based S2PC protocol, with significant advantages in efficiency and applicability. First, in contrast with prior protocols that require a majority of evaluated GCs to be correct, the new protocol only requires that at least one evaluated GC is correct. In practice this reduces the total number of GCs to approximately one third, for the same statistical security goal. This is accomplished by augmenting the C&C with a new forge-and-lose technique based on bit commitments with trapdoor. Second, the output of the new protocol includes reusable XOR-homomorphic bit commitments of all circuit input and output bits, thereby enabling efficient linkage of several S2PCs in a reactive manner. The protocol has additional interesting characteristics (which may allow new comparison tradeoffs), such as needing a low number of exponentiations, using a 2-out-of-1 type of oblivious transfer, and using the C&C structure to statistically verify the consistency of input wire keys.
The full version is available at the Cryptology ePrint Archive, Report 2013/577.
Chapter PDF
Similar content being viewed by others
Keywords
References
Barker, E., Barker, W., Burr, W., Polk, W., Smid, M.: Recommendation for Key Management – Part 1: General (Revision 3) – NIST Special Publication 800-57. U.S. Department of Commerce, NIST-ITL-CSD (July 2012)
Brassard, G., Chaum, D., Crépeau, C.: Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988)
Boyar, J., Damgård, I., Peralta, R.: Short Non-Interactive Cryptographic Proofs. J. Cryptology 13, 449–472 (2000)
Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: Proc. STOC 1996, pp. 479–488. ACM, New York (1996)
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Proc. CCS 2012, pp. 784–796. ACM, New York (2012), See also Cryptology ePrint Archive, Report 2012/265
Blum, M.: Coin flipping by telephone a protocol for solving impossible problems. SIGACT News 15, 23–27 (1983)
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols. In: Proc. STOC 1990, pp. 503–513. ACM, New York (1990)
Brandão, L.T.A.N.: A Framework for Interactive Argument Systems using Quasigroupic Homorphic Commitment. Cryptology ePrint Archive, Report 2006/472 (2006)
Bristol Cryptography Group. Circuits of Basic Functions Suitable For MPC and FHE, http://www.cs.bris.ac.uk/Research/CryptographySecurity/MPC/ (accessed June 2013)
Canetti, R.: Security and Composition of Multiparty Cryptographic Protocols. J. Cryptology 13, 143–202 (2000), See also Cryptology ePrint Archive, Report 1998/018
Crépeau, C., van de Graaf, J., Tapp, A.: Committed Oblivious Transfer and Private Multi-party Computation. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 110–123. Springer, Heidelberg (1995)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: Proc. STOC 2002, pp. 494–503. ACM, New York (2002), See also Cryptology ePrint Archive, Report 2002/140
Damgård, I.B.: The application of claw free functions in cryptography. PhD thesis, Aarhus University, Mathematical Institute (1988)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28, 637–647 (1985)
Frederiksen, T.K., Jakobsen, T.P., Nielsen, J.B., Nordholt, P.S., Orlandi, C.: MiniLEGO: Efficient Secure Two-Party Computation from General Assumptions. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 537–556. Springer, Heidelberg (2013), See also Cryptology ePrint Archive, Report 2013/155
Frederiksen, T.K., Nielsen, J.B.: Fast and Maliciously Secure Two-Party Computation Using the GPU. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 339–356. Springer, Heidelberg (2013)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984)
Goldwasser, S., Micali, S., Rivest, R.L.: A “Paradoxical” Solution To The Signature Problem. In: Proc. FOCS 1984, pp. 441–448. IEEE Computer Society (1984)
Goyal, V., Mohassel, P., Smith, A.: Efficient Two Party and Multi Party Computation Against Covert Adversaries. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289–306. Springer, Heidelberg (2008)
Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: Proc. STOC 1987, pp. 218–229. ACM, New York (1987)
Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications, 7th edn. Cambridge University Press, New York (2004)
Huang, Y., Evans, D., Katz, J., Malka, L.: Faster Secure Two-Party Computation Using Garbled Circuits. In: Proc. SEC 2011. USENIX Association (2011)
Huang, Y., Katz, J., Evans, D.: Quid-Pro-Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution. In: Proc. S&P 2012 (May 2012)
Huang, Y., Katz, J., Evans, D.: Efficient Secure Two-Party Computation Using Symmetric Cut-and-Choose. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 18–35. Springer, Heidelberg (2013), See also Cryptology ePrint Archive, Report 2013/081
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)
Jarecki, S., Shmatikov, V.: Efficient Two-Party Secure Computation on Committed Inputs. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 97–114. Springer, Heidelberg (2007)
Kiraz, M.S.: Secure and Fair Two-Party Computation. Phd thesis, Technische Universiteit Eindhoven, Netherlands (2008)
Kolesnikov, V., Kumaresan, R.: Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 205–221. Springer, Heidelberg (2012)
Kolesnikov, V.: Advances and impact of secure function evaluation. Bell Labs Technical Journal 14(3), 187–192 (2009)
Kiraz, M.S., Schoenmakers, B.: A protocol issue for the malicious case of Yao’s garbled circuit construction. In: Proc. 27th Symp. Information Theory in the Benelux, pp. 283–290 (2006)
Kiraz, M.S., Schoenmakers, B.: An Efficient Protocol for Fair Secure Two-Party Computation. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 88–105. Springer, Heidelberg (2008)
Kolesnikov, V., Schneider, T.: Improved Garbled Circuit: Free XOR Gates and Applications. 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. 486–498. Springer, Heidelberg (2008)
Kreuter, B., Shelat, A., Shen, C.-H.: Billion-gate secure computation with malicious adversaries. In: Proc. Security 2012, pp. 285–300. USENIX Association (2012), See also Cryptology ePrint Archive, Report 2012/179
Lindell: Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. J. Cryptology 16(3), 143–184 (2003), See also Cryptology ePrint Archive, Report 2001/107
Lindell, Y.: Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 1–17. Springer, Heidelberg (2013), See also Cryptology ePrint Archive, Report 2013/079
Lindell, Y., Pinkas, B.: Privacy Preserving Data Mining. J. Cryptology 15(3), 177–206 (2002)
Lindell, Y., Pinkas, B.: An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007), See also Cryptology ePrint Archive, Report 2008/049
Lindell, Y., Pinkas, B.: A Proof of Security of Yao’s Protocol for Two-Party Computation. J. Cryptology 22(2), 161–188 (2009)
Lindell, Y., Pinkas, B.: Secure two-party computation via cut-and-choose oblivious transfer. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 329–346. Springer, Heidelberg (2011), See also Cryptology ePrint Archive, Report 2010/284
Mohassel, P., Franklin, M.K.: Efficiency Tradeoffs for Malicious Two-Party Computation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 458–473. Springer, Heidelberg (2006)
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), See also Cryptology ePrint Archive, Report 2011/091
Nielsen, J.B., Orlandi, C.: LEGO for Two-Party Secure Computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 368–386. Springer, Heidelberg (2009), See also Cryptology ePrint Archive, Report 2008/427
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA 2001, pp. 448–457. SIAM, Philadelphia (2001)
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: Proc. EC 1999, pp. 129–139. ACM, New York (1999)
Niven, I.M., Zuckerman, H.S., Montgomery, H.L.: An introduction to the theory of numbers, 5th edn. Wiley (1991)
Pinkas, B.: Fair Secure Two-Party Computation. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 647–647. Springer, Heidelberg (2003)
Pinkas, B., Schneider, T., Smart, N., Williams, S.: Secure Two-Party Computation Is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009), See also Cryptology ePrint Archive, Report 2009/314
Rabin, M.O.: How to exchange secrets with oblivious transfer. Technical Report TR-81, Harvard University, Aiken Computation Lab, Cambridge, MA (1981), See typesetted version in Cryptology ePrint Archive, Report 2005/187
Shelat, A., Shen, C.-H.: Two-Output Secure Computation with Malicious Adversaries. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 386–405. Springer, Heidelberg (2011), See also Cryptology ePrint Archive, Report 2011/533
van de Graaf, J., Peralta, R.: A Simple and Secure Way to Show the Validity of Your Public Key. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 128–134. Springer, Heidelberg (1988)
Woodruff, D.P.: Revisiting the Efficiency of Malicious Two-Party Computation. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 79–96. Springer, Heidelberg (2007), See also Cryptology ePrint Archive, Report 2006/397
Yao, A.C.: Protocols for secure computations. In: Proc. FOCS 1982, pp. 160–164. IEEE Computer Society (1982)
Yao, A.C.-C.: How to generate and exchange secrets. In: FOCS 1986, pp. 162–167 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brandão, L.T.A.N. (2013). Secure Two-Party Computation with Reusable Bit-Commitments, via a Cut-and-Choose with Forge-and-Lose Technique. In: Sako, K., Sarkar, P. (eds) Advances in Cryptology - ASIACRYPT 2013. ASIACRYPT 2013. Lecture Notes in Computer Science, vol 8270. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-42045-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-42045-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-42044-3
Online ISBN: 978-3-642-42045-0
eBook Packages: Computer ScienceComputer Science (R0)