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

research-article

Integer Functions Suitable for Homomorphic Encryption over Finite Fields

Authors:

Ilia Iliashenko,

Christophe Negre,

Vincent ZuccaAuthors Info & Claims

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

Pages 1 - 10

https://doi.org/10.1145/3474366.3486925

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[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

MAEDA DMORIMURA KNARISADA SFUKUSHIMA KNISHIDE T(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
https://doi.org/10.1587/transfun.2023CIP0010
Morimura KMaeda DNishide T(2023)Accelerating Polynomial Evaluation for Integer-wise Homomorphic Comparison and DivisionJournal of Information Processing10.2197/ipsjjip.31.28831(288-298)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.288
Liu ZTromer E(2022)Oblivious Message RetrievalAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_26(753-783)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15802-5_26

Index Terms

Integer Functions Suitable for Homomorphic Encryption over Finite Fields
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption
2. Theory of computation
  1. Computational complexity and cryptography
    1. Circuit complexity
    2. Cryptographic primitives

Recommendations

A Survey on Homomorphic Encryption Schemes: Theory and Implementation

Legacy encryption systems depend on sharing a key (public or private) among the peers involved in exchanging an encrypted message. However, this approach poses privacy concerns. The users or service providers with the key have exclusive rights on the ...
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Special issue on innovations in theoretical computer science 2012 - Part II

We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, fully homomorphic ...
CCA-Secure Keyed-Fully Homomorphic Encryption
Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 9614

To simultaneously achieve CCA security and homomorphic property for encryption, Emura et al. introduced a new cryptographic primitive named keyed-homomorphic encryption, in which homomorphic ciphertext manipulations can only be performed by someone ...

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

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

Funding Sources

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

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

3
Total Citations
View Citations
207
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

MAEDA DMORIMURA KNARISADA SFUKUSHIMA KNISHIDE T(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
https://doi.org/10.1587/transfun.2023CIP0010
Morimura KMaeda DNishide T(2023)Accelerating Polynomial Evaluation for Integer-wise Homomorphic Comparison and DivisionJournal of Information Processing10.2197/ipsjjip.31.28831(288-298)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.288
Liu ZTromer E(2022)Oblivious Message RetrievalAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_26(753-783)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15802-5_26

View Options

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