2

How do you implement truncation in homomorphic encryption libraries like HELib or SEAL when no division operation is allowed?

I have two floating point numbers a=2.3,b=1.5 which I scale to integers with 2-digit precision. Hence my encoder looks basically like this encode(x)=x*10^2. Assuming enc(x) is the encryption function, then enc(encode(a))=enc(230) and enc(encode(b))=enc(150).

Upon multiplication we obtain the huge value of a*b=enc(23*15)=enc(34500) because the scaling factors multiply too. This means that my inputs grow exponentially unless I can truncate the result, so that trunate(enc(34500))=truncate(enc(345)).

I assume such a truncation function is not possible because it cant be represented by a polynomial. Nonetheless, I wonder if there is any trick on how to perform this truncation mathematically or whether it is just an unsolved problem?

Overholt
  • 867
  • 1
  • 10
  • 23

1 Answers1

4

It is possible but difficult to perform such truncation in the BFV and BGV schemes, and is unlikely to result in acceptable performance in most use-cases. This problem is very much related to the complexity of bootstrapping said schemes; for more details, see https://eprint.iacr.org/2018/067 and https://eprint.iacr.org/2014/873.

On the other hand, truncation is much easier to achieve in the CKKS scheme (see https://eprint.iacr.org/2016/421) where it is a natural operation. However, the downside of the CKKS scheme is that all computations only yield approximately correct results which may not be what you want.

Kim Laine
  • 856
  • 5
  • 10
  • Thank you for your answer and especially the reference to CKKS schemes. I studied the papers and searched for publicly available implementations but I could not find any. Bootstrapping or digit removing is not implemented in SEAL as far as I know. Do you happen to know whether (and how) such implementations are accessible? – Overholt Sep 05 '18 at 09:58
  • CKKS is implemented in SEAL since version 3.0. Bootstrapping is currently not in SEAL and it is not clear if it would bring much value due to performance challenges and the limits to parametrization that it would impose. One implementation of CKKS bootstrapping is available in the HEAAN library: https://github.com/snucrypto/HEAAN. – Kim Laine Nov 16 '18 at 20:22