Paper 2016/344

Encoding Rational Numbers for FHE-based Applications

HeeWon Chung and Myungsun Kim

Abstract

This work addresses a basic problem of security systems that operate on very sensitive information, such as healthcare data. Specifically, we are interested in the problem of privately handling medical data represented by rational numbers. Considering the complicated computations on encrypted medical data, one of the natural and powerful tools for ensuring privacy of the data is fully homomorphic encryption (FHE). However, because the plaintext domain of known FHE schemes is restricted to a set of quite small integers, it is not easy to obtain efficient algorithms for encrypted rational numbers in terms of space and computation costs. Our observation is that this inefficiency can be alleviated by using a different representation of rational numbers instead of naive expressions. For example, the naïve decimal representation considerably restricts the choice of parameters in employing an FHE scheme, particularly the plaintext size. The starting point of our technique in this work is to encode rational numbers using continued fractions. Because continued fractions enable us to represent rational numbers as a sequence of integers, we can use a plaintext space with a small size while preserving the same quality of precision. However, this encoding technique requires performing very complex arithmetic operations, such as division and modular reduction. Theoretically, FHE allows the evaluation of any function, including modular reduction at encrypted data, but it requires a Boolean circuit of very high degree to be constructed. Hence, we primarily focus on developing an approach to solve this efficiency problem using homomorphic operations with small degrees.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Continued fractionsGosper algorithmRational numbersHomomorphic encryption
Contact author(s)
msunkim @ suwon ac kr
History
2016-03-31: received
Short URL
https://ia.cr/2016/344
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/344,
      author = {HeeWon Chung and Myungsun Kim},
      title = {Encoding Rational Numbers for FHE-based Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2016/344},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/344}},
      url = {https://eprint.iacr.org/2016/344}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.