research-article

Distributed Vector-OLE: Improved Constructions and Implementation

Authors:

Phillipp Schoppmann,

Adrià Gascón,

Leonie Reichert,

Mariana RaykovaAuthors Info & Claims

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Pages 1055 - 1072

https://doi.org/10.1145/3319535.3363228

Published: 06 November 2019 Publication History

Abstract

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinear</>communication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme to obtain multi-point FSS. We show that this requirement can be relaxed, resulting in a weaker variant of FSS, for which we give an efficient protocol. This allows us to use efficient probabilistic batch codes that were also recently used for batched PIR by Angel et al. (S&P 2018). We construct a full Vector-OLE generator from our protocols, and compare it experimentally with alternative approaches. Our implementation parallelizes very well, and has low communication overhead in practice. For generating a VOLE of size $2^20 $, our implementation only takes $0.52$s on 32 cores.

Supplementary Material

WEBM File (p1055-schoppmann.webm)

Download
123.15 MB

References

[1]

Sebastian Angel, Hao Chen, Kim Laine, and Srinath T. V. Setty. 2018. PIR with Compressed Queries and Amortized Query Processing. In IEEE Symposium on Security and Privacy. IEEE, 962--979.

[2]

Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, and Lior Zichron. 2017. Secure Arithmetic Computation with Constant Computational Overhead. In CRYPTO (1). Springer, 223--254.

[3]

Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. 2013. More efficient oblivious transfer and extensions for faster secure computation. In CCS. ACM, 535--548.

[4]

Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. 2015. More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries. In EUROCRYPT (1). Springer, 673--701.

[5]

Donald Beaver. 1991. Efficient Multiparty Protocols Using Circuit Randomization. In CRYPTO. Springer, 420--432.

[6]

Donald Beaver. 1996. Correlated Pseudorandomness and the Complexity of Private Computations. In STOC. ACM, 479--488.

[7]

Avrim Blum, Adam Kalai, and Hal Wasserman. 2003. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, Vol. 50, 4 (2003), 506--519.

Digital Library

[8]

Dan Boneh, Kevin Lewi, and David J. Wu. 2017. Constraining Pseudorandom Functions Privately. In Public Key Cryptography (2). Springer, 494--524.

[9]

Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. 2018. Compressing Vector OLE. In CCS. ACM, 896--912.

[10]

Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. 2019. Efficient Pseudorandom Correlation Generators: Silent OT Extension and More. In CRYPTO (3). Springer, 489--518.

[11]

Elette Boyle, Niv Gilboa, and Yuval Ishai. 2015. Function Secret Sharing. In EUROCRYPT (2). Springer, 337--367.

[12]

Elette Boyle, Niv Gilboa, and Yuval Ishai. 2016. Function Secret Sharing: Improvements and Extensions. In CCS. ACM, 1292--1303.

[13]

Ran Canetti. 2000. Security and Composition of Multiparty Cryptographic Protocols. J. Cryptology, Vol. 13, 1 (2000), 143--202.

Digital Library

[14]

Hao Chen, Kim Laine, and Peter Rindal. 2017. Fast Private Set Intersection from Homomorphic Encryption. In CCS. ACM, 1243--1255.

[15]

Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. 1995. Private Information Retrieval. In FOCS. IEEE Computer Society, 41--50.

[16]

Leonardo Dagum and Ramesh Menon. 1998. OpenMP: An industry-standard API for shared-memory programming. Computing in Science & Engineering 1 (1998), 46--55.

Digital Library

[17]

Ivan Damgård, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. 2013. Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits. In ESORICS. Springer, 1--18.

[18]

Ivan Damgård and Sunoo Park. 2012. Is Public-Key Encryption Based on LPN Practical? IACR Cryptology ePrint Archive (2012), 699.

[19]

Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption. In CRYPTO. Springer, 643--662.

[20]

Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. 2018. PIR-PSI: Scaling Private Contact Discovery. PoPETs, Vol. 2018, 4 (2018), 159--178.

[21]

Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In NDSS. The Internet Society.

[22]

Jack Doerner and abhi shelat. 2017. Scaling ORAM for Secure Computation. In CCS. ACM, 523--535.

[23]

Nico Dö ttling, Satrajit Ghosh, Jesper Buus Nielsen, Tobias Nilges, and Roberto Trifiletti. 2017. TinyOLE: Efficient Actively Secure Two-Party Computation from Oblivious Linear Function Evaluation. In CCS. ACM, 2263--2276.

[24]

Nico Dö ttling, Daniel Kraschewski, and Jö rn Mü ller-Quade. 2012. David & Goliath Oblivious Affine Function Evaluation - Asymptotically Optimal Building Blocks for Universally Composable Two-Party Computation from a Single Untrusted Stateful Tamper-Proof Hardware Token. IACR Cryptology ePrint Archive (2012), 135.

[25]

Michael J. Freedman, Carmit Hazay, Kobbi Nissim, and Benny Pinkas. 2016. Efficient Set Intersection with Simulation-Based Security. J. Cryptology, Vol. 29, 1 (2016), 115--155.

Digital Library

[26]

Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. 2005. Keyword Search and Oblivious Pseudorandom Functions. In TCC. Springer, 303--324.

[27]

Adrià Gascó n, Phillipp Schoppmann, Borja Balle, Mariana Raykova, Jack Doerner, Samee Zahur, and David Evans. 2017. Privacy-Preserving Distributed Linear Regression on High-Dimensional Data. PoPETs, Vol. 2017, 4 (2017), 345--364.

[28]

Satrajit Ghosh and Tobias Nilges. 2019. An Algebraic Approach to Maliciously Secure Private Set Intersection. In EUROCRYPT (3). Springer, 154--185.

[29]

Niv Gilboa. [n. d.]. Private Communication.

[30]

Niv Gilboa. 1999. Two Party RSA Key Generation. In CRYPTO. Springer, 116--129.

[31]

Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1986. How to construct random functions. J. ACM, Vol. 33, 4 (1986), 792--807.

Digital Library

[32]

Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.

[33]

Stefan Heyse, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof Pietrzak. 2012. Lapin: An Efficient Authentication Protocol Based on Ring-LPN. In FSE. Springer, 346--365.

[34]

Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. 2003. Extending Oblivious Transfers Efficiently. In CRYPTO. Springer, 145--161.

[35]

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. 2004. Batch codes and their applications. In STOC. ACM, 262--271.

[36]

Jonathan Katz and Yehuda Lindell. 2014. Introduction to Modern Cryptography 2 ed.). Chapman and Hall/CRC Press.

[37]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. In CCS. ACM, 830--842.

[38]

Marcel Keller, Valerio Pastro, and Dragos Rotaru. 2018. Overdrive: Making SPDZ Great Again. In EUROCRYPT (3). Springer, 158--189.

[39]

Joe Kilian. 1988. Founding Cryptography on Oblivious Transfer. In STOC. ACM, 20--31.

[40]

Adam Kirsch, Michael Mitzenmacher, and Udi Wieder. 2009. More Robust Hashing: Cuckoo Hashing with a Stash. SIAM J. Comput., Vol. 39, 4 (2009), 1543--1561.

Digital Library

[41]

Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. 2016. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. In CCS. 818--829.

[42]

Yehuda Lindell and Benny Pinkas. 2009. A Proof of Security of Yao's Protocol for Two-Party Computation. J. Cryptology, Vol. 22, 2 (2009), 161--188.

Digital Library

[43]

Payman Mohassel and Yupeng Zhang. 2017. SecureML: A System for Scalable Privacy-Preserving Machine Learning. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 19--38.

[44]

Moni Naor and Benny Pinkas. 1999. Oblivious Transfer and Polynomial Evaluation. In STOC. ACM, 245--254.

[45]

Moni Naor and Benny Pinkas. 2006. Oblivious Polynomial Evaluation. SIAM J. Comput., Vol. 35, 5 (2006), 1254--1281.

Digital Library

[46]

Rasmus Pagh and Flemming Friche Rodler. 2004. Cuckoo hashing. J. Algorithms, Vol. 51, 2 (2004), 122--144.

Digital Library

[47]

Benny Pinkas, Thomas Schneider, and Michael Zohner. 2014. Faster Private Set Intersection Based on OT Extension. In USENIX Security Symposium. USENIX Association, 797--812.

[48]

Benny Pinkas, Thomas Schneider, and Michael Zohner. 2018. Scalable Private Set Intersection Based on OT Extension. ACM Trans. Priv. Secur., Vol. 21, 2 (2018).

Digital Library

[49]

Michael O. Rabin. 1981. How To Exchange Secrets with Oblivious Transfer. TR-81 edition, Aiken Computation Lab, Harvard University (1981).

[50]

Phillipp Schoppmann, Adrià Gascó n, Mariana Raykova, and Benny Pinkas. 2019. Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning. In CCS. ACM.

[51]

Victor Shoup et al. 2001. NTL: A library for doing number theory. https://www.shoup.net/ntl.

[52]

Abraham Waksman. 1968. A Permutation Network. J. ACM, Vol. 15, 1 (1968), 159--163.

Digital Library

[53]

Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. 2016. EMP-toolkit: Efficient MultiParty computation toolkit. https://github.com/emp-toolkit.

[54]

Robert S. Winternitz. 1984. A Secure One-Way Hash Function Built from DES. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 88--90.

[55]

Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract). In FOCS. IEEE Computer Society, 162--167.

Cited By

Tan WDu SWeng J(2024)Enhancing Efficiency and Security in Unbalanced PSI-CA Protocols through Cloud Computing and Homomorphic Encryption in Mobile NetworksFuture Internet10.3390/fi1606020516:6(205)Online publication date: 7-Jun-2024
https://doi.org/10.3390/fi16060205
Tang YGuo MHuo YZhao ZYu JQin B(2024)An MLWE-Based Cut-and-Choose Oblivious Transfer ProtocolEntropy10.3390/e2609079326:9(793)Online publication date: 16-Sep-2024
https://doi.org/10.3390/e26090793
Wu DLiang BLu ZDing J(2024)Efficient Secure Multi-party Computation for Multi-dimensional Arithmetics and Its Application in Privacy-Preserving Biometric IdentificationCryptology and Network Security10.1007/978-981-97-8013-6_1(3-25)Online publication date: 2-Oct-2024
https://doi.org/10.1007/978-981-97-8013-6_1
Show More Cited By

Index Terms

Distributed Vector-OLE: Improved Constructions and Implementation
1. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic protocols

Recommendations

Compressing Vector OLE
CCS '18: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic ...
What Security Can We Achieve Within 4 Rounds?
Abstract
Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, ...
Black-Box Constructions of Protocols for Secure Computation

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

November 2019

2755 pages

ISBN:9781450367479

DOI:10.1145/3319535

General Chairs:
Lorenzo Cavallaro
King's College London, UK
,
Johannes Kinder
Bundeswehr University Munich, Germany
,
Program Chairs:
XiaoFeng Wang
Indiana University, USA
,
Jonathan Katz
George Mason University, USA

Copyright © 2019 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 the author(s) 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: 06 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Engineering and Physical Sciences Research Council

Conference

CCS '19

Sponsor:

SIGSAC

CCS '19: 2019 ACM SIGSAC Conference on Computer and Communications Security

November 11 - 15, 2019

London, United Kingdom

Acceptance Rates

CCS '19 Paper Acceptance Rate 149 of 934 submissions, 16%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '24

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
658
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)7

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan WDu SWeng J(2024)Enhancing Efficiency and Security in Unbalanced PSI-CA Protocols through Cloud Computing and Homomorphic Encryption in Mobile NetworksFuture Internet10.3390/fi1606020516:6(205)Online publication date: 7-Jun-2024
https://doi.org/10.3390/fi16060205
Tang YGuo MHuo YZhao ZYu JQin B(2024)An MLWE-Based Cut-and-Choose Oblivious Transfer ProtocolEntropy10.3390/e2609079326:9(793)Online publication date: 16-Sep-2024
https://doi.org/10.3390/e26090793
Wu DLiang BLu ZDing J(2024)Efficient Secure Multi-party Computation for Multi-dimensional Arithmetics and Its Application in Privacy-Preserving Biometric IdentificationCryptology and Network Security10.1007/978-981-97-8013-6_1(3-25)Online publication date: 2-Oct-2024
https://doi.org/10.1007/978-981-97-8013-6_1
Agarwal ABoyle EGilboa NIshai YKelkar MMa Y(2024)Compressing Unit-Vector Correlations via Sparse Pseudorandom GeneratorsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_11(346-383)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68397-8_11
Liu HWang XYang KYu Y(2024)The Hardness of LPN over Any Integer Ring and Field for PCG ApplicationsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_6(149-179)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_6
Jiang ZGuo XYu TZhou HWen JWu Z(2023)Private Set Intersection Based on Lightweight Oblivious Key-Value Storage StructureSymmetry10.3390/sym1511208315:11(2083)Online publication date: 18-Nov-2023
https://doi.org/10.3390/sym15112083
HUO WYU YYANG KZHENG ZLI XYAO LXIE J(2023)Privacy-preserving cryptographic algorithms and protocols: a survey on designs and applicationsSCIENTIA SINICA Informationis10.1360/SSI-2022-043453:9(1688)Online publication date: 6-Sep-2023
https://doi.org/10.1360/SSI-2022-0434
Guo CWang XXie XYu Y(2023)The Multi-User Constrained Pseudorandom Function Security of Generalized GGM Trees for MPC and Hierarchical WalletsACM Transactions on Privacy and Security10.1145/359260826:3(1-38)Online publication date: 14-Apr-2023
https://dl.acm.org/doi/10.1145/3592608
Yang YHeath DHazay CKolesnikov VVenkitasubramaniam MMeng WJensen CCremers CKirda E(2023)Batchman and Robin: Batched and Non-batched Branching for Interactive ZKProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623169(1452-1466)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623169
Braun LPancholi MRachuri RSimkin MMeng WJensen CCremers CKirda E(2023)Ramen: Souper Fast Three-Party Computation for RAM ProgramsProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623115(3284-3297)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623115
Show More Cited By

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents