research-article

More efficient oblivious transfer and extensions for faster secure computation

Authors:

Yehuda Lindell,

Thomas Schneider,

Michael ZohnerAuthors Info & Claims

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

Pages 535 - 548

https://doi.org/10.1145/2508859.2516738

Published: 04 November 2013 Publication History

Abstract

Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography.

In this work we present optimizations and efficient implementations of OT and OT extensions in the semi-honest model. We propose a novel OT protocol with security in the standard model and improve OT extensions with respect to communication complexity, computation complexity, and scalability. We also provide specific optimizations of OT extensions that are tailored to the secure computation protocols of Yao and Goldreich-Micali-Wigderson and reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations. By applying our implementation to current secure computation frameworks, we can securely compute a Levenshtein distance circuit with 1.29 billion AND gates at a rate of 1.2 million AND gates per second. Moreover, we demonstrate the importance of correctly implementing OT within secure computation protocols by presenting an attack on the FastGC framework.

References

[1]

D. Beaver. Efficient multiparty protocols using circuit randomization. In Advances in Cryptology -- CRYPTO'91, volume 576 of LNCS, pages 420--432. Springer, 1991.

Digital Library

[2]

D. Beaver. Correlated pseudorandomness and the complexity of private computations. In Symposium on Theory of Computing (STOC'96), pages 479--488. ACM, 1996.

Digital Library

[3]

M. Bellare, S. Goldwasser, and D. Micciancio. "pseudo-random" number generation within cryptographic algorithms: The DDS case. In Advances in Cryptology -- CRYPTO'97, volume 1294 of LNCS, pages 277--291. Springer, 1997.

Digital Library

[4]

M. Bellare, V. Hoang, S. Keelveedhi, and P. Rogaway. Efficient garbling from a fixed-key blockcipher. In Symposium on Security and Privacy, pages 478--492. IEEE, 2013.

Digital Library

[5]

A. Ben-David, N. Nisan, and B. Pinkas. FairplayMP: a system for secure multi-party computation. In Computer and Communications Security (CCS'08), pages 257--266. ACM, 2008.

Digital Library

[6]

J. Boyar and R. Peralta. The exact multiplicative complexity of the Hamming weight function. Electronic Colloquium on Computational Complexity (ECCC'05), (049), 2005.

[7]

R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143--202, 2000.

Digital Library

[8]

S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces. In Cryptographers' Track at the RSA Conference (CT-RSA'12), volume 7178 of LNCS, pages 416--432. Springer, 2012.

Digital Library

[9]

E. De Cristofaro and G. Tsudik. Practical private set intersection protocols with linear complexity. In Financial Cryptography and Data Security (FC'10), volume 6052 of LNCS, pages 143--159. Springer, 2010.

Digital Library

[10]

J. O. Eklundh. A fast computer method for matrix transposing. IEEE Transactions on Computers, C-21(7):801--803, 1972.

Digital Library

[11]

Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, and T. Toft. Privacy-preserving face recognition. In Privacy Enhancing Technologies Symposium (PETS'09), volume 5672 of LNCS, pages 235--253. Springer, 2009.

Digital Library

[12]

S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communmunications of the ACM, 28(6):637--647, 1985.

Digital Library

[13]

K. Frikken, M. Atallah, and C. Zhang. Privacy-preserving credit checking. In Electronic Commerce (EC'05), pages 147--154. ACM, 2005.

Digital Library

[14]

O. Goldreich. Foundations of Cryptography, volume 2: Basic Applications. Cambridge University Press, 2004.

Digital Library

[15]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Symposium on Theory of Computing (STOC'87), pages 218--229. ACM, 1987.

Digital Library

[16]

S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis. Secure two-party computation in sublinear (amortized) time. In Computer and Communications Security (CCS'12), pages 513--524. ACM, 2012.

Digital Library

[17]

D. Harnik, Y. Ishai, E. Kushilevitz, and J. B. Nielsen. OT-combiners via secure computation. In Theory of Cryptography (TCC'08), volume 4948 of LNCS, pages 393--411. Springer, 2008.

Digital Library

[18]

J. Håstad and A. Shamir. The cryptographic security of truncated linearly related variables. In Symposium on Theory of Computing (STOC'85), pages 356--362. ACM, 1985.

Digital Library

[19]

W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In Computer and Communications Security (CCS'10), pages 451--462. ACM, 2010.

Digital Library

[20]

W. Henecka and T. Schneider. Faster secure two-party computation with less memory. In ACM Symposium on Information, Computer and Communications Security (ASIACCS'13), pages 437--446. ACM, 2013.

Digital Library

[21]

A. Holzer, M. Franz, S. Katzenbeisser, and H. Veith. Secure two-party computations in ANSI C. In Computer and Communications Security (CCS'12), pages 772--783. ACM, 2012.

Digital Library

[22]

Y. Huang, P. Chapman, and D. Evans. Privacy-preserving applications on smartphones. In Hot topics in security (HotSec'11). USENIX, 2011.

Digital Library

[23]

Y. Huang, D. Evans, and J. Katz. Private set intersection: Are garbled circuits better than custom protocols? In Network and Distributed Security Symposium (NDSS'12). The Internet Society, 2012.

[24]

Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In Security Symposium. USENIX, 2011.

Digital Library

[25]

Y. Huang, J. Katz, and D. Evans. Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution. In Symposium on Security and Privacy, pages 272--284. IEEE, 2012.

Digital Library

[26]

Y. Huang, L. Malka, D. Evans, and J. Katz. Efficient privacy-preserving biometric identification. In Network and Distributed Security Symposium (NDSS'11). The Internet Society, 2011.

[27]

Intelligence Advanced Research Projects Activity (IARPA). Security and Privacy Assurance Research (SPAR) Program, 2010.

[28]

Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In Advances in Cryptology -- CRYPTO'03, volume 2729 of LNCS, pages 145--161. Springer, 2003.

[29]

A. Jarrous and B. Pinkas. Secure hamming distance based computation and its applications. In Applied Cryptography and Network Security (ACNS'09), volume 5536 of LNCS, pages 107--124. Springer, 2009.

Digital Library

[30]

F. Kerschbaum. Automatically optimizing secure computation. In Computer and Communications Security (CCS'11), pages 703--714. ACM, 2011.

Digital Library

[31]

V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In Cryptology And Network Security (CANS'09), volume 5888 of LNCS, pages 1--20. Springer, 2009.

Digital Library

[32]

V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR gates and applications. In International Colloquium on Automata, Languages and Programming (ICALP'08), volume 5126 of LNCS, pages 486--498. Springer, 2008.

Digital Library

[33]

H. Krawczyk. Cryptographic extraction and key derivation: The HKDF scheme. In Advances in Cryptology -- CRYPTO'10, volume 6223 of LNCS, pages 631--648. Springer, 2010.

Digital Library

[34]

B. Kreuter, A. Shelat, and C.-H. Shen. Billion-gate secure computation with malicious adversaries. In Security Symposium. USENIX, 2012.

Digital Library

[35]

P. MacKenzie, A. Oprea, and M. K. Reiter. Automatic generation of two-party computations. In Computer and Communications Security (CCS'03), pages 210--219. ACM, 2003.

Digital Library

[36]

L. Malka. VMCrypt - modular software architecture for scalable secure computation. In Computer and Communications Security (CCS'11), pages 715--724. ACM, 2011.

Digital Library

[37]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay -- a secure two-party computation system. In Security Symposium, pages 287--302. USENIX, 2004.

Digital Library

[38]

A. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

Digital Library

[39]

S. Nagaraja, P. Mittal, C.-Y. Hong, M. Caesar, and N. Borisov. Botgrep: Finding P2P bots with structured graph analysis. In Security Symposium, pages 95--110. USENIX, 2010.

Digital Library

[40]

M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In ACM-SIAM Symposium On Discrete Algorithms, SODA'01, pages 448--457. Society for Industrial and Applied Mathematics, 2001.

Digital Library

[41]

A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh. Location privacy via private proximity testing. In Network and Distributed Security Symposium (NDSS'11). The Internet Society, 2011.

[42]

J. B. Nielsen. Extending oblivious transfers efficiently - how to get robustness almost for free. Cryptology ePrint Archive, Report 2007/215, 2007.

[43]

J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra. A new approach to practical active-secure two-party computation. In Advances in Cryptology -- CRYPTO'12, volume 7417 of LNCS, pages 681--700. Springer, 2012.

[44]

V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. Privacy-preserving ridge regression on hundreds of millions of records. In Symposium on Security and Privacy, pages 334--348. IEEE, 2013.

Digital Library

[45]

NIST. NIST Special Publication 800--57, Recommendation for Key Management Part 1: General (Rev. 3). Technical report, 2012.

[46]

M. Osadchy, B. Pinkas, A. Jarrous, and B. Moskovich. SCiFI - a system for secure face identification. In Symposium on Security and Privacy, pages 239--254. IEEE, 2010.

Digital Library

[47]

B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. Secure two-party computation is practical. In Advances in Cryptology -- ASIACRYPT'09, volume 5912 of LNCS, pages 250--267. Springer, 2009.

Digital Library

[48]

M. O. Rabin. How to exchange secrets with oblivious transfer, TR-81 edition, 1981. Aiken Computation Lab, Harvard University.

[49]

T. Schneider and M. Zohner. GMW vs. Yao -- Efficient secure two-party computation with low depth circuits. In Financial Cryptography and Data Security (FC'13), LNCS. Springer, 2013.

[50]

A. Schröpfer and F. Kerschbaum. Demo: secure computation in JavaScript. In Computer and Communications Security (CCS'11), pages 849--852. ACM, 2011.

Digital Library

[51]

A. C. Yao. How to generate and exchange secrets. In Foundations of Computer Science (FOCS'86), pages 162--167. IEEE, 1986.

Digital Library

Cited By

Feng JWu YSun HZhang SLiu D(2025)Panther: Practical Secure Two-Party Neural Network InferenceIEEE Transactions on Information Forensics and Security10.1109/TIFS.2025.352606320(1149-1162)Online publication date: 2025
https://doi.org/10.1109/TIFS.2025.3526063
Pang ZWang LYu FZhao KZeng BXu S(2025)PrivCore: Multiplication-activation co-reduction for efficient private inferenceNeural Networks10.1016/j.neunet.2025.107307187(107307)Online publication date: Jul-2025
https://doi.org/10.1016/j.neunet.2025.107307
Ren ZFan MWang ZZhang JZeng CHuang ZHong CChen KBalzarotti DXu W(2024)Accelerating secure collaborative machine learning with protocol-aware RDMAProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699026(2245-2261)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699026
Show More Cited By

Index Terms

More efficient oblivious transfer and extensions for faster secure computation
1. Theory of computation
  1. Models of computation

Recommendations

More Efficient Oblivious Transfer Extensions

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT ...
Improvements to Secure Computation with Penalties
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

Motivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty ...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

November 2013

1530 pages

ISBN:9781450324779

DOI:10.1145/2508859

General Chair:
Ahmad-Reza Sadeghi
TU Darmstadt, CASED, Intel ICRI-SC, Germany
,
Program Chairs:
Virgil Gligor
Carnegie Mellon University, USA
,
Moti Yung
Columbia University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'13

Sponsor:

SIGSAC

CCS'13: 2013 ACM SIGSAC Conference on Computer and Communications Security

November 4 - 8, 2013

Berlin, Germany

Acceptance Rates

CCS '13 Paper Acceptance Rate 105 of 530 submissions, 20%;

Overall Acceptance Rate 1,242 of 6,940 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

282
Total Citations
View Citations
1,597
Total Downloads

Downloads (Last 12 months)125
Downloads (Last 6 weeks)14

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Feng JWu YSun HZhang SLiu D(2025)Panther: Practical Secure Two-Party Neural Network InferenceIEEE Transactions on Information Forensics and Security10.1109/TIFS.2025.352606320(1149-1162)Online publication date: 2025
https://doi.org/10.1109/TIFS.2025.3526063
Pang ZWang LYu FZhao KZeng BXu S(2025)PrivCore: Multiplication-activation co-reduction for efficient private inferenceNeural Networks10.1016/j.neunet.2025.107307187(107307)Online publication date: Jul-2025
https://doi.org/10.1016/j.neunet.2025.107307
Ren ZFan MWang ZZhang JZeng CHuang ZHong CChen KBalzarotti DXu W(2024)Accelerating secure collaborative machine learning with protocol-aware RDMAProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699026(2245-2261)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699026
Zhao SZhao CHuang YSong XXu Q(2024)Two-Party Threshold Private Set Intersection Protocols from Lightweight Cryptographic PrimitivesCryptography10.3390/cryptography80400588:4(58)Online publication date: 22-Dec-2024
https://doi.org/10.3390/cryptography8040058
Allaart CAmiri SBal HBelloum AGommans Lvan Halteren AKlous S(2024)Private and Secure Distributed Deep Learning: A SurveyACM Computing Surveys10.1145/370345257:4(1-43)Online publication date: 15-Nov-2024
https://dl.acm.org/doi/10.1145/3703452
Xue JZhang YWang YWang XZheng HLou QLi BXu WChen JZhang YXue JWang SBai GYuan X(2024)CryptoTrain: Fast Secure Training on Encrypted DatasetProceedings of the 1st ACM Workshop on Large AI Systems and Models with Privacy and Safety Analysis10.1145/3689217.3690617(97-104)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3689217.3690617
Gunasinghe HAtallah MBertino E(2024)PEBASI: A Privacy preserving, Efficient Biometric Authentication Scheme based on IrisesACM Transactions on Privacy and Security10.1145/3677017Online publication date: 11-Jul-2024
https://doi.org/10.1145/3677017
Zhang CChen YLiu WPeng LHao MWang AWang XLuo BLiao XXu JKirda ELie D(2024)Unbalanced Private Set Union with Reduced Computation and CommunicationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690308(1434-1447)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690308
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
Blanton MMurphy DVilela JSchulmann HLi N(2024)Privacy Preserving Biometric Authentication for Fingerprints and BeyondProceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy10.1145/3626232.3653269(367-378)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3626232.3653269
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten