More Web Proxy on the site http://driver.im/

article

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

Authors:

Yehuda Lindell,

Benny PinkasAuthors Info & Claims

Journal of Cryptology, Volume 25, Issue 4

Pages 680 - 722

https://doi.org/10.1007/s00145-011-9107-0

Published: 01 October 2012 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 simulation-based 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]

Y. Aumann, Y. Lindell, Security against covert adversaries: Efficient protocols for realistic adversaries. J. Cryptol. 23(2), 281-343 (2010).

Digital Library

[2]

D. Beaver, Foundations of secure interactive computing, in CRYPTO'91. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 377-391.

[3]

R. Canetti, Security and composition of multi-party cryptographic protocols. J. Cryptol. 13(1), 143-202 (2000).

Digital Library

[4]

R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in 42nd FOCS (2001), pp. 136-145. Full version available at http://eprint.iacr.org/2000/067.

[5]

R. Canetti, M. Fischlin, Universally composable commitments, in CRYPTO 2001. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 19-40.

[6]

L. Carter, M.N. Wegman, Universal classes of Hash functions. J. Comput. Syst. Sci. 18(2), 143-154 (1979).

[7]

R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of Witness hiding protocols, in CRYPTO'94. LNCS, vol. 839 (Springer, Berlin, 1994), pp. 174-187.

[8]

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

[9]

Y. Dodis, R. Gennaro, J. Hastad, H. Krawczyk, T. Rabin, Randomness extraction and key derivation using the CBC, cascade and HMAC modes, in CRYPTO 2004. LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 494-510.

[10]

Y. Dodis, V. Shoup, S. Walfish, Efficient constructions of composable commitments and zero-knowledge proofs, in CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 515-535.

[11]

S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts. Commun. ACM 28(6), 637-647 (1985).

Digital Library

[12]

J. Garay, P. MacKenzie, K. Yang. Strengthening zero-knowledge protocols using signatures, in EUROCRYPT 2003. LNCS, vol. 2656 (Springer, Berlin, 2003), pp. 177-194.

[13]

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

[14]

O. Goldreich, S. Micali, A. Wigderson, How to play any mental game--A completeness theorem for protocols with honest majority, in 19th STOC (1987), pp. 218-229. For details see [13, Chap. 7].

[15]

S. Goldwasser, L. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO'90. LNCS, vol. 537 (Spring, Berlin, 1990), pp. 77-93.

[16]

V. Goyal, P. Mohassel, A. Smith. Efficient two party and multi party computation against covert adversaries, in EUROCRYPT 2008. LNCS, vol. 4965 (Springer, Berlin, 2008), pp. 289-306.

Digital Library

[17]

R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edn. (Addison-Wesley, Reading, 1998).

[18]

J. Hastad, R. Impagliazzo, L. Levin, M. Luby, Construction of a pseudo-random generator from any one-way function. SIAM J. Comput. 28(4), 1364-1396 (1999).

Digital Library

[19]

C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols: Techniques and Constructions (Springer, Berlin, 2010).

[20]

C. Hazay, K. Nissim, Efficient set operations in the presence of malicious adversaries, in PKC 2010. LNCS, vol. 6056 (Springer, Berlin, 2010), pp. 312-331.

[21]

Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer--Efficiently, in CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 572-591.

[22]

Y. Ishai, M. Prabhakaran, A. Sahai, Secure arithmetic computation with no honest majority, in TCC 2009. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 294-314.

[23]

S. Jarecki, V. Shmatikov, Efficient two-party secure computation on committed inputs, in EUROCRYPT 2007. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 97-114.

[24]

M. Kiraz, B. Schoenmakers, A protocol issue for the malicious case of Yao's garbled circuit construction, in Proceedings of the 27th Symposium on Information Theory in the Benelux (2006), pp. 283-290.

[25]

V. Kolesnikov, T. Schneider, Improved garbled circuit: Free XOR gates and applications, in 35th ICALP. LNCS, vol. 5126 (Springer, Berlin, 2008), pp. 486-498.

[26]

Y. Lindell, Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16(3), 143-184 (2003).

[27]

Y. Lindell, Highly-efficient universally-composable commitments, in EUROCRYPT 2011. LNCS, vol. 6632 (Springer, Berlin, 2011), pp. 446-466.

[28]

Y. Lindell, B. Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, in EUROCRYPT 2007. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 52-78.

[29]

Y. Lindell, B. Pinkas, A proof of Yao's protocol for secure two-party computation. J. Cryptol. 22(2), 161-188 (2009).

Digital Library

[30]

P. MacKenzie, K. Yang, On simulation-sound trapdoor commitments, in EUROCRYPT 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 382-400.

[31]

A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 2001).

[32]

S. Micali, P. Rogaway, Secure computation. Unpublished manuscript, 1992. Preliminary version in CRYPTO'91, LNCS, vol. 576 (Springer, Berlin, 1991), pp. 392-404.

[33]

P. Mohassel, M.K. Franklin, Efficiency tradeoffs for malicious two-party computation, in 9th PKC Conference. LNCS, vol. 3958 (Springer, Berlin, 2006), pp. 458-473.

[34]

M. Naor, O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, in 36th FOCS (1995), pp. 170-181.

[35]

J.B. Nielsen, C. Orlandi, LEGO for two-party secure computation, in TCC 2009. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 368-386.

[36]

C. Orlandi, Personal communication, 2010.

[37]

C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in CRYPTO'08. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 554-571.

[38]

B. Pinkas, T. Schneider, N.P. Smart, S.C. Williams. Secure two-party computation is practical, in ASIACRYPT 2009. LNCS, vol. 5912 (Springer, Berlin, 2009), pp. 250-267.

[39]

M. Rabin, How to exchange secrets by oblivious transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981.

[40]

A. Shamir, How to share a secret. Commun. ACM 22(11), 612-613 (1979).

Digital Library

[41]

A.C. Yao, How to generate and exchange secrets, in 27th FOCS (1986), pp. 162-167.

Digital Library

Cited By

Jin CYin Cvan Dijk MDuan SMassacci FReiter MZhang HLuo BLiao XXu JKirda ELie D(2024)PG: Byzantine Fault-Tolerant and Privacy-Preserving Sensor Fusion with Guaranteed Output DeliveryProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670343(3272-3286)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670343
Liu KGupta TNiu JVaidya J(2024)Making Privacy-preserving Federated Graph Analytics Practical (for Certain Queries)Proceedings of the 29th ACM Symposium on Access Control Models and Technologies10.1145/3649158.3657047(31-39)Online publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1145/3649158.3657047
Pohle EAbidin APreneel B(2024)Fast Evaluation of S-Boxes With Garbled CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340214519(5530-5544)Online publication date: 16-May-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3402145
Show More Cited By

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

Recommendations

Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries

In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of ...
On Cut-and-Choose Oblivious Transfer and Its Variants
Proceedings, Part I, of the 21st International Conference on Advances in Cryptology -- ASIACRYPT 2015 - Volume 9452

Motivated by the recent progress in improving efficiency of secure computation, we study cut-and-choose oblivious transfer--a basic building block of state-of-the-art constant round two-party secure computation protocols that was introduced by Lindell ...
An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

We show an efficient secure two-party protocol, based on Yao's construction, which provides security against malicious adversaries. Yao's original protocol is only secure in the presence of semi-honest adversaries, and can be transformed into a protocol ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology

Journal of Cryptology Volume 25, Issue 4

October 2012

223 pages

ISSN:0933-2790

Issue’s Table of Contents

Copyright © Copyright © 2012 International Association for Cryptologic Research.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jin CYin Cvan Dijk MDuan SMassacci FReiter MZhang HLuo BLiao XXu JKirda ELie D(2024)PG: Byzantine Fault-Tolerant and Privacy-Preserving Sensor Fusion with Guaranteed Output DeliveryProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670343(3272-3286)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670343
Liu KGupta TNiu JVaidya J(2024)Making Privacy-preserving Federated Graph Analytics Practical (for Certain Queries)Proceedings of the 29th ACM Symposium on Access Control Models and Technologies10.1145/3649158.3657047(31-39)Online publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1145/3649158.3657047
Pohle EAbidin APreneel B(2024)Fast Evaluation of S-Boxes With Garbled CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340214519(5530-5544)Online publication date: 16-May-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3402145
Hazay CVenkitasubramaniam MWeiss M(2024)The Price of Active Security in Cryptographic ProtocolsJournal of Cryptology10.1007/s00145-024-09509-237:3Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1007/s00145-024-09509-2
Liu XYang GSusilo WHe KDeng RWeng J(2023)Privacy-Preserving Multi-User Outsourced Computation for Boolean CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.330173418(4929-4943)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3301734
Hazay CIshai YVenkitasubramaniam M(2023)Actively Secure Garbled Circuits with Constant Communication Overhead in the Plain ModelJournal of Cryptology10.1007/s00145-023-09465-336:3Online publication date: 8-Jun-2023
https://dl.acm.org/doi/10.1007/s00145-023-09465-3
Ning JTan Z(2023)Geometry-Based Garbled Circuits Relying Solely on One Evaluation Algorithm Under Standard AssumptionInformation Security and Cryptology10.1007/978-981-97-0942-7_10(183-202)Online publication date: 9-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-97-0942-7_10
Yadav VAndola NVerma SVenkatesan S(2022)A Survey of Oblivious Transfer ProtocolACM Computing Surveys10.1145/350304554:10s(1-37)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1145/3503045
Baum CDavid BDowsley R(2022)(Public) Verifiability for Composable Protocols Without Adaptivity or Zero-KnowledgeProvable and Practical Security10.1007/978-3-031-20917-8_17(249-272)Online publication date: 11-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20917-8_17
Ding HJiang HXu Q(2021)Postquantum Cut-and-Choose Oblivious Transfer Protocol Based on LWESecurity and Communication Networks10.1155/2021/99746042021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/9974604
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents