Article

Secure two-party computation via cut-and-choose oblivious transfer

Authors:

Yehuda Lindell,

Benny PinkasAuthors Info & Claims

TCC'11: Proceedings of the 8th conference on Theory of cryptography

Pages 329 - 346

Published: 28 March 2011 Publication History

Abstract

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulationbased ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao's protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

References

[1]

Aumann, Y., Lindell, Y.: Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. Journal of Cryptology 23(2), 281-343 (2010)

Digital Library

[2]

Beaver, D.: Foundations of Secure Interactive Computing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 377-391. Springer, Heidelberg (1992)

Digital Library

[3]

Canetti, R.: Security and Composition of Multi-party Cryptographic Protocols. Journal of Cryptology 13(1), 143-202 (2000)

[4]

Canetti, R.: Universally Composable Security: A New Paradigm for Cryptographic Protocols. In: 42nd FOCS, pp. 136-145 (2001), Full version http://eprint.iacr.org/2000/067

Digital Library

[5]

Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19-40. Springer, Heidelberg (2001)

Digital Library

[6]

Carter, L., Wegman, M.N.: Universal Classes of Hash Functions. JCSS 18(2), 143- 154 (1979)

[7]

Cramer, R., Damgård, I., Schoenmakers, B.: Proof of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174-187. Springer, Heidelberg (1994)

Digital Library

[8]

Damgård, I.: On S Protocols, http://www.daimi.au.dk/~ivan/Sigma.pdf

[9]

Dodis, Y., Shoup, V., Walfish, S.: Efficient Constructions of Composable Commitments and Zero-Knowledge Proofs. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 515-535. Springer, Heidelberg (2008)

Digital Library

[10]

Dodis, Y., Gennaro, R., Håstad, J., Krawczyk, H., Rabin, T.: Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 494-510. Springer, Heidelberg (2004)

[11]

Garay, J., MacKenzie, P., Yang, K.: Strengthening Zero-Knowledge Protocols Using Signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 177-194. Springer, Heidelberg (2003)

Digital Library

[12]

Goldreich, O.: Foundations of Cryptography: Volume 2 - Basic Applications. Cambridge University Press, Cambridge (2004)

Digital Library

[13]

Goldreich, O., Micali, S., Wigderson, A.: How to Play any Mental Game - A Completeness Theorem for Protocols with Honest Majority. In: 19th STOC, pp. 218-229 (1987), For details see {12, Chapter 7}

Digital Library

[14]

Goldwasser, S., Levin, L.: Fair Computation of General Functions in Presence of Immoral Majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77-93. Springer, Heidelberg (1991)

Digital Library

[15]

Goyal, V., Mohassel, P., Smith, A.: Efficient Two Party and Multi Party Computation Against Covert Adversaries. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289-306. Springer, Heidelberg (2008)

Digital Library

[16]

Hastad, J., Impagliazzo, R., Levin, L., Luby, M.: Construction of a Pseudo-random Generator from any One-way Function. SIAM Journal on Computing 28(4), 1364- 1396 (1999)

Digital Library

[17]

Hazay, C., Nissim, K.: Efficient Set Operations in the Presence of Malicious Adversaries. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 312-331. Springer, Heidelberg (2010)

Digital Library

[18]

Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer - Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572-591. Springer, Heidelberg (2008)

Digital Library

[19]

Ishai, Y., Prabhakaran, M., Sahai, A.: Secure Arithmetic Computation with No Honest Majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 294-314. Springer, Heidelberg (2009)

Digital Library

[20]

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)

Digital Library

[21]

Kiraz, M., Schoenmakers, B.: A Protocol Issue for the Malicious Case of Yao's Garbled Circuit Construction. In: Proceedings of 27th Symposium on Information Theory in the Benelux, pp. 283-290 (2006)

[22]

Lindell, Y.: Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. Journal of Cryptology 16(3), 143-184 (2003)

[23]

Lindell, Y., Pinkas, B.: A Proof of Yao's Protocol for Secure Two-Party Computation. The Journal of Cryptology 22(2), 161-188 (2009)

Digital Library

[24]

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)

Digital Library

[25]

MacKenzie, P., Yang, K.: On Simulation-Sound Trapdoor Commitments. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 382- 400. Springer, Heidelberg (2004)

[26]

Micali, S., Rogaway, P.: Secure Computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392-404. Springer, Heidelberg (1992)

[27]

Naor, M., Reingold, O.: Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions. In: 36th FOCS, pp. 170-181 (1995)

Digital Library

[28]

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)

Digital Library

[29]

Orlandi, C.: Personal communication (2010)

[30]

Peikert, C., Vaikuntanathan, V., Waters, B.: A Framework for Efficient and Composable Oblivious Transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554-571. Springer, Heidelberg (2008)

Digital Library

[31]

Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure Two-Party Computation Is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250-267. Springer, Heidelberg (2009)

Digital Library

[32]

Shamir, A.: How to Share a Secret. Communications of the ACM 22(11), 612-613 (1979)

Digital Library

[33]

Yao, A.C.: How to Generate and Exchange Secrets. In: 27th FOCS, pp. 162-167 (1986)

Digital Library

Cited By

Colombo SNikitin KCorrigan-Gibbs HWu DFord BCalandrino JTroncoso C(2023)Authenticated private information retrievalProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620452(3835-3851)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620452
Choi JTian DHernandez GPatton CMood BShrimpton TButler KTraynor PGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)A Hybrid Approach to Secure Function Evaluation using SGXProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329835(100-113)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329835
Hazay CMikkelsen GRabin TToft TNicolosi A(2019)Efficient RSA Key Generation and Threshold Paillier in the Two-Party SettingJournal of Cryptology10.1007/s00145-017-9275-732:2(265-323)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00145-017-9275-7
Show More Cited By

Recommendations

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed ...
Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
An efficient fair UC-secure protocol for two-party computation

With the development of modern Internet and mobile networks, there is an increasing need for collaborative privacy-preserving applications. Secure multi-party computation SMPC gives a general solution to these applications and has become a hot topic. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'11: Proceedings of the 8th conference on Theory of cryptography

March 2011

629 pages

ISBN:9783642195709

Editor:
Yuval Ishai
Technion, Computer Science Department, Haifa, Israel

Sponsors

IACR: International Association for Cryptologic Research

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 March 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Colombo SNikitin KCorrigan-Gibbs HWu DFord BCalandrino JTroncoso C(2023)Authenticated private information retrievalProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620452(3835-3851)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620452
Choi JTian DHernandez GPatton CMood BShrimpton TButler KTraynor PGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)A Hybrid Approach to Secure Function Evaluation using SGXProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329835(100-113)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329835
Hazay CMikkelsen GRabin TToft TNicolosi A(2019)Efficient RSA Key Generation and Threshold Paillier in the Two-Party SettingJournal of Cryptology10.1007/s00145-017-9275-732:2(265-323)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00145-017-9275-7
Hazay C(2018)Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFsJournal of Cryptology10.1007/s00145-017-9263-y31:2(537-586)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s00145-017-9263-y
Rasheed AKenneth AMahapatra RPuthal DTrien JProwell SGoodall JBeaver JBridges R(2017)Private matching and set intersection computation in multi-agent and industrial control systemsProceedings of the 12th Annual Conference on Cyber and Information Security Research10.1145/3064814.3064817(1-6)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3064814.3064817
Asharov GLindell YSchneider TZohner M(2017)More Efficient Oblivious Transfer ExtensionsJournal of Cryptology10.1007/s00145-016-9236-630:3(805-858)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00145-016-9236-6
Garg SMukherjee PPandey OPolychroniadou A(2016)The Exact Round Complexity of Secure ComputationProceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966610.5555/3081738.3081754(448-476)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081738.3081754
Doerner JEvans Dshelat aWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)Secure Stable Matching at ScaleProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978373(1602-1613)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978373
Lindell Y(2016)Fast Cut-and-Choose-Based Protocols for Malicious and Covert AdversariesJournal of Cryptology10.1007/s00145-015-9198-029:2(456-490)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s00145-015-9198-0
Gennaro RHazay CSorensen J(2016)Automata Evaluation and Text Search Protocols with Simulation-Based SecurityJournal of Cryptology10.1007/s00145-014-9193-x29:2(243-282)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s00145-014-9193-x
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents