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

research-article

Open access

Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors

Authors:

Chiraag Juvekar,

Vinod VaikuntanathanAuthors Info & Claims

WAHC '21: Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography

Pages 29 - 41

https://doi.org/10.1145/3474366.3486928

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.

Digital Library

[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.

Digital Library

[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/

Digital Library

[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.

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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.

Digital Library

[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

Digital Library

[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.

Digital Library

[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

Digital Library

[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

Digital Library

[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

Digital Library

[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.

Digital Library

[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

Digital Library

[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.

Digital Library

[27]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices and Learning with Errors Over Rings. EUROCRYPT (2010).

Digital Library

[28]

Moni Naor and Benny Pinkas. 2006. Oblivious Polynomial Evaluation. SIAM J. Comput. 35 (01 2006), 1254--1281. https://doi.org/10.1137/S0097539704383633

Digital Library

[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

Digital Library

[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

Xu JPan Y(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
https://dl.acm.org/doi/10.1007/978-981-97-8013-6_6
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
Froelicher DCho HEdupalli MSa Sousa JBossuat JPyrgelis ATroncoso-Pastoriza JBerger BHubaux J(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
https://doi.org/10.1109/SP46215.2023.10179350
Show More Cited By

Index Terms

Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors
1. Security and privacy
  1. Cryptography

Recommendations

Efficient protocols for oblivious linear function evaluation from ring-LWE¹
Selected papers from the 12th Conference on Security and Cryptography for Networks

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f ( x ) = a x + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f ( x ). OLE can be used to build secret-shared multiplication, and is an ...
Universally composable oblivious transfer from ideal lattice

As a fundamental cryptographic primitive, oblivious transfer (OT) is developed for the sake of efficient usability and combinational feasibility. However, most OT protocols are built upon some quantum non-immune cryptosystems by assuming the hardness of ...
Sok: vector OLE-based zero-knowledge protocols
Abstract
A zero-knowledge proof is a cryptographic protocol where a prover can convince a verifier that a statement is true, without revealing any further information except for the truth of the statement. This article is a survey of recent developments in ...

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

Program Chairs:
Michael Brenner
Leibniz Universität Hannover, Germany
,
Rachel Player
Royal Holloway, University of London, UK
,
Kurt Rohloff
NJIT and Duality Technologies, USA

Copyright © 2021 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: 15 November 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '21

Sponsor:

SIGSAC

CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security

November 15, 2021

Virtual Event, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 6 of 17 submissions, 35%

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

6
Total Citations
View Citations
644
Total Downloads

Downloads (Last 12 months)334
Downloads (Last 6 weeks)46

Reflects downloads up to 03 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu JPan Y(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
https://dl.acm.org/doi/10.1007/978-981-97-8013-6_6
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
Froelicher DCho HEdupalli MSa Sousa JBossuat JPyrgelis ATroncoso-Pastoriza JBerger BHubaux J(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
https://doi.org/10.1109/SP46215.2023.10179350
Baum CDittmer SScholl PWang X(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
https://dl.acm.org/doi/10.1007/s10623-023-01292-8
de Castro LHazay CIshai YVaikuntanathan VVenkitasubramaniam M(2022)Asymptotically Quasi-Optimal CryptographyAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-06944-4_11(303-334)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-06944-4_11
Mouchet CTroncoso-Pastoriza JBossuat JHubaux J(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
https://doi.org/10.2478/popets-2021-0071

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

Media

Figures

Other

Tables

View Table of Contents