Top

Published in:

2018 | OriginalPaper | Chapter

(Finite) Field Work: Choosing the Best Encoding of Numbers for FHE Computation

Authors : Angela Jäschke, Frederik Armknecht

Published in: Cryptology and Network Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Fully Homomorphic Encryption (FHE) schemes operate over finite fields while many use cases call for real numbers, requiring appropriate encoding of the data into the scheme’s plaintext space. However, the choice of encoding can tremendously impact the computational effort on the encrypted data. In this work, we investigate this question for applications that operate over integers and rational numbers using p-adic encoding and the extensions p’s Complement and Sign-Magnitude, based on three natural metrics: the number of finite field additions, multiplications, and multiplicative depth. Our results are partly constructive and partly negative: For the first two metrics, an optimal choice exists and we state it explicitly. However, for multiplicative depth the optimum does not exist globally, but we do show how to choose this best encoding depending on the use-case.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Computational Aspects of Ideal (t, n)-Threshold Scheme of Chen, Laing, and Martin

next chapter An Efficient Attribute-Based Authenticated Key Exchange Protocol

The term \(p^k\)-adic encoding denotes the natural extension of p-adic encoding to the field \(GF(p^k)\) for \(k\ge 1\) and is explained in Sect. 6.

Arita, S., Nakasato, S.: Fully homomorphic encryption for point numbers. IACR Cryptology ePrint Archive 2016/402 (2016)

Bonte, C., Bootland, C., Bos, J.W., Castryck, W., Iliashenko, I., Vercauteren, F.: Faster homomorphic function evaluation using non-integral base encoding. IACR Cryptology ePrint Archive 2017/333 (2017)

Chen, Y., Gong, G.: Integer arithmetic over ciphertext and homomorphic data aggregation. In: CNS (2015)

Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. IACR Cryptology ePrint Archive 2016/421 (2016)

Chung, H., Kim, M.: Encoding rational numbers for FHE-based applications. IACR Cryptology ePrint Archive 2016/344(2016)

Costache, A., Smart, N.P., Vivek, S., Waller, A.: Fixed point arithmetic in SHE scheme. IACR Cryptology ePrint Archive 2016/250 (2016)

van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_2CrossRef

Dowlin, N., Gilad-Bachrach, R., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Manual for using homomorphic encryption for bioinformatics. Technical report. MSR-TR-2015-87, Microsoft Research (2015)

Jäschke, A., Armknecht, F.: Accelerating homomorphic computations on rational numbers. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 405–423. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_22CrossRef

10.

Jäschke, A., Armknecht, F.: (Finite) field work: choosing the best encoding of numbers for FHE Computation. IACR Cryptology ePrint Archive 2017/582 (2017)

11.

Kim, E., Tibouchi, M.: FHE over the integers and modular arithmetic circuits. In: CANS, pp. 435–450 (2016)CrossRef

12.

Nuida, K., Kurosawa, K.: (Batch) fully homomorphic encryption over integers for non-binary message spaces. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 537–555. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_21CrossRef

13.

Xu, C., Chen, J., Wu, W., Feng, Y.: Homomorphically encrypted arithmetic operations over the integer ring. In: Bao, F., Chen, L., Deng, R.H., Wang, G. (eds.) ISPEC 2016. LNCS, vol. 10060, pp. 167–181. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49151-6_12CrossRef

Title: (Finite) Field Work: Choosing the Best Encoding of Numbers for FHE Computation
Authors: Angela Jäschke
Frederik Armknecht
Publisher: Springer International Publishing
Book: Cryptology and Network Security
Print ISBN: 978-3-030-02640-0

Electronic ISBN: 978-3-030-02641-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-02641-7_23

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner