Paper 2024/673 Original: eprint.iacr.org/2024/673 ↗

Chocobo: Creating Homomorphic Circuit Operating with Functional Bootstrapping in basis B

Abstract

The TFHE cryptosystem only supports small plaintext space, up to 5 bits with usual parameters. However, one solution to circumvent this limitation is to decompose input messages into a basis B over multiple ciphertexts. In this work, we introduce B-gates, an extension of logic gates to non binary bases, to compute base B logic circuit. The flexibility introduced by our approach improves the speed performance over previous approaches such as the so called tree-based method which requires an exponential amount of operations in the number of inputs. We provide experimental results using sorting as a benchmark application and, additionally, we obtain a speed-up of ×3 in latency compared to state of the art BGV techniques for this application. As an additional result, we introduce a keyswitching key specific to packing TLWE ciphertexts into TRLWE ciphertexts with redundancy, which is of interest in many functional bootstrapping scenarios.