Paper 2017/582

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

Angela Jäschke and Frederik Armknecht

Abstract

Fully Homomorphic Encryption (FHE) schemes allow arbitrary computations on encrypted data, making them a promising tool for numerous use cases that require outsourcing computation on private data to untrusted parties. 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. Although the question of selecting the encoding arises immediately in practice, users are mostly left alone in choosing it. 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 the 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 depends on the use-case and does not exist globally. We do show how to choose this best encoding depending on the use-case.

Note: Slight revisions so that structure is the same as CANS-paper.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. CANS 2017
Keywords
Fully Homomorphic EncryptionFHEEncodingEffort Analysis
Contact author(s)
jaeschke @ uni-mannheim de
History
2017-10-27: last of 2 revisions
2017-06-20: received
See all versions
Short URL
https://ia.cr/2017/582
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/582,
      author = {Angela Jäschke and Frederik Armknecht},
      title = {(Finite) Field Work: Choosing the Best Encoding of Numbers for FHE Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/582},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/582}},
      url = {https://eprint.iacr.org/2017/582}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.