Fast Base Conversion and Its Application

Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another.

For example, if we have $14 \mod 77$ and want to convert it to $x \mod 390$, FBC is widely used.

Mathematically, it can be represented as follows:

Here, the above equation represents an integer $x$ in modulus $q$, and FBC converts this integer into the modulus space $t$. The modulus $q$ is the product of small coprime moduli (i.e., $q = q_1 q_2 \dots q_k$), and $x$ is an integer such that $x \in [0, q)$. We also note that $q$ and $t$ are coprime numbers.

Here, we remark that it is not necessary for the above equation to produce the exact result for $x$. Instead of $x \mod t$, it will provide $x' \mod t$. Thus, the output of the above equation is as follows:

$\text{FBC}(x,q,t)=x+Aq\mathrm{mod}t$, where $A \in [0, k-1]$ and $A\mathrm{q\; is\; also\; known\; as\; the\; overflow\; error.}$

Theoretical Computation

Below is our theoretical computation. 

We consider x = 14, q = 2 x 3 x 5 = 30, and t = 7 x 11 =77.

The idea behind the calculation is as follows:

-->{[((14 mod 2)(2/30)) mod 2 x (30/2)] + [((14 mod 3)(3/30)) mod 3 x (30/3)] + [((14 mod 5)(5/30)) mod 5 x (30/5)]} (mod 77)

-->{0 + ((1/5) mod 3) x 10 + ((2/3) mod 5) x 6} (mod 77)

-->{-1 x 10 + 4 x 6} (mod 77)

--> {-10 + 24} (mod 77)

--> 14 mod 77.

Luckily, the overflow error is 0 in this case, but that is not always the case. ✌

Implementation

Below is our python implementation [you can also find the code on FBC).

 *****

from fractions import Fraction

def extended_euclidean(a, b):

    """Computes modular inverse of a (mod b) using extended Euclidean Algorithm."""

    old_r, r = a, b

    old_s, s = 1, 0

   

    while r != 0:

        quotient = old_r // r

        old_r, r = r, old_r - quotient * r

        old_s, s = s, old_s - quotient * s

   

    return old_s  # do not convert to positive*

def modular_inverse(fraction, mod):

    """Computes modular inverse of a fraction (a/b) mod mod correctly."""

    a, b = fraction.numerator, fraction.denominator

   

    # Compute b^{-1} mod 

    b_inv = extended_euclidean(b, mod)

    # Compute (a * b^{-1}) mod 

    inv = (a * b_inv) % mod

    # If numerator is 1, just return the modular inverse of denominator

    return inv if a != 1 else b_inv  # handling 1/b cases correctly

def fast_base_conversion(x, q, p, q_factors):

    """Converts x mod q to x mod p using FBT, preserving negatives.*"""

    terms = []

   

    for i, qi in enumerate(q_factors):

        xi = x % qi  # Compute x mod qi

        Qi = q // qi  # Compute Qi = q/qi

        if xi == 0:

            continue  # Skip if x mod qi is 0

        Ji = Fraction(xi, Qi)  # Compute Ji = xi / Qi

        # Compute J_i^{-1} mod qi correctly

        Ji_inv = modular_inverse(Ji, qi)

        # Compute the term ((J_i^{-1} mod q_i) * Q_i) mod p (preserve negatives)

        term = (Ji_inv * Qi) % p

        if Ji_inv * Qi < 0:

            term -= p  # ensures correct negative value is taken

        terms.append(term)

        print(f"Step {i+1}: x mod {qi} = {xi}, Q_i = {Qi}, J_i = {Ji}, J_i^(-1) mod {qi} = {Ji_inv}, term = {term} mod {p}")

   

    '''compute final result'''

    result = sum(terms) % p

    print("\nIntermediate Results:", terms)

    print(f"Final Output: {x} mod {q} = {result} mod {p}")

    return result

# Example Usage

x = 17

q = 105

p = 22

q_factors = [3, 5, 7]  # q = 2 * 3 * 5

converted_value = fast_base_conversion(x, q, p, q_factors)

*****

Application

Fast Base Conversion (FBC) is used in homomorphic encryption (HE) primarily for modulus switching and key-switching operations. These operations help manage ciphertext size and noise growth, ensuring efficient computations while preserving correctness.

Most HE schemes work over polynomial rings. Since working with a large $q$ is inefficient, FBC helps perform polynomial operations under smaller moduli, improving performance.

Gaining Point

Why is FBC widely used in homomorphic encryption?

Modulus switching is widely used in homomorphic encryption, and we know that each operation in homomorphic encryption increases the noise level. That’s why FBC is a valuable technique:

1. It produces less noise.
2. The noise accumulated during the FBC operation can be easily handled using advanced techniques such as the gamma-correction technique from [1] and floating-point instruction from [2].

We thanks to..

[1] Jean-Claude Bajard, Julien Eynard, M Anwar Hasan, and Vincent Zucca. A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes. In International Conference on Selected Areas in Cryptography, pages 423–442, 2016.

[2] Shai Halevi, Yuriy Polyakov, and Victor Shoup. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In Topics in Cryptology–CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings, pages 83–105, 2019