Paper 2026/1102

Finite-Field Arithmetic in CKKS

Abstract

We propose a CKKS-based technique for evaluating arithmetic over finite fields F_{p^r} with small characteristic p under homomorphic encryption. The core of our approach is a pair of complementary ciphertext representations. In the so-called spectral encoding, ciphertext addition and multiplication realize addition and multiplication in the field F_{p^r}. In another encoding, coefficient encoding, the same operations act as slotwise addition and multiplication in the slot algebra (F_p)^r. We show that one can switch homomorphically between these encodings at cost linear in r, and that F_p-linear maps, such as taking p-th powers in F_{p^r}, can be folded into these switches or applied directly in either representation. We complement the construction with theoretical and practical correctness-management techniques. To support unbounded computations, we integrate our framework with existing CKKS bootstrapping techniques and benchmark it against BGV-based implementations of F_{p^r}-arithmetic, a natural baseline for high-throughput finite-field computation. Across the fields we tested, this yields speedups ranging from 1.7x to 178x in amortized multiplication time when bootstrapping is taken into account. The gains are parameter-dependent: roughly speaking, our advantage over BGV increases as the characteristic p becomes smaller and the extension degree r becomes larger.