Skip to content

Schemes and Protocols

This page provides [some of] the mathematical details of the cryptographic schemes and protocols used in Sequre.

1. Additive secret sharing

Sequre's MPC uses additive secret sharing over a finite field or ring (if specified by user via --use-ring flag).

Sharing

To share a value \(x\) among \(N\) parties:

  1. Sample \(x_1, \ldots, x_{N-1} \xleftarrow{\$} \mathbb{Z}_p\)
  2. Set \(x_N = x - \sum_{i=1}^{N-1} x_i \pmod{p}\)

Reconstruction

\[x = \sum_{i=1}^{N} x_i \pmod{p}\]

Addition (free)

Given \(\langle x \rangle\) and \(\langle y \rangle\), each party locally computes \(z_i = x_i + y_i \pmod{p}\). No communication needed.

Multiplication (Beaver triples)

Multiplication requires Beaver triples \((a, b, c)\) where \(c = a \cdot b \pmod{p}\), pre-generated by the trusted dealer.

To compute \(\langle z \rangle = \langle x \rangle \cdot \langle y \rangle\):

  1. Each party computes \(\epsilon_i = x_i - a_i\) and \(\delta_i = y_i - b_i\)
  2. Reveal \(\epsilon = x - a\) and \(\delta = y - b\)
  3. Each party computes: \(z_i = c_i + \epsilon \cdot b_i + \delta \cdot a_i + [i = 1] \cdot \epsilon \cdot \delta\)

Cost: one round of communication per multiplication.

Fixed-point arithmetic

Sequre represents real numbers in fixed-point with \(f\) fractional bits (MPC_NBIT_F):

\[\text{encode}(x) = \lfloor x \cdot 2^f \rceil \pmod{p}\]

After multiplication, the result has \(2f\) fractional bits and must be truncated back to \(f\) bits. Sequre uses secure truncation protocol here.

2. CKKS scheme

CKKS enables approximate homomorphic encryption of complex vectors.

Key generation

  • Sample secret \(s \xleftarrow{\chi_s} R_{QP}\) (ternary or Gaussian)
  • Public key: \(\text{pk} = (-a \cdot s + e, \; a)\) where \(a \xleftarrow{\$} R_Q\)
  • Relinearization key: gadget decomposition of \(s^2\) under auxiliary modulus \(P\)

Encoding

Map a vector \(\mathbf{v} \in \mathbb{C}^{N/2}\) to a polynomial \(m \in R\):

\[m = \lfloor \Delta \cdot \sigma^{-1}(\mathbf{v}) \rceil\]

where \(\sigma^{-1}\) is the inverse canonical embedding and \(\Delta\) is the scale.

Encryption

\[\text{ct} = (c_0, c_1) = (\text{pk}_0 \cdot u + m + e_0, \; \text{pk}_1 \cdot u + e_1)\]

where \(u \xleftarrow{\chi_s} R\) and \(e_0, e_1 \xleftarrow{\chi_e} R\).

Decryption

\[m + e_{\text{noise}} = c_0 + c_1 \cdot s\]

Homomorphic operations

Operation Formula Scale Level cost
Add \((c_0^A + c_0^B, \; c_1^A + c_1^B)\) \(\Delta\) 0
Mul \((d_0, d_1, d_2)\) then relinearize \(\Delta^2\) 0 (before rescale)
Rescale Divide by \(q_L\), drop level \(\Delta\) 1
Rotate by \(k\) Apply Galois \(\sigma_{5^k}\) + key-switch \(\Delta\) 0

Noise budget

Each ciphertext has \(L+1\) moduli. After \(L\) rescales, the ciphertext is at level 0 and cannot support further multiplications. The bootstrap (refresh) protocol restores levels. Sequre/Shechi currently supports only collective bootstrapping.

3. Multiparty CKKS protocols

Collective key generation (CKG)

Each party \(i\) holds \(s_i\) and produces:

\[h_i = a \cdot s_i + e_i\]

where \(a\) is the CRP. The hub aggregates: \(\text{pk} = (\sum_i h_i, \; -a)\). The collective secret is \(s = \sum_i s_i\) but no party knows it.

Collective relinearization key generation (RKG)

Similar to CKG but for the quadratic secret \(s^2\). Each party contributes an RKG share computed from \(s_i^2\) and cross-terms. Two rounds are needed.

Collective rotation key generation (RTG)

For each rotation index \(k\), each party produces a share relating \(\sigma_{5^k}(s_i)\) to \(s_i\). Shares are aggregated to form the Galois key.

Collective bootstrap (Refresh)

When a ciphertext's level is low:

  1. E2S (Encryption-to-Shares): Convert the ciphertext to additive plaintext shares
  2. Each party computes a masked partial decryption from its \(s_i\)
  3. Hub aggregates to get the plaintext share with smudging noise
  4. Transform: (Optional) Apply a function in the plaintext domain
  5. S2E (Shares-to-Encryption): Re-encrypt the shares into a fresh ciphertext at level \(L\)
  6. Each party encrypts its share under the collective public key
  7. Hub aggregates to get a fresh ciphertext

Cost: approximately 2 rounds of communication + the cost of fresh encryption.

Protocol switching (MPC ↔ MHE)

Sequre can convert between the two representations:

MPC → MHE (additive_share_vector_to_ciphervector):

  1. Each party masks its MPC share with bounded random values
  2. Reveal masked shares (communication)
  3. Each party encrypts its portion using CKKS enc_vector
  4. Aggregate ciphertexts at hub

MHE → MPC (ciphervector_to_additive_share_vector):

  1. Each party computes \(s_i \cdot c_1 + \text{mask}_i + e_i\)
  2. Aggregate at hub → hub gets \(c_0 + s \cdot c_1 + \sum \text{mask}_i + \sum e_i = m + \sum \text{mask}_i + \text{noise}\)
  3. Hub subtracts its mask → its MPC share
  4. Other parties use their mask as their MPC share

4. Comparison protocols

Secure comparisons (\(>, <, ==\)) cannot be done natively in CKKS. Sequre handles comparisons via MPC:

  1. Switch from MHE to MPC (if currently in HE)
  2. Execute the comparison using bit-decomposition in the MPC domain
  3. Switch back to MHE (if needed)

This is one of the key motivations for the hybrid MPC+MHE approach: MPC handles non-linear operations while MHE handles linear algebra efficiently.

Next steps