Threshold decryption and the ML adapter¶

A threshold scheme shares every functional key among s decryption servers: any t of them decrypt together, and fewer learn nothing beyond the result. This page walks through the threshold flow, the threshold MCFE over Ring-LWE with its split key shares, the accounting of the flooding noise, and federated learning with pyfe4ai.ml, and lists what fails and why.

The servers are honest-but-curious: a partial decryption carries no proof of correctness, so one server that deviates changes the result unnoticed (see Several enrolled sets). The threshold layers of tMIFE-LWE, tMCFE-LWE, tMCFE-Ring-LWE and tMCFE-FH-Multi-IPE are the project’s own constructions (status experimental; Security & Status).

Roles and flow¶

The key generator (the key authority) sets up the scheme, hands every client its encryption key and every server its key share of a functional key: get_decryption_keys(sid, credentials={"fusion_weight": y, ...}).
The clients encrypt, as in the scheme without a threshold.
An enrolled set of at least t servers is chosen; each enrolled server computes a partial decryption with share_decrypt, for that set.
A combiner (any party; it holds no secret) adds up the partial decryptions with combine_decrypt and decodes the result.

With the threshold MCFE over DDH (mcfe/ddh_threshold, reviewed):

import pyfe4ai

x = {"c0": [1, 2], "c1": [3, -1], "c2": [0, 4]}
y = {"c0": [2, 1], "c1": [1, 1], "c2": [-1, 3]}
servers = ["s0", "s1", "s2"]

kg, TMCFE = pyfe4ai.create("mcfe/ddh_threshold", {
    "eta": 2, "n": 3, "lst_nid": list(x), "s": 3, "t": 2, "lst_sid": servers})
kg.setup()
pp = kg.get_public_parameters()

label = "round-1"
cts = {nid: TMCFE({"id": nid, "keys": {"pp": pp, "sk": kg.get_private_keys(nid)}}).encrypt(x[nid], label)
       for nid in x}

def partials(enrolled):
    out = {}
    for sid in enrolled:
        dk = kg.get_decryption_keys(sid, credentials={"fusion_weight": y, "label": label})
        server = TMCFE({"id": sid, "keys": {"pp": pp, "dk": dk}})
        out[sid] = server.share_decrypt(cts, y, dk, enrolled, label)
    return out

combiner = TMCFE({"id": "combiner", "keys": {"pp": pp}})
print(combiner.combine_decrypt(partials(["s0", "s2"])))  # 18.0

The arguments of share_decrypt follow the scheme: the clients’ ciphertexts, then the weights of the key (mife/ddh_threshold, mife/lwe_threshold, mcfe/ddh_threshold) or the credentials {"fusion_weight": y, "label": label} (mcfe/lwe_threshold, mcfe/ring_lwe_threshold), the server’s key share, the enrolled set, and the label for mcfe/ddh_threshold and mcfe/fh_multi_ipe_pairing_threshold. The examples mcfe_threshold_demo.py, mcfe_lwe_threshold_demo.py, mife_lwe_threshold_demo.py, mcfe_fh_multi_ipe_threshold_demo.py and mcfe_ring_lwe_threshold_demo.py in the repository’s examples/ run each of them. Server and client ids are str or int, one type per list (Configuration options).

Several enrolled sets¶

combine_decrypt also takes a list of {sid: partial} mappings, one per enrolled set, and raises FESchemeError if their results disagree. With the t + 1 subsets of size t of t + 1 servers, every server is left out of some set, so one deviating server is detected (not identified):

print(combiner.combine_decrypt([partials(["s0", "s1"]), partials(["s1", "s2"]), partials(["s0", "s2"])]))

Sharings¶

The DDH and pairing threshold layers share the key with Shamir’s sharing and interpolate in the exponent. The LWE layers (mife/lwe_threshold, mcfe/lwe_threshold, mcfe/ring_lwe_threshold) flood every partial decryption with noise and share the key

with Shamir’s sharing for t = s;
with a replicated sharing for t < s (sharing="replicated", the default): Shamir shares with t < s let partial decryptions reveal the decryption noise modulo small integers (the leak of v0.3.0; see SECURITY.md and Upgrading from 0.3.0). A server then holds C(s - 1, t - 1) key pieces; the opt-in sharing="replicated-seeded" expands all of them but one from secret seeds (smaller key shares, computational instead of perfect hiding).

An explicit sharing="shamir" with t < s is refused under the standard profile and warns under toy; servers refuse such key shares unless their config has legacy_shamir="warn".

Threshold MCFE over Ring-LWE¶

mcfe/ring_lwe_threshold is the threshold scheme for large vectors and gradients: one ciphertext carries a whole tensor in chunks, and the Rust extension runs it natively. Its defaults (both profiles) are binary ciphertexts (ct_format="binary"), an RNS modulus (ring_modulus="rns") and split key shares (key_shares="split"):

the weight part – the label-independent part of the key, for one weight vector – is issued once: kg.get_weight_key_share(sid, credentials={"fusion_weight": y}), and each server keeps it with add_weight_key_share;
per round, get_decryption_keys(sid, credentials={"fusion_weight": y, "label": label}) issues only the label part, the shares of the label’s terms (key_part="full" asks for a whole key share instead).

import numpy as np
import pyfe4ai

clients, servers = ["c0", "c1", "c2"], ["s0", "s1", "s2"]
kg, TMCFE = pyfe4ai.create("mcfe/ring_lwe_threshold", {
    "eta": 1, "n": 3, "lst_nid": clients, "s": 3, "t": 2, "lst_sid": servers,
    "ring_n": 16, "bound_x": 50, "bound_y": 2})                 # toy sizes
kg.setup()
pp = kg.get_public_parameters()
weights = {"c0": [1], "c1": [2], "c2": [1]}
enrolled = ["s0", "s2"]

# once per weights: each server keeps its weight key share
srv = {sid: TMCFE({"id": sid, "keys": {"pp": pp}}) for sid in enrolled}
for sid, server in srv.items():
    server.add_weight_key_share(kg.get_weight_key_share(sid, credentials={"fusion_weight": weights}))

client = {nid: TMCFE({"id": nid, "keys": {"pp": pp, "sk": kg.get_private_keys(nid)}}) for nid in clients}
combiner = TMCFE({"id": "combiner", "keys": {"pp": pp}})

# a round of single vectors: eta rows per client, here a batch of two values
label = "round-1"
x = {"c0": [[3, -1]], "c1": [[2, 5]], "c2": [[-4, 0]]}
cts = {nid: client[nid].encrypt(x[nid], label) for nid in clients}
creds = {"fusion_weight": weights, "label": label}
partials = {sid: server.share_decrypt(cts, creds, kg.get_decryption_keys(sid, credentials=creds), enrolled)
            for sid, server in srv.items()}
print(combiner.combine_decrypt(partials))  # [3, 9]

# a round of gradients: ndarrays, packed into chunks
label = "round-2"
grads = {nid: np.random.default_rng(i).integers(-5, 6, (3, 7)) for i, nid in enumerate(clients)}
cts = {nid: client[nid].encrypt_lst_ndarray([grads[nid]], label=label) for nid in clients}
creds = {"fusion_weight": weights, "label": label,
         "n_chunks": TMCFE.key_chunks(cts["c0"]), "label_term": False}
parts = {sid: server.compute_lst_ndarray_ct(cts, creds, kg.get_decryption_keys(sid, credentials=creds), enrolled)
         for sid, server in srv.items()}
total = combiner.decrypt_lst_ndarray_ct(parts)[0]
print(np.array_equal(total, sum(weights[nid][0] * grads[nid] for nid in clients)))  # True

For ndarrays the label part covers the chunks (n_chunks, from key_chunks of a client’s ciphertexts); label_term=False leaves out the term that only single ciphertexts of the label need.

What the key generator keeps:

the sharings of the last 64 weight vectors (WEIGHT_SHARINGS_KEPT); weights issued again after that get a new sharing, and their servers need the new weight part (has_weight_key_share(dk) tells a server whether it keeps the weight part a label part completes);
the label parts of the last 16 labels per weight vector (LABEL_PARTS_KEPT); a label part asked for again later is a new sharing of the same key.

Accounting of the flooding noise¶

By default (flooding_accounting="per-sample") the flooding noise of a partial decryption is within statistical distance 2^-stat_param of its simulation per flooded value, with no limit on the number of partial decryptions; over a run the distances add up (the number of flooded values times 2^-stat_param). The opt-in flooding_accounting="kl" (mife/lwe_threshold and mcfe/ring_lwe_threshold, t = s with Shamir’s sharing only) bounds a whole run of at most max_partial_decryptions partial decryptions per server instead, for a smaller modulus and a weaker guarantee: a Hellinger distance below 2^(-stat_param/2) for the first max_partial_decryptions partial decryptions of every server, about stat_param - 6.85 bits in the bit-security sense of Micciancio and Walter for decision games – a total statistical distance of about 2^-65 at stat_param = 128, not 2^-121 (pyfe4ai.schemes.threshold.kl). Each server then counts its partial decryptions in a PartialDecryptionBudget that its deployment creates and passes in the server’s config:

import pyfe4ai
from pyfe4ai.schemes.threshold.kl import PartialDecryptionBudget

clients, servers = ["c0", "c1"], ["s0", "s1", "s2"]
kg, TMCFE = pyfe4ai.create("mcfe/ring_lwe_threshold", {
    "eta": 1, "n": 2, "lst_nid": clients, "s": 3, "t": 3, "lst_sid": servers,
    "ring_n": 16, "bound_x": 50, "bound_y": 2,
    "flooding_accounting": "kl", "max_partial_decryptions": 1000})
kg.setup()
pp = kg.get_public_parameters()

budgets = {sid: PartialDecryptionBudget(1000) for sid in servers}   # one per server
srv = {sid: TMCFE({"id": sid, "keys": {"pp": pp}, "partial_budget": budgets[sid]}) for sid in servers}
weights = {"c0": [1], "c1": [1]}
for sid, server in srv.items():
    server.add_weight_key_share(kg.get_weight_key_share(sid, credentials={"fusion_weight": weights}))

label = "round-1"
cts = {nid: TMCFE({"id": nid, "keys": {"pp": pp, "sk": kg.get_private_keys(nid)}}).encrypt([[7, 1]], label)
       for nid in clients}
creds = {"fusion_weight": weights, "label": label}
partials = {sid: s.share_decrypt(cts, creds, kg.get_decryption_keys(sid, credentials=creds), servers)
            for sid, s in srv.items()}
print(TMCFE({"id": "combiner", "keys": {"pp": pp}}).combine_decrypt(partials), budgets["s0"].remaining)  # [14, 2] 999

The guarantee holds only if a server’s count covers all its partial decryptions under the setup: a server that runs as several processes or restarts must share or persist its count (for instance a subclass with an atomic, durable consume). A budget cannot be copied or pickled, and it refuses to count in another process than the one that made it (after os.fork() parent and child would each count from the copied value). standard refuses mife/lwe_threshold with either accounting.

Federated learning with the ML adapter¶

FESchemeWrapper runs a scheme’s key generator and gives the helpers of pyfe4ai.ml what they need: encrypt_gradient() (a client) and aggregate_gradients() (the aggregator), with precompute_gradient() and prepare_aggregation() for an offline phase before the round. It holds the master key and plays every party, a single trust domain meant for experiments. Its default policy:

a client encrypts at most once per label (ValueError otherwise);
aggregate_gradients() needs a ciphertext and a non-zero weight for every enrolled client (allow_partial=True relaxes this) and aggregates a label with one weight vector only;
a gradient filed under another client than the one it names is refused.

These checks are per wrapper object, and they do not stop very unequal weights, which separate two clients’ gradients in one aggregate: the weights are the key holder’s choice. A pickled or copied wrapper carries the master key and every client’s key; ship a worker its client’s own crypto object instead (the scheme class built from wrapper.pp and wrapper.kg.get_private_keys(nid)).

The threshold MCFE in the adapter¶

For mcfe/ring_lwe_threshold the wrapper also runs the s decryption servers. prepare_aggregation() and aggregate_gradients() take servers= (default: the first t of lst_sid) and give each enrolled server its label key share of the round and, once per weights, its weight key share. The messages of a deployment are those of the separate steps: partial_decrypt_gradients() at each server and combine_partial_decryptions() at the combiner, with EncryptedGradient and ThresholdPartial serialised as JSON:

import json
import numpy as np
from pyfe4ai.ml import (EncryptedGradient, FESchemeWrapper, ThresholdPartial, aggregate_gradients,
                        combine_partial_decryptions, encrypt_gradient, partial_decrypt_gradients,
                        prepare_aggregation)

clients, servers = ["c0", "c1", "c2"], ["s0", "s1", "s2"]
wrapper = FESchemeWrapper("mcfe", "ring_lwe_threshold", {
    "eta": 1, "n": 3, "lst_nid": clients, "s": 3, "t": 2, "lst_sid": servers,
    "ring_n": 16, "bound_x": 50, "bound_y": 2}, precision=1)
weights = {"c0": 1, "c1": 2, "c2": 1}
grads = {nid: np.round(np.random.default_rng(i).uniform(-2, 2, (3, 7)), 1) for i, nid in enumerate(clients)}

# in-process: the wrapper runs the enrolled servers
enc = {nid: encrypt_gradient(grads[nid], wrapper, nid=nid, label="round-a") for nid in clients}
total = aggregate_gradients(enc, wrapper, weights, label="round-a", servers=["s0", "s1"])

# the messages of a deployment
prepared = prepare_aggregation(wrapper, weights, shape=(3, 7), label="round-b", servers=["s1", "s2"])
sent = {nid: json.dumps(encrypt_gradient(grads[nid], wrapper, nid=nid, label="round-b").to_dict())
        for nid in clients}
received = {nid: EncryptedGradient.from_dict(json.loads(m)) for nid, m in sent.items()}
wire = {sid: json.dumps(partial_decrypt_gradients(received, wrapper, prepared, server=sid).to_dict())
        for sid in prepared.servers}
total_b = combine_partial_decryptions(
    {sid: ThresholdPartial.from_dict(json.loads(m)) for sid, m in wire.items()}, wrapper, prepared)
print(np.allclose(total, total_b), np.allclose(total, sum(weights[n] * grads[n] for n in clients)))  # True True

If the label key shares of the enrolled servers turn out to be of different sharings, aggregate_gradients() fetches them again for all servers and decrypts once more; the separate steps raise MixedSharingsError (prepare the round again). A PreparedAggregation holds key material (the servers’ label key shares). The adapter refuses flooding_accounting="kl" and the other threshold and decentralized variants, which are used through their scheme classes as above.

What fails, and why¶

Error	Cause and remedy
`FESchemeError`: partial decryptions disagree on the ciphertexts they decrypted	the servers of one enrolled set decrypted different ciphertexts (a server answered another round, or deviated); in earlier versions `combine_decrypt` returned `None` here
`FESchemeError`: insufficient threshold shares	fewer than `t` partial decryptions, or a partial computed for another enrolled set
`FESchemeError`: the results of several enrolled sets disagree	one server deviates (Several enrolled sets)
`MixedSharingsError`	tMCFE-Ring-LWE partials of two sharings of one key (a label part issued again); fetch the label parts again for all servers
`FEKeyError`: a label key share needs this server’s weight key share	call `add_weight_key_share` with the server’s weight part of the same weights first
`FESchemeError`: the key share was derived for another label	each round needs its own label part
`FESchemeError`: need one ciphertext for every client of the key	the request lacks a client of the weights
`FESchemeError`: the ciphertext of a client is not authenticated for this server	tMIFE-LWE, tMCFE-Ring-LWE and tMCFE-FH-Multi-IPE servers decrypt only ciphertexts their clients tagged for them, under the label they serve
`FEKeyError` for a key share of v0.3.0, of another flooding or of other public parameters	key shares are bound to their public parameters (`pp_binding`) and to the flooding derivation; re-share the keys with this version (Upgrading from 0.3.0)
`FESchemeError` for a Shamir key share with `t < s`	re-share with the default replicated sharing, or create the server with `legacy_shamir="warn"` (`toy` only)
`FESchemeError`: partial decryption limit reached	the server’s `PartialDecryptionBudget` is spent (`"kl"`); a server without a budget, or with a budget made in another process, is refused the same way
`FEValidationError` for a server or client id	ids are `str` or `int`, one type per list; numpy integers are read as ints after setup (Configuration options)
`ValueError` from the ML adapter	its policy: a label used twice by one client, a missing client or a zero weight without `allow_partial=True`, a gradient filed under another client, or servers or weights keyed by values that are no ids
`NotImplementedError` from the ML adapter	MIFE (no labels) for gradients, or a threshold or decentralized variant other than `mcfe/ring_lwe_threshold`
`None`	the result is outside the decoding range (bounds too small for the data; with an `FEWarning`), or a key was requested for an unknown server (with an `FEWarning`) or an unknown client (with an `FEWarning` in the MIFE and MCFE DDH schemes and their ristretto255, threshold and decentralized variants; the other schemes return `None` without a warning)