[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3474366.3486928acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
research-article
Open access

Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors

Published: 15 November 2021 Publication History

Abstract

Oblivious linear evaluation (OLE) is a fundamental building block in multi-party computation protocols. In OLE, a sender holds a description of an affine function $f_α,β (z)=α z+β$, the receiver holds an input x, and gets α x+β$ (where all computations are done over some field, or more generally, a ring). Vector OLE (VOLE) is a generalization where the sender has many affine functions and the receiver learns the evaluation of all of these functions on a single point x. The state-of-the-art semi-honest VOLE protocols generally fall into two groups. The first group relies on standard assumptions to achieve security but lacks in concrete efficiency. These constructions are mostly based on additively homomorphic encryption (AHE) and are classified as "folklore". The second group relies on less standard assumptions, usually properties of sparse, random linear codes, but they manage to achieve concrete practical efficiency. In this work, we present a conceptually simple VOLE protocol that derives its security from a standard assumption, namely Ring Learning with Errors (RLWE), while still achieving concrete efficiency comparable to the fastest VOLE protocols from non-standard coding assumptions~\citeADI+17, BCGI18, SGRR19. Furthermore, our protocol admits a natural extension to batch OLE (BOLE), which is yet another variant of OLE that computes many OLEs in parallel.

References

[1]
Carlos Aguilar-Melchor, Joris Barrier, Serge Guelton, Adrien Guinet, Marc-Olivier Killijian, and Tancrède Lepoint. 2016. NFLlib: NTT-Based Fast Lattice Library. In Topics in Cryptology - CT-RSA 2016, Kazue Sako (Ed.). Springer International Publishing, Cham, 341--356.
[2]
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. 2018. Homomorphic Encryption Security Standard. Technical Report. HomomorphicEncryption.org, Toronto, Canada.
[3]
Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, and Lior Zichron. 2017. Secure Arithmetic Computation with Constant Computational Overhead. In Advances in Cryptology -- CRYPTO 2017, Jonathan Katz and Hovav Shacham (Eds.). Springer International Publishing, Cham, 223--254.
[4]
Abhishek Banerjee, Chris Peikert, and Alon Rosen. 2012. Pseudorandom Functions and Lattices. In Advances in Cryptology -- EUROCRYPT 2012, David Pointcheval and Thomas Johansson (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 719--737.
[5]
Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, and Juan Ramón Troncoso-Pastoriza. 2020. Efficient Protocols for Oblivious Linear Function Evaluation from Ring-LWE. In Security and Cryptography for Networks, Clemente Galdi and Vladimir Kolesnikov (Eds.). Springer International Publishing, Cham, 130--149.
[6]
Avrim Blum, Adam Tauman Kalai, and Hal Wasserman. 2003. Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. Journal of the ACM (JACM) 50, 4 (July 2003), 506--519. https://www.microsoft.com/en-us/research/ publication/noise-tolerant-learning-parity-problem-statistical-query-model/
[7]
Florian Bourse, Rafaël Del Pino, Michele Minelli, and Hoeteck Wee. 2016. FHE Circuit Privacy Almost for Free. In Advances in Cryptology -- CRYPTO 2016, Matthew Robshaw and Jonathan Katz (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 62--89.
[8]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. 2018. Compressing Vector OLE. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (Toronto, Canada) (CCS '18). Association for Computing Machinery, New York, NY, USA, 896--912. https://doi.org/10.1145/3243734. 3243868
[9]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. 2019. Efficient Two-Round OT Extension and Silent Non- Interactive Secure Computation. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (London, United Kingdom) (CCS '19). Association for Computing Machinery, New York, NY, USA, 291--308. https://doi.org/10.1145/3319535.3354255
[10]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. 2020. Efficient Pseudorandom Correlation Generators from Ring-LPN. In Advances in Cryptology -- CRYPTO 2020, Daniele Micciancio and Thomas Ristenpart (Eds.). Springer International Publishing, Cham, 387--416.
[11]
Zvika Brakerski. 2012. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Proceedings of Advances in Cryptology-Crypto 7417 (08 2012). https://doi.org/10.1007/978--3--642--32009--5_50
[12]
Zvika Brakerski and Vinod Vaikuntanathan. 2011. Efficient Fully Homomorphic Encryption from (Standard) LWE. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22--25, 2011, Rafail Ostrovsky (Ed.). IEEE Computer Society, 97--106. https://doi.org/10.1109/FOCS. 2011.12
[13]
Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski, Tianren Liu, Rafail Ostrovsky, and Vinod Vaikuntanathan. 2019. Reusable Non-Interactive Secure Computation. In Advances in Cryptology -- CRYPTO 2019, Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer International Publishing, Cham, 462--488.
[14]
Leo de Castro, Chiraag Juvekar, and Vinod Vaikuntanathan. 2020. Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors. Cryptology ePrint Archive, Report 2020/685. https://ia.cr/2020/685.
[15]
Léo Ducas and Damien Stehlé. 2016. Sanitization of FHE Ciphertexts. In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8- 12, 2016, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 9665), Marc Fischlin and Jean-Sébastien Coron (Eds.). Springer, 294--310. https://doi.org/10. 1007/978--3--662--49890--3_12
[16]
Nagarjun Dwarakanath and Steven Galbraith. 2014. Sampling from discrete Gaussians for lattice-based cryptography on a constrained device. Applicable Algebra in Engineering, Communication and Computing 25 (06 2014). https: //doi.org/10.1007/s00200-014-0218--3
[17]
Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. https://eprint.iacr.org/2012/144.pdf
[18]
Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. STOC.
[19]
Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15--19, 2010. Proceedings (Lecture Notes in Computer Science, Vol. 6223), Tal Rabin (Ed.). Springer, 155--172. https://doi.org/10.1007/978--3--642--14623--7_9
[20]
Shai Halevi, Yuriy Polyakov, and Victor Shoup. 2019. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In Topics in Cryptology -- CT-RSA 2019 - The Cryptographers' Track at the RSA Conference 2019, Proceedings (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)), Mitsuru Matsui (Ed.). Springer-Verlag, 83--105. https://doi.org/10.1007/978--3-030--12612--4_5
[21]
Carmit Hazay, Yuval Ishai, Antonio Marcedone, and Muthuramakrishnan Venkitasubramaniam. 2019. LevioSA: Lightweight Secure Arithmetic Computation. In Proceedings of the 2019 ACMSIGSAC Conference on Computer and Communications Security (London, United Kingdom) (CCS '19). Association for Computing Machinery, New York, NY, USA, 327--344. https://doi.org/10.1145/3319535.3354258
[22]
Yuval Ishai and Anat Paskin. 2007. Evaluating Branching Programs on Encrypted Data. In Theory of Cryptography, Salil P. Vadhan (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 575--594.
[23]
Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2008. Founding Cryptography on Oblivious Transfer -- Efficiently. 572--591. https://doi.org/10.1007/978--3--540- 85174--5_32
[24]
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. 2018. GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In 27th USENIX Security Symposium (USENIX Security 18). USENIX Association, Baltimore, MD, 1651--1669. https://www.usenix.org/conference/usenixsecurity18/ presentation/juvekar
[25]
Kim Laine. 2019. https://github.com/microsoft/SEAL/issues/89.
[26]
Vadim Lyubashevsky and Daniele Micciancio. 2006. Generalized Compact Knapsacks Are Collision Resistant. In Automata, Languages and Programming, Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 144--155.
[27]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices and Learning with Errors Over Rings. EUROCRYPT (2010).
[28]
Moni Naor and Benny Pinkas. 2006. Oblivious Polynomial Evaluation. SIAM J. Comput. 35 (01 2006), 1254--1281. https://doi.org/10.1137/S0097539704383633
[29]
Zhiniang Peng. 2019. Danger of using fully homomorphic encryption: A look at Microsoft SEAL. CoRR abs/1906.07127 (2019). arXiv:1906.07127 http://arxiv.org/ abs/1906.07127
[30]
Y. Polyakov, K. Rohloff, and G.W Ryan. [n.d.]. PALISADE lattice cryptography library. https://git.njit.edu/palisade/PALISADE.
[31]
Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova. 2019. Distributed Vector-OLE: Improved Constructions and Implementation. https://doi.org/10.1145/3319535.3363228
[32]
SEAL 2020. Microsoft SEAL (release 3.5). https://github.com/Microsoft/SEAL. Microsoft Research, Redmond, WA.
[33]
Victor Shoup. [n.d.]. NTL: A Library for doing Number Theory. https://shoup. net/ntl/.
[34]
C. Weng, K. Yang, J. Katz, and X. Wang. 2021. Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits. In 2021 2021 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, Los Alamitos, CA, USA, 1074--1091. https://doi.org/10.1109/SP40001. 2021.00056
[35]
Adam Yala, Constance Lehman, Tal Schuster, Tally Portnoi, and Regina Barzilay. 2019. A Deep Learning Mammography-based Model for Improved Breast Cancer Risk Prediction. Radiology 292 (05 2019), 182716. https://doi.org/10.1148/radiol. 2019182716

Cited By

View all
  • (2024)1-Out-of-N Oblivious Transfer from MLWECryptology and Network Security10.1007/978-981-97-8013-6_6(123-143)Online publication date: 24-Sep-2024
  • (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
  • (2023)Scalable and Privacy-Preserving Federated Principal Component Analysis2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179350(1908-1925)Online publication date: May-2023
  • Show More Cited By

Index Terms

  1. Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    WAHC '21: Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography
    November 2021
    75 pages
    ISBN:9781450386562
    DOI:10.1145/3474366
    This work is licensed under a Creative Commons Attribution International 4.0 License.

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 15 November 2021

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. batch ole
    2. oblivious linear evaluation
    3. ring learning with errors
    4. vector ole

    Qualifiers

    • Research-article

    Conference

    CCS '21
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 6 of 17 submissions, 35%

    Upcoming Conference

    CCS '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)302
    • Downloads (Last 6 weeks)46
    Reflects downloads up to 02 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)1-Out-of-N Oblivious Transfer from MLWECryptology and Network Security10.1007/978-981-97-8013-6_6(123-143)Online publication date: 24-Sep-2024
    • (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
    • (2023)Scalable and Privacy-Preserving Federated Principal Component Analysis2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179350(1908-1925)Online publication date: May-2023
    • (2023)Sok: vector OLE-based zero-knowledge protocolsDesigns, Codes and Cryptography10.1007/s10623-023-01292-891:11(3527-3561)Online publication date: 1-Oct-2023
    • (2022)Asymptotically Quasi-Optimal CryptographyAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-06944-4_11(303-334)Online publication date: 30-May-2022
    • (2021)Multiparty Homomorphic Encryption from Ring-Learning-with-ErrorsProceedings on Privacy Enhancing Technologies10.2478/popets-2021-00712021:4(291-311)Online publication date: 23-Jul-2021

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media