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

Integer Functions Suitable for Homomorphic Encryption over Finite Fields

Published: 15 November 2021 Publication History

Abstract

Fully Homomorphic Encryption (FHE) gives the ability to evaluate any function over encrypted data. However, despite numerous improvements during the last decade, the computational overhead caused by homomorphic computations is still very important. As a consequence, optimizing the way of performing the computations homomorphically remains fundamental. Several popular FHE schemes such as BGV and BFV encode their data, and thus perform their computations, in finite fields. In this work, we study and exploit algebraic relations occurring in prime characteristic allowing to speed-up the homomorphic evaluation of several functions over prime fields.
More specifically we give several examples of unary functions: "modulo", "is power of b" and "Hamming weight" and "Mod2" whose homomorphic evaluation complexity over Fp can be reduced from the generic bound √2p + O (log(p)) homomorphic multiplications, to √ + O (log(p)), O (log (p)), O (√log (p)) and O (√(log (p))) respectively. Additionally we provide a proof of a recent claim regarding the structure of the polynomial interpolation of the "less-than'' bivariate function which confirms that this function can be evaluated in 2p-6 homomorphic multiplications instead of 3p-5 over Fp for p≥ - 5.

References

[1]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, page 309--325, New York, NY, USA, 2012. Association for Computing Machinery.
[2]
Hao Chen, Ilaria Chillotti, and Yongsoo Song. Improved bootstrapping for approximate homomorphic encryption. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 34--54. Springer, Heidelberg, May 2019.
[3]
Hao Chen and Kyoohyung Han. Homomorphic lower digits removal and improved FHE bootstrapping. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 315--337. Springer, Heidelberg, April / May 2018.
[4]
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. Bootstrapping for approximate homomorphic encryption. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 360--384. Springer, Heidelberg, April / May 2018.
[5]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology -- ASIACRYPT 2017, pages 409--437, Cham, 2017. Springer International Publishing.
[6]
Jung Hee Cheon, Dongwoo Kim, and Duhyeong Kim. Efficient homomorphic comparison methods with optimal complexity. In ASIACRYPT 2020, Part II, LNCS, pages 221--256. Springer, Heidelberg, December 2020.
[7]
Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun-Hee Lee, and Keewoo Lee. Numerical method for comparison on homomorphically encrypted numbers. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part II, volume 11922 of LNCS, pages 415--445. Springer, Heidelberg, December 2019.
[8]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 377--408. Springer, Heidelberg, December 2017.
[9]
Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping homomorphic encryption in less than a second. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 617--640. Springer, Heidelberg, April 2015.
[10]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144, 2012. https://eprint.iacr.org/2012/144.
[11]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 169--178. ACM Press, May / June 2009.
[12]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In CRYPTO (1), pages 75--92, 2013.
[13]
Shai Halevi and Victor Shoup. Bootstrapping for HElib. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 641--670. Springer, Heidelberg, April 2015.
[14]
Kyoohyung Han and Dohyeong Ki. Better bootstrapping for approximate homomorphic encryption. In CT-RSA 2020, LNCS, pages 364--390. Springer, Heidelberg, 2020.
[15]
Ilia Iliashenko and Vincent Zucca. Faster homomorphic comparison operations for BGV and BFV. PoPETs, 2021(3):246--264, 2021.
[16]
Shizuo Kaji, Toshiaki Maeno, Koji Nuida, and Yasuhide Numata. Polynomial expressions of p-ary auction functions. Journal of Mathematical Cryptology, 13(2):69--80, 2019.
[17]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60(6):43, 2013.
[18]
Michael S Paterson and Larry J Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal on Computing, 2(1):60--66, 1973.
[19]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84--93, 2005.
[20]
B. H. M. Tan, H. T. Lee, H. Wang, S. Q. Ren, and A. M. M. Khin. Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields. IEEE Transactions on Dependable and Secure Computing, pages 1--1, 2020.

Cited By

View all
  • (2024)Efficient Homomorphic Evaluation of Arbitrary Uni/Bivariate Integer Functions and Their ApplicationsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2023CIP0010E107.A:3(234-247)Online publication date: 1-Mar-2024
  • (2023)Accelerating Polynomial Evaluation for Integer-wise Homomorphic Comparison and DivisionJournal of Information Processing10.2197/ipsjjip.31.28831(288-298)Online publication date: 2023
  • (2022)Oblivious Message RetrievalAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_26(753-783)Online publication date: 12-Oct-2022

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

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. finite fields
  2. fully homomorphic encryption
  3. polynomial evaluation

Qualifiers

  • Research-article

Funding Sources

  • Junior Postdoctoral Fellowship from the Research Foundation ? Flanders (FWO)
  • CyberSecurity Research Flanders

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)30
  • Downloads (Last 6 weeks)1
Reflects downloads up to 02 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Efficient Homomorphic Evaluation of Arbitrary Uni/Bivariate Integer Functions and Their ApplicationsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2023CIP0010E107.A:3(234-247)Online publication date: 1-Mar-2024
  • (2023)Accelerating Polynomial Evaluation for Integer-wise Homomorphic Comparison and DivisionJournal of Information Processing10.2197/ipsjjip.31.28831(288-298)Online publication date: 2023
  • (2022)Oblivious Message RetrievalAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_26(753-783)Online publication date: 12-Oct-2022

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media