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

research-article

Open access

Grotto: Screaming fast (2+1)-PC or ℤ2n via (2,2)-DPFs

Authors:

Adithya Vadapalli,

Ryan HenryAuthors Info & Claims

CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

Pages 2143 - 2157

https://doi.org/10.1145/3576915.3623147

Published: 21 November 2023 Publication History

Abstract

We introduce Grotto, a framework and C++ library for space- and time-efficient (2+1)-party piecewise polynomial (i.e., spline) evaluation on secrets additively shared over ℤ2n. Grotto improves on the state-of-the-art approaches based on distributed comparison functions (DCFs) in almost every metric, offering asymptotically superior communication and computation costs with the same or lower round complexity. At the heart of Grotto is a novel observation about the structure of the ''tree'' representation underlying the most efficient distributed point functions (DPFs) from the literature, alongside an efficient algorithm that leverages this structure to do with a lightweight DPF what state-of-the-art approaches require comparatively heavyweight DCFs to do. Our open-source Grotto implementation supports dozens of useful functions out of the box, including trigonometric and hyperbolic functions with their inverses; various logarithms; roots, reciprocals, and reciprocal roots; sign testing and bit counting; and over two dozen of the most common univariate activation functions from the deep-learning literature.

References

[1]

Donald Beaver. Efficient multiparty protocols using circuit randomization. In Advances in Cryptology: Proceedings of CRYPTO 1991, volume 576 of LNCS, pages 420--432, Santa Barbara, CA, USA (August 1991).

[2]

John L. Bentley. Solution to Klee's rectangle problems. Technical Report (Unpublished), Carnegie-Mellon University, Pittsburgh, PA, USA, 1977.

[3]

Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathee. Function secret sharing for mixed-mode and fixed-point secure computation. In Advances in Cryptology: Proceedings of EUROCRYPT 2021 (Part II), volume 12697 of LNCS, pages 871--900, Zagreb, Croatia (October 2021).

Digital Library

[4]

Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing. In Advances in Cryptology: Proceedings of EUROCRYPT 2015 (Part II), volume 9057 of LNCS, pages 337--367, Sofia, Bulgaria (April 2015).

[5]

Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the circuit size barrier for secure computation under DDH. In Advances in Cryptology: Proceedings of CRYPTO 2016 (Part I), volume 9814 of LNCS, pages 509--539, Santa Barbara, CA, USA (August 2016).

Digital Library

[6]

Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In Proceedings of CCS 2016, pages 1292--1303, Vienna, Austria (October 2016).

Digital Library

[7]

Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In Proceedings of FOCS 1995, pages 41--50, Milwaukee, WI, USA (October 1995).

[8]

Henry Corrigan-Gibbs, Dan Boneh, and David Mazières. Riposte: An anonymous messaging system handling millions of users. In Proceedings of IEEE S&P 2015, pages 321--338, San Jose, CA, USA (May 2015).

Digital Library

[9]

Wenliang Du and Mikhail J. Atallah. Protocols for secure remote database access with approximate matching. In E-Commerce Security and Privacy (Part II), volume 2 of Advances in Information Security, pages 87--111, February 2001.

[10]

Saba Eskandarian, Henry Corrigan-Gibbs, Matei Zaharia, and Dan Boneh. Express: Lowering the cost of metadata-hiding communication with crypto-graphic privacy. In Proceedings of USENIX Security 2021, Vancouver, BC, Canada (August 2021).

[11]

Niv Gilboa and Yuval Ishai. Distributed point functions and their applications. In Advances in Cryptology: Proceedings of EUROCRYPT 2014, volume 8441 of LNCS, pages 640--658, Copenhagen, Denmark (May 2014).

[12]

Kanav Gupta, Deepak Kumaraswamy, Divya Gupta, and Nishanth Chandran. LLAMA: A low latency math library for secure inference. Proceedings on Privacy Enhancing Technologies (PoPETS), 2022(4):274--294, October 2022.

[13]

Ryan Henry, Chris Jiang, et al. libdpf [computer software]. Available from: https://github.com/DigitalLibertiesLab/libdpf.git, September 2023.

[14]

Zhicong Huang, Wen-jie Lu, Cheng Hong, and Jiansheng Ding. Cheetah: Lean and fast secure two-party deep neural network inference. In Proceedings of USENIX Security 2022, pages 809--826, Boston, MA, USA (August 2022).

[15]

Neha Jawalkar, Kanav Gupta, Arkaprava Basu, Nishanth Chandran, Divya Gupta, and Rahul Sharma. Orca: FSS-based Secure Training with GPUs. IACR Cryptology ePrint Archive, Report 2023/206, February 2023.

[16]

Payman Mohassel and Yupeng Zhang. SecureML: A system for scalable privacy-preserving machine learning. In Proceedings of IEEE S&P 2017, pages 19--38, San Jose, CA, USA (May 2017).

[17]

Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology: Proceedings of EUROCRYPT 1999, volume 1592 of LNCS, pages 223--238, Prague, Czech Republic (May 1999).

[18]

Arpite Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: Improved mixed-protocol secure two-party computation. In Proceedings of USENIX Security 2021, pages 2165--2182, Virtual event (August 2021).

[19]

Michael O. Rabin. How to exchange secrets with oblivious transfer. Technical Report TR-81, Aiken Computation Lab, Harvard University, Cambridge, MA, USA, May 1981.

[20]

Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi. SiRnn: A math library for secure RNN inference. In Proceedings of IEEE S&P 2021, pages 1003--1020, San Francisco, CA, USA (May 2021).

[21]

Théo Ryffel, Pierre Tholoniat, David Pointcheval, and Francis R. Bach. AriaNN: Low-interaction privacy-preserving deep learning via function secret sharing. Proceedings on Privacy Enhancing Technologies (PoPETS), 2022(1):291--316, January 2022.

[22]

Adi Shamir. How to share a secret. Communications of the ACM (CACM), 22(11):612--613, November 1979.

[23]

Kyle Storrier, Adithya Vadapalli, Alan Lyons, and Ryan Henry. Grotto: Screaming fast (2 1)-PC for ℤ2n via (2, 2)-DPFs. IACR Cryptology ePrint Archive, Report 2023/108, January 2023.

[24]

Adithya Vadapalli, Fattaneh Bayatbabolghani, and Ryan Henry. You may also like... Privacy: Recommendation systems meet PIR. Proceedings on Privacy Enhancing Technologies (PoPETS), 2021(4):30--53, October 2021.

[25]

Adithya Vadapalli, Kyle Storrier, and Ryan Henry. Sabre: Sender-anonymous messaging with fast audits. In Proceedings of IEEE S&P 2022, pages 1953--1970, San Francisco, CA, USA (May 2022).

[26]

Sameer Wagh. Pika: Secure computation using function secret sharing over rings. Proceedings on Privacy Enhancing Technologies (PoPETS), 2022(4):351--377, October 2022.

Cited By

Yang PJiang ZGao SWang HZhou JJin YYiu SFang J(2025)Communication-Efficient Secure Neural Network via Key-Reduced Distributed Comparison FunctionProvable and Practical Security10.1007/978-981-96-0957-4_8(143-163)Online publication date: 31-Jan-2025
https://doi.org/10.1007/978-981-96-0957-4_8
Breuer MMeyer UWetzel SQuek TGao DZhou JCardenas A(2024)Efficient Privacy-Preserving Approximation of the Kidney Exchange ProblemProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3645015(306-322)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3645015
Fu JCheng KSong AXia YChang ZShen Y(2024)FSS-DBSCAN: Outsourced Private Density-Based Clustering via Function Secret SharingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.344623319(7759-7773)Online publication date: 19-Aug-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3446233
Show More Cited By

Index Terms

Grotto: Screaming fast (2+1)-PC or ℤ2n via (2,2)-DPFs
1. Security and privacy

Recommendations

Digital Restoration of Seokguram Grotto: The Digital Archiving and the Exhibition of South Korea's Representative UNESCO World Heritage
ISUVR '12: Proceedings of the 2012 International Symposium on Ubiquitous Virtual Reality

The digitalization of Seokguram Grotto, a UNESCO World Heritage: KAIST GSCT produced a digitalized mapping of Seokguram Grotto, a UNESCO World Heritage and South Korea's representative cultural heritage, on two separate occasions in year 2008 and 2011. ...
Uniform approximation on [-1, 1] via discrete de la Vallée Poussin means

Starting from the function values on the roots of Jacobi polynomials, we construct a class of discrete de la Vallée Poussin means, by approximating the Fourier coefficients with a Gauss---Jacobi quadrature rule. Unlike the Lagrange interpolation ...
New spherical ( 2 s + 1 ) -designs from Kuperberg's set

In 2005, Kuperberg proved that 2 s points z 1 z 2 z s ' form a Chebyshev-type ( 2 s + 1 ) -quadrature formula on - 1 , 1 with constant weight if and only if the z i 's are the zeros of polynomial Q ( x ) = x s - x s - 1 3 + x s - 2 45 - + ( - 1 ) s 1 3 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

November 2023

3722 pages

ISBN:9798400700507

DOI:10.1145/3576915

General Chairs:
Weizhi Meng
Technical University of Denmark
,
Christian D. Jensen
Technical University of Denmark
,
Program Chairs:
Cas Cremers
CISPA Helmholtz Center for Information Security
,
Engin Kirda
Khoury College of Computer Sciences

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 November 2023

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS '23

Sponsor:

SIGSAC

CCS '23: ACM SIGSAC Conference on Computer and Communications Security

November 26 - 30, 2023

Copenhagen, Denmark

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
813
Total Downloads

Downloads (Last 12 months)704
Downloads (Last 6 weeks)91

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang PJiang ZGao SWang HZhou JJin YYiu SFang J(2025)Communication-Efficient Secure Neural Network via Key-Reduced Distributed Comparison FunctionProvable and Practical Security10.1007/978-981-96-0957-4_8(143-163)Online publication date: 31-Jan-2025
https://doi.org/10.1007/978-981-96-0957-4_8
Breuer MMeyer UWetzel SQuek TGao DZhou JCardenas A(2024)Efficient Privacy-Preserving Approximation of the Kidney Exchange ProblemProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3645015(306-322)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3645015
Fu JCheng KSong AXia YChang ZShen Y(2024)FSS-DBSCAN: Outsourced Private Density-Based Clustering via Function Secret SharingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.344623319(7759-7773)Online publication date: 19-Aug-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3446233
Fu JCheng KXia YSong ALi QShen Y(2024)Private Decision Tree Evaluation with Malicious Security via Function Secret SharingComputer Security – ESORICS 202410.1007/978-3-031-70890-9_16(310-330)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70890-9_16
Yang PJiang ZZhuang JFang JYiu SWang X(2024)FSSiBNN: FSS-Based Secure Binarized Neural Network Inference with Free Bitwidth ConversionComputer Security – ESORICS 202410.1007/978-3-031-70879-4_12(229-250)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70879-4_12
Dalskov AEscudero DNof A(2024)Fully Secure MPC and zk-FLIOP over Rings: New Constructions, Improvements and ExtensionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_5(136-169)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten