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.