Digital Log

    Seal-Manual-Notes

    The BFV Scheme

    • Plaintexts are polynomials in $R_t = \mathbb{Z}_t[x] / (x^n + 1)$. This is a quotient ring of polynomials with coefficients mod $t$. The polynomial modulus ensures the polynomials have degree less than $n$ (since $x^n = -1$ in this quotient ring).
      • Encrypting integers (larger than $t$) or rational numbers requires encoding into a plaintext polynomial in $R_t$. To ensure valid additions/multiplications, such operations need to be homormophic w.r.t. the encoding and decoding to and from the plaintext.
    • Ciphertexts are arrays of polynomials in $R_q$. The arrays have length greater than or equal to 2.
      • Addition: simple, compontent-wise
      • Multiplication: complicated, explained below, size of array increases unless relinearization is performed.
    • Other Parameters:
      • Security: $\lambda$
      • Base: $w$ (why is this needed? TODO ask Ravital)
        • Determines $\ell = \lfloor{\log_w(q)}\rfloor$, the number of terms in the decomposition from an integer in base $q$ into base $w$.
          • We also decompose polynomials in $R_q$ componentwise, resulting in $\ell + 1$ polynomials.
    • Notation: $s\xleftarrow{\$} \mathcal{S}$ denotes sampling $s$ uniformly from a finite set $\mathcal{S}$.
      • $\chi$: Error distribution (truncated discrete Guassian distribution)
      • $\Delta t$: $\lfloor q/t \rfloor$. That is, $\Delta$ is the quotient of a division: $q = \Delta t + r_t(q)$.
    • Algorithms:
      • SecretKeyGen($\lambda$):
        1. Sample $s \xleftarrow{\$} R_2$
        2. Output sk := $s$
      • PublicKeyGen(sk):
        1. Set $s =$ sk.
        2. Sample $a \xleftarrow{\$} R_q, \quad e \leftarrow \chi$
        3. Output $\left( \left[ -(as + e) \right]_q, a \right)$
      • EvaluationKeyGen(sk, $w$):
        1. For $i \in \{ 0, \ldots, \ell \}$ sample $a_i \xleftarrow{\$} R_q, \quad e_i \leftarrow \chi$
        2. Output evk[] = $\left( \left[ -(a_is + e_i) + w^is^2 \right]_q, a_i \right)$
        • Notice this is quite like the public key, but its an array the length of $\ell$ with powers of $w$, looks like it will be used for some sort of $q$ to $w$ base transformation.
      • Encrypt(pk, $m$):
        1. Let pk = $(p_0, p_1)$
        2. Sample $u \xleftarrow{\$} R_2, \quad e_1, e_2 \leftarrow \chi$
        3. Output ct = $\left(\left[\Delta m + p_0 u + e_1 \right]_q, \left[ p_1 u + e_2 \right]_q\right)$
      • Decrypt(sk, ct):
        1. Set $s =$ sk
        2. Set $c_0 =$ ct[0] and $c_1 =$ ct[1]
        3. Output $\left[ \lfloor \frac{t}{q}\left[ c_0 + c_1s \right]_q \rceil \right]_t$. That is, take the inner part mod $q$, scale to $t$, take the nearest integer, then compute modulo $t$.
      • Add(ct_a, ct_b):
        1. Output (ct_a[0] + ct_b[0], ct_a[1], ct_b[1])
      • Mult(evk, ct_a, ct_b):
        1. See source, too much to type. Basically:
          1. Take the tuple multiplication terms, which results in three polynomials: c_0 = c_a[0]c_b[0], c_1 = c_a[1]c_b[1], c_2 = c_a[0]c_b[1] + c_a[1]c_b[0],
          2. Scale them into $t$ and then reduce mod $q$, then combine them all with a base $w$ version ofc_1 (found using the evk key) to reduce the three polynomials into two. This is the relinearization step.

    The SEAL Scheme

    Seal's decryption is a bit more generalized

    • Plaintexts are the same.
    • Ciphertexts, instead of always being two polynomials, are instead generally $k$-tuple polynomials.
    • Decrypt(sk, ct[]):
      1. Set $s =$ sk
      2. Set $c_i =$ ct[i] for $i = 0,\ldots, k$
      3. Output $\left[ \lfloor \frac{t}{q}\left[ c_0 +\cdots+ c_ks^k \right]_q \rceil \right]_t$
    • Multiplication:
      • Evaluator::multiply is the first step (generalized to $k$-tuples), which can be applied and create larger ciphertexts without relinearization, if that's desirable.
      • Evaluator::relinearize is the second step (generalized to $k$-tuples).
    • Relinearization:
      • Requires $\ell + 1$ evaluator keys.
      • Getting an evaluator key requires the secret key, so it's not something in general that the evaluating party can do on the fly; they must request these up front.
      • Relinearizing after every multiplication step only requires one evaluator key, since this can continually take the ciphertext from size 3 to size 2.
    • Addition:
      • Also generalized to ciphertexts of arbitrary size. Simple, compontent-wise: if $ct_1 = (c_0,\ldots,c_j)$ and $ct_2 = (d_0,\ldots d_k)$ where $j \le k$, then $ct_+ = ([c_0 + d_0]_q,\ldots,[c_j+d_j]q, d{j+1}, \ldots, d_k)$.
      • Functions Evaluator::add and Evaluator::sub.

    Galois Automormophisms

    It's not clear exactly what this buys the user, but SEAL supports applying Galois automorphisms. I think it is performed on the ciphertext in a homomorphic way? It also requires special keys generated from KeyGenerator::generate_galois_keys.

    Plain operations

    You can also do add/multiply operations of a plaintext with a ciphertext, which is much more efficient than when both are ciphertexts.

    Multiple operations

    For adding or multiplying many ciphertexts at once, there is a more efficient Evaluator::multiply_many and Evaluator::add_many, the former uses relinearization and hence requires keys as input. Evaluator::exponentiate is similar.

    Square operations

    Evaluator::square has better complexity than normal multiplication, but the same noise growth.

    Composite Coefficient Modulus

    The coefficient modulus $q$ is a product of distinct primes, and homomorphic operations are implemented based on residue number system (RNS) arithmetic. Essentially $R_q \sim R_{q_1} \times \cdots \times R_{q_k}$ with operations done per prime factor.

    Noise budgets

    Note that full certainty noise budgets are not super practical; that is, if we want 100% certainty that we have enough noise budget for decryption, we get really poor upper bound estimates. Instead, SEAL uses heuristics that give estimates that hold with very high probability. Other things to note:

    • Every ciphertext has non-zero noise.
    • Addition/subtraction have very small impact on noise.
    • Relinearization increases noise by an additive factor; if this is done after a bunch of multiplications, its effect is dwarfed by the multiplication.
    • Decomposition bit count is important
      • Decreasing it is better for relinearization noise growth
      • Increasing it is better for relinearization computation cost
      • Setting this value and deciding when to relinearize are tough optimization choices.

    Encoding

    Encoding the desired values (integers, real numbers, etc.) into $R_t$, such that addition/multiplication is respected, is nontrivial. The responsibility falls to the evaluating party to be aware of the encoding and ensure that operations throughout computation remain in the image of the encoding map.

    Examples:

    1. Scalar: Encode $a \in \mathbb{Z}$ as constant polynomial $a \in R_t$. Works fine but obviously limited to integers modulo $t$. Naively increasing $t$? You get noise growth problems, which depends strongly on $t$. This is not a good choice.
    2. Integer encode: Encode $a \in \mathbb{Z}$ in terms of a base $B$. E.g. when $B = 2$ write $a$ as a polynomial where the coefficient $a_i \in \{0, 1\}$ is the $i$th digit in the binary expansion of $a$. Then decoding is simply evaluating the polynomial at $x = 2$.
      • Note that the ciphertext coefficients are not binary; they will increase up to $q$. This is all fine and correct until coefficients reduce modulo $t$ or polynomials reduce modulo $x^n +1$. Whne this happens, decoding will be incorrect with no error indication. Thus, again, it is on the evaluating party to ensure their computations stay within the limits of this encoding.
      • Offered via the class IntegerEncoder.
    3. Fractional Encoder: Given some base e.g. $B = 2$, expand the integral part as in the integer encoder. Further, encode the fractional $2^{-m}$ parts as terms $-x^{n-m}$ in the polynomial plaintext. Due to $x^n \equiv -1$, polynomial operations will respect rational operations.
      • Works for finite binary expansion. If not finite, precision must be truncated to $n_f$ bits (limited by the highest degree coefficients in the plaintext polynomial).
      • Requires a fixed $n_i$ boundary for which coefficients are fractional (the higher coefficients nearer to $n$) and which are integral (lower coefficients nearer to exponent $0$).
      • Requires operations do not wrap modulo $t$.
      • Requires that multiplication respects $n_i$. that is, integer exponents will start to rise toward $n_i$ and fractional parts will lower towards $n_i$; if this threshold is crossed, decoding will fail.
      • Available via class FractionalEncoder.
    4. CRT Batching: Leveraging a bunch of algebraic number theory that I don't understand quite yet, this is a powerful encoder that operates coefficient-wise in a SIMD (single instruction, multiple data) manner, aka batching.
      • Requires modulus $t$ to be a prime and $t \equiv 1 \mod 2n$.
      • Can be a huge performance improvement when used correctly.

    Encryption Parameters

    These affect performance, capabilities, and security. Good defaults are chosen where possible, but this is largely on the end user! Refer to HomomorphicEncryption.org for further advice.

    1. Polynomial Modulus: Must be $x^n + 1$ where $n$ is a power of 2. The larger $n$, the larger $q$ can be chosen, which allows for higher noise budget and larger $t$. Howerver, larger $n$ also decreases performance.
    2. Coefficient Modulus: Given a fixed polynomial modulus, coeffcient modulus $q$ affects (a) the noise budget of freshly encrypted ciphertext and (b) security level.
      • Note that SEAL can set "good" default values for $q$ after $n$ is chosen, but for some cases this will be unnecessarily large, and the user may prefer to use a smaller $q$ for performance.
      • Furthermore, decreasing $q$ always increases the security level.
    3. Plaintext Modulus: Any positive integer $t \ge 2$ and at most 60 bits in length. (Unless batching, which also requires $t \equiv 1 \mod 2n$).

    The EncryptionParameters instance is passed to SEALContext which verifies validity and keeps track of certain qualifiers (e.g. enable_batching is set to true if batching is possible with the given params).

    Function Privacy

    By default, SEAL does not try to keep information hidden from the owner of the secret key. This may not be desirable for certain protocols; for example if the evaluating party inputs private info into the circuit, the owner of the secret key can deduce information about the circuit and the inputs of the evaluator. If function privacy is required, there are a few approaches such as

    • flooding noise via relinearization and adding an encrypted 0 with very large noise. This is the recommended approach for SEAL 2.3.1.
    • soak-spin-repeat which uses bootstrapping to repeatedly re-encrypt ciphertext. This is super slow, requires large encryption parameters, and is not implemented in SEAL.
    • There are also scheme specific approaches to function privacy that are more efficient than these two generic methods.