Shared Scheme Components

Building blocks shared by several scheme families: the DDH and EC-DDH base classes, the ABDP15 LWE layer and the configuration types.

DDH Base Classes

Base classes for DDH-family key generators.

Provides shared parameter caching logic (group generation, verification, serialisation) so that concrete SIFE / MIFE / MCFE DDH schemes only need to declare which configuration fields they use.

class pyfe4ai.schemes.common.ddh_base.DDHKeyGeneratorBase(config, **kwargs)

Bases: IPFEAbsKeyGenerator, ParameterCacheMixin

Base for standard DDH key generators sharing a (p, q, r, g) group.

Subclasses must set _scheme_type and _verify_keys, and may override _extra_param_fields to persist additional configuration.

Parameters:

config (dict)

class pyfe4ai.schemes.common.ddh_base.DamgardDDHKeyGeneratorBase(config, **kwargs)

Bases: IPFEAbsKeyGenerator, ParameterCacheMixin

Base for Damgard DDH key generators sharing a (p, q, g, h) group.

Subclasses must set _scheme_type and _verify_keys, implement _validate_bounds, and may override _extra_param_fields.

Parameters:

config (dict)

Elliptic-Curve DDH Base Classes

Shared parts of the DDH schemes over ristretto255 (*/ddh_ristretto255).

The constructions are those of the */ddh modules, which are stated for any prime-order group where DDH is hard; here the group is ristretto255 (RFC 9496, order L ~ 2^252, about 126-bit security against Pollard’s rho) instead of a 3072-bit Z_p^* subgroup. There are no group parameters to generate or cache. Group elements are serialised as 64 hex digits, scalars as decimal strings. Select these schemes with the variant ddh_ristretto255 or, through FESchemeWrapper, with group="ristretto255" on the ddh variant.

pyfe4ai.schemes.common.ec_ddh_base.check_group(config)

The group entry of a config, which must name ristretto255 if given.

Parameters:

config (dict)

Return type:

str

class pyfe4ai.schemes.common.ec_ddh_base.ECDDHKeyGeneratorBase(config, **kwargs)

Bases: IPFEAbsKeyGenerator

Key generator base: checks the group entry of the config.

Parameters:

config (dict)

class pyfe4ai.schemes.common.ec_ddh_base.ECDDHCryptoBase(config, **kwargs)

Bases: IPFEAbsCrypto

Crypto base: public parameters must name the group; dlog_bound (default 10^(precision + 2)) bounds the results decryption recovers.

Parameters:

config (dict)

ABDP15 LWE Base

Parts shared by the ABDP15 LWE IPFEs: sife/lwe, mife/lwe, mife/lwe_threshold.

The public matrix A in Z_q^{m x lwe_n} is published as a 32-byte seed and expanded by pyfe4ai.primitives.lattice.lwe_matrix.SeededMatrix (FrodoKEM-style; the expansion is modelled as a random oracle). Encryption draws a binary r and needs A^T r and pk^T r; both are computed exactly with numpy, for a whole batch of plaintexts at once.

matrix_mode (key generator and crypto configs; default "memory") chooses between keeping the expanded A in memory (fast, 8 L bytes per entry with L = ceil(bits(q) / 31)) and expanding it again for every batch ("stream": little memory, slow). The public keys pk = A S + E (m x eta per slot) are always held in memory.

Under the standard security profile lwe_n = "auto" selects the smallest dimension whose (q, sigma') meets pyfe4ai.primitives.lattice.lwe_utils.WIDE_LWE_128_LOG_RATIO, a lattice-estimator table for LWE with a uniform secret; an explicit lwe_n is checked against it. sigma' = sigma / (1 + B sqrt(eta)) is the error width of the LWE problem the security proof reduces to (pyfe4ai.primitives.lattice.lwe_utils.abdp15_reduction_sigma()), where B bounds how far the two challenge vectors of the IPFE game differ per coordinate: 2 X for sife/lwe, and 4 X in the slots of mife/lwe, whose reduction (ACFGU18, proof of Thm. 3) asks for x^(j,0) - x^(1,0) + x^(1,1) against x^(j,1). The width sigma of pk itself is 1 + B sqrt(eta) times larger, so the dimension is larger than an attack on pk alone would need.

The reduction is the ABDP15 full version (ePrint 2015/017, Oct. 2015), Thm. 4.4 with Thms. 6.6 and 6.7 (Construction 6.5, Sec. 6.2), written out in F. Bourse’s PhD thesis (ENS 2017), Thm. 4.3.5 with Thms. 8.2.2, 8.2.3, 8.3.2. Its width is the condition derived in the proof of Thm. 6.6 (= Bourse, Thm. 8.2.2); the parameter list of the full version’s Sec. 6.2 states the stronger, sufficient (l B + 1) sigma'.

Hypotheses of the papers that the library meets differently:

• The literal p > l B^2 of Thm. 4.4 / Sec. 6.2 is not needed for this Regev instance. The change of basis acts on secret keys mod the LWE prime q, where ||x1 - x0||^2 != 0 with a wide margin. Decryption decodes the integer inner product (p > 2 eta X Y + 1), so admissible keys are orthogonal to x1 - x0 over Z. The last hybrid only needs a + b uniform mod p.

• The 4 X per MIFE slot is the library’s ACFGU18 composition; neither text covers MIFE.

• The thesis’s LWE hardness bound (an absolute width above 2 sqrt(n)), which the full version does not state, is met under standard: sigma' >= 2^16, the smallest width of the table that standard enforces.

The public keys’ noise E – the only Gaussian of these schemes (encryption draws a binary r) – enters the proof as LWE with noise D_{Z,sigma}. Under standard it is sampled exactly (gaussian_sampler = "facct"; an explicit "rounded" is refused, a gaussian_sampler() block ignored): the double-precision rounded sampler is far from D_{Z,sigma} over the m eta samples of a key (crypto review, October 2026). Under toy it follows the config’s gaussian_sampler, else the library-wide choice. The public parameters record the sampler used.

pyfe4ai.schemes.common.abdp15_lwe.ENCRYPT_BATCH = 64

Plaintexts encrypted per pass over A by the ndarray helpers.

class pyfe4ai.schemes.common.abdp15_lwe.ABDP15KeyGeneratorMixin

Bases: ParameterCacheMixin

Parameter cache, seeded A and public keys of an ABDP15 LWE key generator.

The host class sets eta, bound_x and bound_y and calls _init_abdp15.

class pyfe4ai.schemes.common.abdp15_lwe.ABDP15CryptoMixin

Bases: object

Lazily expanded A, limb form of pk and batched masks (A^T r, pk^T r).

property A: SeededMatrix

The public matrix, shared by all crypto objects of this process.

Threshold Schemes

Shared machinery of the threshold schemes.

• sharing: Shamir, replicated and seed-expanded replicated sharing, dealt and added up for an enrolled set.

• binding: what key shares, ciphertexts and partial decryptions are bound to (pp_binding, construction ids, weights, client tags, sharing ids, formats, state versions) and the checks.

• codec: encodings of the key material, the threshold ciphertexts and partial decryptions (JSON and binary), strict parsing.

• store: the caches and stores of key share parts and sums, their locks.

• roles: server and combiner logic (checks, flooding noise, combination).

• kl: the KL accounting of the flooding.

Key Sharing

Key sharing of the threshold schemes: Shamir, replicated and seed-expanded replicated sharings, their dealing and the sums a server adds up for an enrolled set.

Provides polynomial evaluation, Shamir secret sharing, Lagrange interpolation and modular centering used identically by both the LWE and Ring-LWE threshold variants, and the replicated sharing (sharing = "replicated", the default for t < s, see resolve_sharing()) of the LWE / Ring-LWE threshold layers.

Why the LWE layers offer a second sharing: they flood partial decryptions with noise that hides a small unknown (the decryption noise nu) from whoever learns the result. With t - 1 servers C corrupted, the honest partial lambda_k^E F(k) + e_k of a Shamir sharing equals something computable from C’s shares and the result, plus e_k - M nu with M = lambda_k^E prod_{j in C} (k - j) / (0 - j). That is a rational number whenever t < s: for s = 3, t = 2, C = {2}, E = {1, 3} it is 3 / 4, and four times the partial minus the computable part is 4 e_k - 3 nu, an integer whose residue mod 4 is nu mod 4 – whatever the flooding width. Fewer corrupted servers, or none, can suffice: from the partials of several enrolled sets the aggregator alone reads nu modulo (s - 1)! for t = 1 (6 for s = 5, t = 2). A replicated sharing (one additive piece per (t - 1)-subset T of the points, held by the servers outside T) has reconstruction coefficients 0 and 1: M is 0 or 1, and the flooding argument holds as stated. Its cost is C(s - 1, t - 1) pieces per server instead of one share (2 for s = 3, t = 2; 6 for s = 5, t = 3). See share_replicated(). The opt-in sharing = "replicated-seeded" (share_replicated_seeded()) expands every piece but one from a 32-byte seed, so that a server holds seeds and at most one full piece; the pieces, and the partial decryptions, are those of a replicated sharing, but the key shares hide the key only computationally (SHAKE-256 keyed by the seeds as a pseudo-random function).

The encodings of the key material (value lists or binary words) are in pyfe4ai.schemes.threshold.codec, the caches of the sums for an enrolled set in pyfe4ai.schemes.threshold.store.

pyfe4ai.schemes.threshold.sharing.eval_poly(coeffs, x_value, modulus)

Evaluate a polynomial at x_value modulo modulus.

Parameters:

• coeffs (list[mpz]) – Polynomial coefficient list.

• x_value (int) – Evaluation point.

• modulus (mpz) – Modulus for the arithmetic operation.

Return type:

mpz

pyfe4ai.schemes.threshold.sharing.share_secret(secret, threshold, share_points, modulus)

Create Shamir secret shares of secret.

Parameters:

• secret (mpz) – The secret to share.

• threshold (int) – Minimum number of shares needed for reconstruction.

• share_points (list[int]) – Evaluation points for the shares.

• modulus (mpz) – Modulus for the arithmetic operation.

Return type:

dict[int, mpz]

pyfe4ai.schemes.threshold.sharing.lagrange_coefficient_at_zero(x_j, xs, modulus)

Return the Lagrange basis coefficient of point x_j evaluated at 0.

Computes prod_{m != j} x_m / (x_m - x_j) modulo modulus with a modular inverse, so modulus must be prime (or at least coprime to every difference) and the points in xs must be distinct and non-zero.

Parameters:

• x_j (int) – Evaluation point whose coefficient is requested.

• xs (list[int]) – All evaluation points taking part in the reconstruction.

• modulus (mpz) – Modulus for the arithmetic operation.

Return type:

mpz

pyfe4ai.schemes.threshold.sharing.lagrange_at_zero(shares, modulus)

Reconstruct the secret (polynomial value at 0) from shares.

Parameters:

• shares (dict[int, mpz]) – List of (x, y) share pairs.

• modulus (mpz) – Modulus for the arithmetic operation.

Return type:

mpz

pyfe4ai.schemes.threshold.sharing.center_mod(value, modulus)

Center value into the range (-modulus/2, modulus/2].

Parameters:

• value (mpz) – Input value.

• modulus (mpz) – Modulus for the arithmetic operation.

Return type:

mpz

pyfe4ai.schemes.threshold.sharing.share_points(lst_sid)

Map each decryption server to its Shamir evaluation point.

Points start at 1: the polynomial value at 0 is the shared secret itself, so no server may ever hold the share at x = 0.

Parameters:

lst_sid (list[str]) – Ordered list of all decryption-server identifiers.

Return type:

dict[str, int]

pyfe4ai.schemes.threshold.sharing.validate_threshold(threshold, lst_sid)

Reject a lst_sid that is not a list of distinct server ids (check_id_list()) and thresholds outside 1 <= t <= s (or bool).

Parameters:

• threshold (int) – Minimum number of shares needed for reconstruction.

• lst_sid (list[str]) – Ordered list of all decryption-server identifiers.

Return type:

None

pyfe4ai.schemes.threshold.sharing.check_rns_servers(s, factors)

Raise unless every factor of an RNS modulus exceeds the number of servers s: Shamir sharing over Z_q = prod F_{q_i} (CRT) needs the points 1..s and their differences to be units mod every factor.

Raises:

FEValidationError – If s >= min q_i.

Return type:

None

pyfe4ai.schemes.threshold.sharing.replicated_sets(points, threshold)

Index sets of a replicated sharing: the (t - 1)-subsets of points, sorted.

Parameters:

• points (list[int])

• threshold (int)

Return type:

list[tuple[int, ...]]

pyfe4ai.schemes.threshold.sharing.share_replicated(material, threshold, points, modulus, binary=False)

Replicated sharing of every value in material (nested dicts and lists).

Draws one piece r_T per (t - 1)-subset T of points, of the layout of material (values as decimal strings), uniform subject to sum_T r_T = material mod modulus. The server at point x receives the pieces with x not in T: any t servers hold every piece, any t - 1 servers C miss exactly r_C, which is uniform given the others. With t = s this is additive sharing (one piece each). With the native backend the pieces are drawn and the correction computed by the extension, with the values of the Python code for the same random bytes (_share_replicated_native). With binary every polynomial of a piece is bytes (binary_material(); the same values).

Return type:

dict[tuple[int, ...], object]

Returns:

{T: piece} for every index set T.

Parameters:

• threshold (int)

• points (list[int])

• modulus (mpz)

• binary (bool, default: False)

pyfe4ai.schemes.threshold.sharing.pieces_held(pieces, point)

The pieces of share_replicated() held by the server at point, as [{"set": [...], "share": piece}] (JSON-friendly).

Parameters:

• pieces (dict)

• point (int)

Return type:

list[dict]

pyfe4ai.schemes.threshold.sharing.SEED_BYTES = 32

many seeds are dealt, and the LWE layers aim at post-quantum security).

Type:

Bytes of a seed of share_replicated_seeded() (256 bits

pyfe4ai.schemes.threshold.sharing.piece_layout(material)

The layout of material that expand_seeded_piece() follows: dicts and lists of the same structure, a list of values replaced by its length and a single value by None (JSON-friendly).

pyfe4ai.schemes.threshold.sharing.expand_seeded_piece(seed, index_set, layout, modulus, fields=None, ctx=None)

The piece r_T of a seeded replicated sharing, of layout, as ints mod modulus.

Every list of values (path p in layout, length L) is hash_to_zq_vector(json([seed, T, p, q]), q, L) under the domain pyfe4ai/threshold/replicated-seeded/piece/v1: SHAKE-256 blocks of bits(q) + 128 bits reduced mod q, each within 2^-130 of uniform, and pseudo-random as long as the seed is secret (SHAKE-256 as a PRF keyed by the seed, which follows a public prefix, on the inputs (T, p, q)). The seed is lower-case hex and the dict keys of p are the strings JSON makes of them, so that a key share expands alike before and after a JSON round trip.

Parameters:

• seed (str) – The piece’s seed (hex, SEED_BYTES bytes).

• index_set – The set T of the piece.

• layout – piece_layout() of the shared material.

• modulus – Modulus q.

• fields (default: None) – Top-level entries to expand (all if None).

• ctx (default: None) – A ring of modulus (pyfe4ai.backend.ring(), any dimension): expand with its hash_to_zq() (natively for a native ring: the same values).

Raises:

• FEKeyError – For a malformed seed or layout.

• FESchemeError – For a context of another modulus.

pyfe4ai.schemes.threshold.sharing.share_replicated_seeded(material, threshold, points, modulus, ctx=None)

Replicated sharing of material with pieces expanded from seeds.

The pieces are those of share_replicated() – one per (t - 1)-subset T of points, held by the servers outside T, adding up to material mod modulus – except that each piece but the first, T0 = {1, ..., t - 1}, is r_T = G(seed_T, T) (expand_seeded_piece(), a fresh SEED_BYTES-byte seed per piece) and the first is the correction r_T0 = material - sum r_T. A server stores the seeds of its pieces (C(s - 1, t - 1) of them, one fewer if it holds r_T0) and r_T0 if it lies outside T0: the servers 1..t-1 hold no full piece, the others one.

Hiding is computational: a coalition C of t - 1 servers other than T0 holds r_T0 and misses seed_C, and r_T0 is independent of the key only once G(seed_C) is replaced by a uniform piece. That hybrid takes SHAKE-256 to be a PRF keyed by the secret 256-bit seed, which follows a public prefix and is expanded over many leaf paths (a standard keyed-sponge assumption, of the kind the derandomised flooding noise of the threshold layers makes with its key first). C = T0 holds seeds only, which are independent of the key, as with share_replicated().

Parameters:

• ctx (default: None) – A ring of modulus (pyfe4ai.backend.ring()): checked (the leaves are expanded and added up by the backend’s zq_sum()).

• threshold (int)

• points (list[int])

• modulus (mpz)

Return type:

dict

Returns:

{"layout", "correction": (T0, r_T0 as decimal strings), "seeds": {T: hex}}.

pyfe4ai.schemes.threshold.sharing.seeded_pieces_held(sharing, point)

What the server at point stores of a share_replicated_seeded() sharing: {"pieces": [{"set", "share"}] (r_T0, or none), "seeds": [{"set", "seed"}], "layout"} (JSON-friendly).

Parameters:

• sharing (dict)

• point (int)

Return type:

dict

pyfe4ai.schemes.threshold.sharing.deal_replicated(material, sharing, threshold, lst_sid, modulus, binary=False, ctx=None)

What each server stores of a replicated sharing of material among lst_sid (points of share_points()): {sid: {"pieces": ...}} (share_replicated(), pieces_held()) for "replicated", or {sid: {"pieces", "seeds", "layout"}} (share_replicated_seeded(), seeded_pieces_held()) for "replicated-seeded". binary deals binary pieces ("replicated"), ctx expands the seeded pieces natively ("replicated-seeded").

Raises:

FEValidationError – For another sharing.

Parameters:

• sharing (str)

• threshold (int)

• lst_sid (list)

• binary (bool, default: False)

Return type:

dict

pyfe4ai.schemes.threshold.sharing.share_polys(polys, threshold, lst_sid, modulus, ring_n, binary=False, ctx=None)

Shamir shares of every coefficient of polys (ring_n values or ring_n binary words each) among lst_sid (points of share_points()): [{sid: share polynomial}], as decimal strings, or bytes with binary. With ctx, a ring of modulus on which the threshold kernels run natively (threshold_native), in one native call (coefficients drawn as share_secret() draws them, in the same order); else share_secret() per coefficient. Every polynomial must be ring_n values or ring_n words on its own (binary polynomials that are whole words only together would be dealt misaligned).

Raises:

FEKeyError – For malformed key material.

Parameters:

• polys (list)

• threshold (int)

• lst_sid (list)

• ring_n (int)

• binary (bool, default: False)

Return type:

list

pyfe4ai.schemes.threshold.sharing.replicated_assignment(x_k, xs, points, threshold)

Index sets whose pieces the server at x_k adds up for enrolled points xs.

Piece r_T goes to the smallest enrolled point outside T (|xs| >= t > |T|, so there is one, and it holds r_T): the enrolled servers’ sums add up to the secret, each piece counted once.

Parameters:

• x_k (int)

• xs (list[int])

• points (list[int])

• threshold (int)

Return type:

list[tuple[int, ...]]

pyfe4ai.schemes.threshold.sharing.share_for_enrolled(dk, sid, lst_sid_enrolled, threshold, modulus, fields=None, cache=None, legacy_shamir='refuse', profile=None, ring_n=None)

What server sid multiplies, by what, for a partial decryption for lst_sid_enrolled.

Returns (share, multiplier, tag). For a Shamir key share dk: (dk, lambda, digits(lambda)), lambda the Lagrange coefficient at zero. With t < s (a key share of versions <= 0.3.0, or an explicit sharing="shamir") such a key share is refused, unless legacy_shamir is "warn" and the public parameters do not record the standard profile: then it is served with an FESecurityWarning. For a replicated one (dk["pieces"]): dk with the sum of the pieces of replicated_assignment() in place of the pieces (of the entries fields only, if given), multiplier 1 and a tag naming those pieces. Partial decryptions seed their flooding noise with the tag: they depend on the enrolled set only through it. A seeded replicated key share (dk["seeds"], share_replicated_seeded()) gives what the replicated key share of the expanded pieces gives, tag included.

Parameters:

• cache (default: None) – An OrderedDict that keeps the sums of the last SHARE_CACHE_SIZE key shares and assignments, for key shares that are not modified once handed in (they are told apart by identity). The returned share must not be modified.

• ring_n (default: None) – The ring dimension of a Ring-LWE layer; the sums (the backend’s zq_sum()) need no ring, so it is only checked against the backend’s ring of the modulus.

• legacy_shamir (str, default: 'refuse') – "refuse" or "warn" (see LEGACY_SHAMIR_POLICIES).

• profile (default: None) – security_profile recorded in the public parameters (None for those of versions <= 0.3.0).

• dk (dict)

• sid (str)

• lst_sid_enrolled (list[str])

• threshold (int)

• modulus (mpz)

Raises:

• FEKeyError – If dk lacks a piece (or its seed) the server must add.

• FESchemeError – For a Shamir key share with t < s that is not to be served.

Return type:

tuple[dict, mpz, str]

Binding and Versions

What the threshold artifacts are bound to, and the checks.

• Key shares to public parameters: pp_binding() over a scheme’s binding fields, checked by check_pp_binding() before every partial decryption; key shares to the weights they were derived for (fusion_weight_id()). The sharing, the threshold construction and the other version markers are checked by pyfe4ai.core.versions.

• Ciphertexts to the servers that decrypt them: HMAC-SHA256 tags under client-server keys (client_server_mac_keys(), tag_ciphertext(), check_ciphertext_tags(); the tag messages are in pyfe4ai.schemes.threshold.codec).

• The threshold MCFE over Ring-LWE: the fields its weight and label key share parts share (check_split_parts()).

Binding fields are those of earlier versions; nothing here changes a digest.

pyfe4ai.schemes.threshold.binding.pp_binding(pp, fields, defaults=None)

Hex SHA-256 of the public-parameter fields a threshold key share is bound to (canonical JSON of [[field, value], ...]; a missing field takes its value in defaults – what its absence means, e.g. the label hash of versions <= 0.3.0 – else null).

The key generator writes it into every key share (pp_binding) and a server compares it with that of its own public parameters (check_pp_binding()) before computing a partial decryption: one key share answering a request under public parameters that differ in the modulus, the flooding (distribution, width, tail cut, accounting and its limit) or the label hash would give a second, differently derived answer to the same request, and the difference of the two reveals key material (with the label hash: lambda <share, H_A(l) - H_B(l)> exactly). The sharing and the threshold construction are checked on their own (check_served_sharing()).

Parameters:

• pp (dict)

• fields (tuple)

• defaults (dict | None, default: None)

Return type:

str

pyfe4ai.schemes.threshold.binding.check_pp_binding(pp, dk, fields, defaults=None)

Raise unless key share dk was issued for public parameters with pp’s values of fields (see pp_binding()); return pp’s digest.

The servers also seed their flooding noise with the returned digest – that of their own public parameters, equal to the key share’s once checked – so that even if this check were bypassed, a request answered under other public parameters would get another noise, not an exact difference.

Raises:

FEKeyError – For a key share of other public parameters, or one without pp_binding (issue new key shares).

Parameters:

• pp (dict)

• dk (dict)

• fields (tuple)

• defaults (dict | None, default: None)

Return type:

str

pyfe4ai.schemes.threshold.binding.TMIFE_LWE_BINDING_FIELDS = ('q', 'p', 'lwe_n', 'm', 'eta', 'n', 'A_seed', 's', 't', 'lst_sid', 'sigma_f', 'flood_tail_cut', 'flooding_accounting', 'max_partial_decryptions', 'stat_param')

The public-parameter fields a tMIFE-LWE key share is bound to.

pyfe4ai.schemes.threshold.binding.TMIFE_LWE_BINDING_DEFAULTS = {'flooding_accounting': 'per-sample'}

The values of absent tMIFE-LWE binding fields.

pyfe4ai.schemes.threshold.binding.TMCFE_LWE_BINDING_FIELDS = ('q', 'q0', 'K', 'delta', 'n0', 'm0', 's', 't', 'lst_sid', 'sigma_f', 'label_hash')

The public-parameter fields a tMCFE-LWE key share is bound to, the label hash among them (one key share answering a label under two label hashes with the same noise would give w_A - w_B = lambda <share, H_A(l) - H_B(l)> exactly).

pyfe4ai.schemes.threshold.binding.TMCFE_LWE_BINDING_DEFAULTS = {'label_hash': 'shake256-wide'}

The values of absent tMCFE-LWE binding fields.

pyfe4ai.schemes.threshold.binding.TMCFE_RING_LWE_BINDING_FIELDS = ('q', 'p', 'ring_n', 'eta', 's', 't', 'lst_sid', 'flooding', 'flood_bits', 'sigma_f', 'flood_tail_cut', 'flooding_accounting', 'max_partial_decryptions', 'stat_param', 'label_hash')

The public-parameter fields a tMCFE-Ring-LWE key share is bound to (what its partial decryptions depend on beyond the sharing and the construction).

pyfe4ai.schemes.threshold.binding.TMCFE_RING_LWE_BINDING_DEFAULTS = {'flooding': 'gaussian', 'flooding_accounting': 'per-sample', 'label_hash': 'shake256-wide'}

The values of absent tMCFE-Ring-LWE binding fields.

pyfe4ai.schemes.threshold.binding.TMCFE_RING_LWE_OPTIONAL_BINDING_FIELDS = ('ct_format', 'q_factors')

The tMCFE-Ring-LWE fields bound only where the public parameters have them (the digests of public parameters without them, of earlier versions too, stay as they were).

pyfe4ai.schemes.threshold.binding.tmcfe_ring_lwe_binding_fields(pp)

The public-parameter fields a tMCFE-Ring-LWE key share of pp is bound to: TMCFE_RING_LWE_BINDING_FIELDS and those of TMCFE_RING_LWE_OPTIONAL_BINDING_FIELDS that pp has (ct_format of binary public parameters, q_factors of an RNS modulus).

Parameters:

pp (dict)

Return type:

tuple

pyfe4ai.schemes.threshold.binding.fusion_weight_id(fusion_weight)

Return a canonical digest of a fusion-weight dict.

Key shares record the digest of the weights they were derived for, so a server can refuse to combine ciphertexts under different weights.

Parameters:

fusion_weight (dict) – Mapping of client IDs to integer weight lists.

Return type:

str

pyfe4ai.schemes.threshold.binding.check_fusion_weight(dk, fusion_weight)

Raise unless fusion_weight are the weights the key share dk is for.

Parameters:

• dk (dict)

• fusion_weight (dict)

Return type:

None

pyfe4ai.schemes.threshold.binding.client_server_mac_keys(lst_nid, lst_sid)

Fresh 32-byte MAC keys (hex), {nid: {sid: key}}, for ciphertext tags.

Client nid holds {sid: key} and tags each ciphertext for every server; server sid holds {nid: key} and checks the tags meant for it (see check_ciphertext_tags()).

Parameters:

• lst_nid (list)

• lst_sid (list)

Return type:

dict

pyfe4ai.schemes.threshold.binding.ciphertext_tag(mac_key, domain, payload)

HMAC-SHA256 (hex) of (domain, payload) under mac_key (hex).

Parameters:

• mac_key (str)

• domain (str)

Return type:

str

pyfe4ai.schemes.threshold.binding.tag_ciphertext(ct, mac_keys, domain, payload)

Add tags (one per server of mac_keys) to ct and return it.

Parameters:

• ct (dict)

• mac_keys (dict)

• domain (str)

Return type:

dict

pyfe4ai.schemes.threshold.binding.server_tag(tags, sid)

The tag for server sid in a ciphertext’s tags (None if there is none). JSON writes the key of an integer server id as its decimal string (1 becomes "1"): after a JSON round trip the tag of server 1 is found under "1". It still verifies only under that server’s key.

pyfe4ai.schemes.threshold.binding.check_ciphertext_tags(dict_ct, mac_keys, sid, domain, payload_of)

Raise unless every ciphertext’s tag for server sid verifies.

Threshold servers compute partial decryptions that are linear in parts of the ciphertexts they are handed; were these chosen freely, the partials would reveal the shared functional key. Servers therefore only decrypt ciphertexts tagged by their clients.

Parameters:

• dict_ct (dict) – {nid: ciphertext}.

• mac_keys (dict) – The server’s {nid: key}.

• sid (str) – The server’s id.

• domain (str) – Domain-separation string of the scheme.

• payload_of – payload_of(nid, ct), the tagged content of a ciphertext.

Raises:

FESchemeError – For a missing, malformed or wrong tag.

Return type:

None

pyfe4ai.schemes.threshold.binding.tag_ciphertext_message(ct, mac_keys, message)

Add tags to ct: HMAC-SHA256 (hex) of the raw message under each server’s key of mac_keys, and return it (binary ciphertexts, whose tag messages are bytes rather than JSON).

Parameters:

• ct (dict)

• mac_keys (dict)

• message (bytes)

Return type:

dict

pyfe4ai.schemes.threshold.binding.check_ciphertext_tag_messages(dict_ct, mac_keys, sid, message_of)

check_ciphertext_tags() for tags over raw messages (tag_ciphertext_message()): message_of(nid, ct) returns the bytes a ciphertext’s tag covers, or raises ValueError (KeyError, TypeError) for a malformed one.

Raises:

FESchemeError – For a missing, malformed or wrong tag.

Parameters:

• dict_ct (dict)

• mac_keys (dict)

• sid (str)

Return type:

None

pyfe4ai.schemes.threshold.binding.SPLIT_SHARE_FIELDS = ('sid', 'lst_sid', 'weights_id', 'share_set_id', 'sharing', 'mac_keys', 'noise_version', 'noise_sampler', 'flooding', 'label_hash', 'pp_binding')

Fields in which the weight and the label part of a tMCFE-Ring-LWE key share must agree (an absent sharing is "shamir").

pyfe4ai.schemes.threshold.binding.check_split_parts(weight, dk)

Raise unless the weight part weight and the label part dk of a key share agree in every field of SPLIT_SHARE_FIELDS.

Raises:

FEKeyError – For parts that do not belong together.

Parameters:

• weight (dict)

• dk (dict)

Return type:

None

Encodings

Encodings of the threshold artifacts and their strict parsing.

• The values of the threshold DDH key shares: decimal strings only (is_decimal()).

• Key material (nested dicts and lists of polynomials) as value lists – ints, mpz or decimal strings, read by strict_mpz() – or binary words (binary_material(): ceil(bits(q) / 8) bytes per value, little-endian, strictly below q), and the kinds of its polynomials (poly_kinds(), uniform_material()).

• The ciphertexts of the threshold MCFE over Ring-LWE (pyfe4ai.schemes.mcfe.ring_lwe_threshold): JSON, tagged over their JSON form, or format 2 of encode_threshold_ciphertext() with what their tags (binary_tag_message()) and the noise seeds (binary_request_digests()) hash; strict reading of both, and the digests of canonical ciphertexts (ciphertexts_digest()).

• Its partial decryptions: values as decimal strings (JSON) or binary words.

A format-2 encoding is unique (a value >= q is refused): no client can re-encode one request to draw a second noise for the same key part.

pyfe4ai.schemes.threshold.codec.binary_material(material, modulus)

material (nested dicts and lists of values) with every polynomial as ceil(bits(q) / 8)-byte little-endian words (values reduced mod q): the binary key shares of the threshold Ring-LWE MCFE.

pyfe4ai.schemes.threshold.codec.strict_mpz(value)

A key-share value as mpz: an int, an mpz or a decimal string (floats and other types are refused rather than truncated).

Raises:

FEKeyError – For any other value.

pyfe4ai.schemes.threshold.codec.is_decimal(value)

Whether value is a decimal string (ASCII digits only), the documented type of the threshold DDH key share values (gmpy2.digits of a value mod q); ints and other types are not.

Return type:

bool

pyfe4ai.schemes.threshold.codec.poly_kinds(material)

The kinds of the polynomials of key material: "bytes" (bytes or bytearray), "values" (a list or tuple of values; only its first element is looked at) and "other" (anything else, e.g. a memoryview). The walk is over polynomials, not values.

Return type:

set

pyfe4ai.schemes.threshold.codec.uniform_material(material, modulus)

material with polynomials of one kind: bytes polynomials decoded to values when it mixes them with value lists (what the Python dealing reads them as), else unchanged.

Raises:

FEKeyError – For polynomials that are neither ("other") or malformed bytes.

pyfe4ai.schemes.threshold.codec.ciphertexts_digest(canonical)

Return the digest of ciphertexts given in canonical form ({nid: values}).

Partial decryptions seed their flooding noise with it, so it must depend only on the values a server computes with, never on how a request encodes them: otherwise re-encoding one request draws fresh noise, and averaging the partials removes it.

Parameters:

canonical (dict)

Return type:

str

pyfe4ai.schemes.threshold.codec.binary_ciphertext_digests(ct, q, eta, ring_n)

(k, d0, d1) of a format-2 ciphertext dict: its batch length and d0 = SHA-256(domain || header || ct0 rows), d1 = SHA-256(domain || ct1) (the values are checked when read: decode_threshold_ciphertext()).

Raises:

ValueError – Unless ct["ct"] is a format-2 ciphertext of these parameters whose batch length is ct["k"].

Parameters:

• ct (dict)

• eta (int)

• ring_n (int)

Return type:

tuple

pyfe4ai.schemes.threshold.codec.binary_tag_message(pp_digest, encoded_label, ct, digests)

What the tag of a format-2 ciphertext covers (HMAC-SHA256 under the client-server key): a domain, the digest of the public parameters (pp_binding() over tmcfe_ring_lwe_binding_fields()), the (chunk) label, the ciphertext’s label_hash code (for an ndarray chunk its layer’s; see _chunk_with_code), the batch length and the digests of binary_ciphertext_digests().

Raises:

ValueError – For a label hash code that is not a byte.

Parameters:

• pp_digest (bytes)

• encoded_label (str)

• ct (dict)

• digests (tuple)

Return type:

bytes

pyfe4ai.schemes.threshold.codec.binary_request_digests(digests)

(ct_digest, key_inputs) (hex) of a request of format-2 ciphertexts from their binary_ciphertext_digests() {nid: (k, d0, d1)}: SHA-256 over the client ids (json.dumps, sorted) with (k, d0, d1) each, and over the ids with d1 only – the values the key part depends on, so the flooding noise is seeded with them (a format-2 encoding is unique: no re-encoding of one request draws fresh noise).

Parameters:

digests (dict)

Return type:

tuple

pyfe4ai.schemes.threshold.codec.check_ciphertext_format(dict_ct, binary)

Refuse ciphertexts of the other format than the public parameters’: JSON ones (ct0, ct1) under binary public parameters, binary ones (ct) under JSON ones.

Raises:

FESchemeError – For a ciphertext of the other format.

Parameters:

• dict_ct (dict)

• binary (bool)

Return type:

None

pyfe4ai.schemes.threshold.codec.read_json_ciphertexts(dict_ct, q, eta, ring_n)

{nid: (k, ct0, ct1)} of JSON ciphertexts, read strictly (canonical_ring_ciphertext()).

Raises:

FESchemeError – For a malformed ciphertext.

Parameters:

• dict_ct (dict)

• q (int)

• eta (int)

• ring_n (int)

Return type:

dict

pyfe4ai.schemes.threshold.codec.read_binary_ciphertexts(dict_ct, k, q, eta, ring_n)

{nid: (k, ct0, ct1)} of format-2 ciphertexts of batch length k (the Python reading of format 2, strict: decode_threshold_ciphertext()).

Raises:

FESchemeError – For a malformed ciphertext.

Parameters:

• dict_ct (dict)

• k (int)

• q (int)

• eta (int)

• ring_n (int)

Return type:

dict

pyfe4ai.schemes.threshold.codec.native_json_inputs(ctx, dict_ct, sk_y, fusion_weight, z_share, eta, ring_n)

JSON ciphertexts read natively for a partial decryption: (nids, ks, packed, ct_digest, key_inputs), the client ids sorted, the digests those of ciphertexts_digest(); None when the Python path must read them (values other than exact ints and plain decimal strings, other layouts – also of the key share sk_y, z_share – and malformed ciphertexts, whose errors it raises). ctx: a ring of the backend on which the threshold kernels run natively (threshold_native).

Parameters:

• dict_ct (dict)

• sk_y (dict)

• fusion_weight (dict)

• eta (int)

• ring_n (int)

Return type:

tuple | None

pyfe4ai.schemes.threshold.codec.partial_values(values, q, binary)

Values of a partial decryption as its format writes them: binary words (ceil(bits(q) / 8) bytes each) or decimal strings.

Parameters:

• values (list)

• binary (bool)

pyfe4ai.schemes.threshold.codec.check_partial_format(partials, ct_format)

Refuse partial decryptions whose w and c_y are not of the public parameters’ format: bytes (binary) or sequences (JSON).

Raises:

FESchemeError – Otherwise.

Parameters:

• partials (list)

• ct_format (str)

Return type:

None

pyfe4ai.schemes.threshold.codec.partial_batch_length(first, partials, ring_n, binary)

The batch length k of partial decryptions: an int in [1, ring_n]; every JSON partial holds at least k values (a shorter one would give a shorter result).

Raises:

FESchemeError – Otherwise.

Parameters:

• first (dict)

• partials (list)

• ring_n (int)

• binary (bool)

Return type:

int

pyfe4ai.schemes.threshold.codec.json_partial_difference(first, partials, q)

c_y - sum w mod q of JSON partial decryptions, value by value.

Parameters:

• first (dict)

• partials (list)

Return type:

list

pyfe4ai.schemes.threshold.codec.binary_partial_difference(first, partials, q, k)

c_y - sum w mod q of binary partial decryptions (k values of ceil(bits(q) / 8) bytes each, strictly below q).

Raises:

FESchemeError – For a malformed partial decryption.

Parameters:

• first (dict)

• partials (list)

• k (int)

Return type:

list

Stores and Caches

Caches and stores of the threshold schemes, and their locks.

• The sums of a replicated key share’s pieces for an enrolled set (share_for_enrolled()), per scheme object (share_cache(), SHARE_CACHE_SIZE).

• The threshold MCFE over Ring-LWE (pyfe4ai.schemes.mcfe.ring_lwe_threshold): the key generator’s sharings of sk_y per weights (WEIGHT_SHARINGS_KEPT) with the label parts issued for each (LABEL_PARTS_KEPT; a label part is handed out only while its sharing is the weights’ current one, checked under the lock), a server’s weight key share parts and its cache of NTT(sk_y).

The stores are attributes of the scheme objects; pickles and copies of a server leave its share_cache() out (without_share_cache()). The module locks guard the several steps of each lookup and eviction, never the sharing or the arithmetic. The locks are process-wide, not per object: a shallow copy (copy.copy) of a key generator or a server shares its stores with the original, and one lock per store container keeps the two consistent. A forked child replaces each lock (the parent’s may be held by another thread; pyfe4ai.core.forksafe.renew_lock()).

pyfe4ai.schemes.threshold.store.SHARE_CACHE_SIZE = 16

Entries kept by a cache of share_for_enrolled() (per scheme object).

pyfe4ai.schemes.threshold.store.SHARE_CACHE_ATTR = '_enrolled_share_cache'

The attribute of a scheme object holding its share_cache().

pyfe4ai.schemes.threshold.store.share_cache(obj)

The share_for_enrolled() cache of scheme object obj (created on first use; of two threads using it first, both get the one stored first).

Return type:

OrderedDict

pyfe4ai.schemes.threshold.store.without_share_cache(state)

state, a server’s __dict__ (a copy) for a pickle or a copy, without its share_cache(): the cache keeps the key shares callers passed in and their sums, which a pickle or copy of the server does not carry (they are summed again on use). Also applied when a state is loaded, so that pickles of earlier versions, which hold the cache, load without it.

Parameters:

state (dict)

Return type:

dict

pyfe4ai.schemes.threshold.store.cached_share(cache, key, dk)

The sum kept in cache under key for the key share dk (the same object, not only the same id), made the most recently used; None if there is none.

Parameters:

• cache (OrderedDict)

• key (tuple)

• dk (dict)

pyfe4ai.schemes.threshold.store.keep_share(cache, key, dk, out)

Keep the sum out of key share dk in cache under key; the least recently used beyond SHARE_CACHE_SIZE are dropped.

Parameters:

• cache (OrderedDict)

• key (tuple)

• dk (dict)

Return type:

None

pyfe4ai.schemes.threshold.store.WEIGHT_SHARINGS_KEPT = 64

Weights whose shares of sk_y a key generator keeps (least recently used out): a label part for weights no longer kept comes with a new share set, which servers holding the old weight part refuse until given the new one.

pyfe4ai.schemes.threshold.store.LABEL_PARTS_KEPT = 16

Labels whose label parts a key generator keeps per sharing of sk_y (least recently used out; the servers of one label get the same shares while it is kept). A label part asked for again after that is a new sharing of the same terms (same share set and noise key) with another sharing_id: combiners refuse partial decryptions of the two sharings (MixedSharingsError), and the servers then fetch the label’s parts again, all from the new sharing.

pyfe4ai.schemes.threshold.store.weight_entry(owner, weights_id, make)

The key generator owner’s sharing of sk_y for the weights weights_id (owner.dict_weight_shares), made by make() on first use and made the most recently used; the least recently used beyond WEIGHT_SHARINGS_KEPT are dropped with their label parts. Of two threads making it, both return the one kept.

Parameters:

weights_id (str)

Return type:

dict

pyfe4ai.schemes.threshold.store.label_parts(owner, weights_id, ident, current_entry, make, attempts)

The label parts ident of the weights’ current sharing of sk_y (current_entry(), weight_entry()): kept with that sharing (evicted with it, without a scan of the other keys; the last LABEL_PARTS_KEPT labels), made by make(entry) on first use. A label part, cached or made, is handed out only while its sharing is the weights’ current one (checked under the lock): one whose sharing another thread evicted meanwhile is made again for the weights’ new share set, so none is issued for a sharing the key generator no longer hands out.

Raises:

FESchemeError – If the sharing was evicted during each of attempts (more than WEIGHT_SHARINGS_KEPT weights in use at once).

Parameters:

• weights_id (str)

• ident (str)

• attempts (int)

Return type:

dict

pyfe4ai.schemes.threshold.store.keep_weight_share(owner, key, share, kept)

Keep the weight key share part share of server owner under key ((weights_id, share_set_id)); the least recently used beyond kept are dropped.

Parameters:

• key (tuple)

• share (dict)

• kept (int)

Return type:

None

pyfe4ai.schemes.threshold.store.has_weight_share(owner, key)

Whether server owner keeps a weight key share part under key.

Parameters:

key (tuple)

Return type:

bool

pyfe4ai.schemes.threshold.store.weight_share(owner, key)

The weight key share part server owner keeps under key, or None.

Parameters:

key (tuple)

pyfe4ai.schemes.threshold.store.NTT_CACHE_SIZE = 64

NTT(sk_y) of the shares of kept weight parts a server keeps (cached_ntt()).

pyfe4ai.schemes.threshold.store.cached_ntt(owner, poly, ctx, make)

NTT(poly) in the native ring ctx, kept by server owner across labels (make() on first use; the last NTT_CACHE_SIZE).

Return type:

bytes

Servers and Combiners

Server and combiner logic shared by the threshold schemes.

Trust model of every threshold scheme: decryption servers are honest-but-curious. Fewer than t of them learn nothing beyond the result, but nothing proves a partial decryption correct, so a server that deviates can change the result undetected – unless the combiner asks for partial decryptions for several enrolled sets and combine_consistently() compares them.

• A server: its policy for Shamir key shares with t < s (legacy_shamir_policy()), the checks before a partial decryption (check_key_share_server(), check_request()), how it sums its share for an enrolled set (enrolled_share_options() for share_for_enrolled()) and the flooding noise of the LWE threshold layers, a function of the server’s noise key and the request (noise_seed(); flooding_noise(), flooding_poly(), uniform_flooding_poly()).

• A combiner: the checks of a set of partial decryptions (validate_partial_decryptions()) and the combination of one or several enrolled sets (combine_consistently(), combine_elementwise()).

pyfe4ai.schemes.threshold.roles.check_key_share_server(server_id, dk, pp, constructions)

Raise unless key share dk is server server_id’s and of the sharing and a threshold construction of pp among constructions (check_served_sharing()).

Raises:

FESchemeError – For another server’s key share, another sharing or an unknown construction.

Parameters:

• server_id (str)

• dk (dict)

• pp (dict)

• constructions (dict)

Return type:

None

pyfe4ai.schemes.threshold.roles.check_request(server_id, dk, lst_sid_enrolled, threshold, fusion_weight)

Raise unless server server_id may answer for lst_sid_enrolled (validate_enrolled()) and fusion_weight are the weights its key share dk was derived for.

Raises:

FESchemeError – Otherwise.

Parameters:

• server_id (str)

• dk (dict)

• lst_sid_enrolled (list)

• threshold (int)

Return type:

None

pyfe4ai.schemes.threshold.roles.enrolled_share_options(server)

The keyword arguments of share_for_enrolled() for a server object: its cache of sums, its legacy_shamir policy and the security_profile of its public parameters.

Return type:

dict

pyfe4ai.schemes.threshold.roles.noise_seed(dk, *context)

The seed of a partial decryption’s flooding noise: key share dk’s noise_key (secret, per server) followed by the JSON list of context – what the key part depends on (the ciphertext values or the label), the tag of the server’s share for the enrolled set, and the digest of the server’s own public parameters (the key share’s pp_binding, checked) – so that a request for the same key part always draws the same noise, and under other public parameters another noise.

Parameters:

dk (dict)

Return type:

bytes

pyfe4ai.schemes.threshold.roles.flooding_noise(sigma, rng=None)

Sample e <- D_{Z, sigma} truncated to |e| <= 12 sigma.

Uses the arbitrary-precision sampler: sigma is far wider than a double’s mantissa, and scaling a 53-bit normal by it would leave the low bits of e deterministic.

Parameters:

• sigma (int) – Width.

• rng (default: None) – Bit source (default: OS CSPRNG). An XofRandom makes the sample a function of its seed.

Return type:

int

pyfe4ai.schemes.threshold.roles.flooding_poly(sigma, ring_n, rng)

ring_n samples of D_{Z, sigma} cut at GAUSSIAN_TAIL_CUT sigma, drawn in order.

Parameters:

• sigma (int)

• ring_n (int)

Return type:

list

pyfe4ai.schemes.threshold.roles.uniform_flooding_poly(bits, ring_n, seed)

ring_n integers uniform on [-2^bits, 2^bits), a function of seed: coefficient i is block i of ceil((bits + 1) / 8) big-endian bytes of SHAKE-256 over a domain tag, the seed’s length and the seed, its low bits + 1 bits, minus 2^bits.

Parameters:

• bits (int)

• ring_n (int)

• seed (bytes)

Return type:

list

pyfe4ai.schemes.threshold.roles.uniform_flooding_material(seed)

The SHAKE-256 input of uniform_flooding_poly() for seed (the native backend draws the noise from it).

Parameters:

seed (bytes)

Return type:

bytes

pyfe4ai.schemes.threshold.roles.SERVER_IDS = "a server's id and the enrolled servers must be server ids (str or int; numpy integers are read as int)"

The FEValidationError of a server whose own id, or an entry of the enrolled set it is asked to answer for, is not a server id (enrolled_ids()).

pyfe4ai.schemes.threshold.roles.enrolled_ids(server_id, lst_sid_enrolled)

The enrolled set server server_id is asked to answer for, as a list of server ids: numpy integer scalars read as the int they equal (as_id(); list(rng.choice(lst_sid, t)) gives them), so that the partial decryption carries ids the combiner accepts. The membership checks (validate_enrolled()) follow.

Raises:

FEValidationError – SERVER_IDS unless server_id and every entry of lst_sid_enrolled (an iterable) are server ids after that reading (a float, a bool, None, bytes, a tuple are refused here rather than by the combiner; the message holds none of the values).

Return type:

list

pyfe4ai.schemes.threshold.roles.validate_enrolled(sid, lst_sid, lst_sid_enrolled, threshold)

Check that sid may produce a partial decryption for lst_sid_enrolled.

Parameters:

• sid (str) – Identifier of the server producing the partial decryption.

• lst_sid (list[str]) – Ordered list of all decryption-server identifiers.

• lst_sid_enrolled (list[str]) – Servers whose shares will be combined.

• threshold (int) – Minimum number of shares needed for reconstruction.

Return type:

None

pyfe4ai.schemes.threshold.roles.validate_partial_decryptions(dict_ct_prime, threshold)

Check a set of partial decryptions before combining them.

Each partial decryption carries the server id that produced it and the enrolled set its Lagrange coefficient was computed for; the contributors must be exactly that enrolled set, each appearing once, and number at least threshold.

Parameters:

• dict_ct_prime (dict) – Mapping of server ids to partial decryptions.

• threshold (int) – Minimum number of shares needed for reconstruction.

Raises:

• FEValidationError – If a partial decryption’s sid is not a server id (a str or an int, is_id(); a numpy integer is read as the int it equals, as_id()) or its lst_sid_enrolled not a list (or tuple) of server ids (the message holds none of the values).

• FESchemeError – For too few, duplicate or mismatched partial decryptions.

Return type:

None

pyfe4ai.schemes.threshold.roles.partial_groups(partials)

Partial decryptions as a list of groups {sid: partial}, one per enrolled set.

Accepts one group (a mapping) or several (a list or tuple of mappings).

Return type:

list

pyfe4ai.schemes.threshold.roles.DISAGREEING_PARTIALS = 'partial decryptions disagree on the ciphertexts they decrypted'

The error of a group of partial decryptions that disagree on the ciphertexts they decrypted (raised by every threshold combiner, for one value and for an element of an ndarray alike).

pyfe4ai.schemes.threshold.roles.combine_consistently(partials, combine_group)

Combine every group of partial decryptions and require a single result.

Servers are assumed honest-but-curious: nothing proves a partial decryption correct, and one server can shift the result of every group it belongs to. With more than t servers, partial decryptions for several enrolled sets (a server answers once per set) detect such a server – though not which one – unless it is in every group: to detect any one faulty server, leave every server out of some group, e.g. use the t + 1 subsets of size t of t + 1 servers.

Parameters:

• partials – {sid: partial} for one enrolled set, or a list of them.

• combine_group – Function combining one group into a result.

Raises:

FESchemeError – If the groups give different results.

pyfe4ai.schemes.threshold.roles.combine_elementwise(dict_ndarray_ct, combine)

Combine element-wise ndarray partial decryptions into object arrays.

Parameters:

• dict_ndarray_ct – {sid: [array per layer]} for one enrolled set, or a list of them (see partial_groups()).

• combine – combine(groups, layer, index), combining the partials of one element (a list of {sid: partial}).

Raises:

FESchemeError – If the servers’ outputs differ in structure, an element does not decrypt (out of range), or the partial decryptions of an element disagree on the ciphertexts (the error and message of combine_decrypt).

Return type:

list

Flooding Accounting

Accounting of the statistical flooding of the threshold LWE layers.

mife/lwe_threshold and mcfe/ring_lwe_threshold flood every partial decryption with e_k <- D_{Z, sigma_f}, so that it can be simulated from the result: real and simulated partials differ by a shift c of the noise, the honest part of the decryption noise (|c| <= B). The flooding_accounting entry of their key generator config chooses how sigma_f is sized against that shift:

"per-sample" (default)

sigma_f = 2^stat_param B: statistical distance below 2^-stat_param per flooded coefficient, cut at GAUSSIAN_TAIL_CUT sigma_f, no limit on the number of partial decryptions. This is the guarantee the standard profile documents.

"kl" (opt-in; needs max_partial_decryptions and t = s)

A bound for the adversary’s whole view of a run in which every server produces at most Q = max_partial_decryptions partial decryptions: N = s Q k flooded coefficients (k per partial decryption). With lambda = stat_param the Hellinger distance between the real and the simulated view stays below 2^(-lambda/2), split as

• KL(D + c || D) = c^2 / (2 sigma^2) per coefficient, adding up over the adaptive run (chain rule): sigma_f = ceil(sqrt(B^2 N 2^lambda)) gives KL <= 2^-(lambda+1), HD <= sqrt(KL / 2) <= 2^(-lambda/2) / 2;

• the tail cut, on both sides: HD^2 <= N Pr[|D| > T sigma], at most 2^-(lambda+6) with the cut T of kl_tail_cut() (16 for N = 2^53, lambda = 128);

• the sampler, on both sides: HD^2 <= N delta with the rounded sampler’s deviation delta <= 2^4.3 sigma 2^-P per sample (an estimate of its Box-Muller grid, not a proof) at P = bits(sigma) + lambda + log2 N + 11 bits (kl_sampler_precision()), or FACCT’s 2^-185; at most 2^-(lambda+6).

By the triangle inequality HD <= (1/2 + 2/8 + 2/8) 2^(-lambda/2). In the bit-security framework of Micciancio and Walter (EUROCRYPT 2018) that keeps lambda - 6.85 bits for decision games (Hellinger replacement, Yasunaga, ITC 2021, Thm. 5), whatever the adversary’s running time; read conventionally it is a total statistical distance of about 2^-(lambda+2)/2 (2^-65 at lambda = 128). A different and weaker guarantee than "per-sample", valid only for the first Q partial decryptions of every server.

The servers count against Q through a PartialDecryptionBudget that the deployment passes to each server’s crypto object (partial_budget); without one they refuse. Where the count lives (one object, shared by every object, process and restart of the server, persisted) is the deployment’s decision: the library only enforces it per budget object.

Both accountings assume that an honest partial differs from its simulation by exactly the decryption noise. With Shamir shares and Lagrange coefficients mod q that holds only for t = s (every enrolled set is then all servers, and the multipliers are 0 or 1); for t < s some enrolled sets make the shift a rational multiple (r / d) nu, and d times a partial reveals nu mod d whatever the width. "kl" therefore refuses t < s. (The default accounting does not check this.)

The replicated sharing (sharing="replicated", the default for t < s) also has multipliers 0 or 1, but "kl" is not enabled for it: the key generators accept "kl" with the Shamir sharing at t = s only (and, for mcfe/ring_lwe_threshold, with the Gaussian flooding, its default under "kl"). mife/lwe_threshold stays refused under standard with either accounting.

The flooding noise is drawn by the pinned FLOODING_SAMPLER (the MPFR rounded Gaussian), whatever the sampler selected elsewhere, at kl_sampler_precision() bits, which is never below the sampler’s own bigint_precision().

pyfe4ai.schemes.threshold.kl.kl_flooded_samples(servers, max_partial_decryptions, coefficients)

N: flooded coefficients of a run, servers * max_partial_decryptions * coefficients.

Parameters:

• servers (int)

• max_partial_decryptions (int)

• coefficients (int)

Return type:

int

pyfe4ai.schemes.threshold.kl.kl_flooding_width(noise_bound, samples, stat_param)

Smallest integer sigma with samples * noise_bound^2 / (2 sigma^2) <= 2^-(stat_param + 1).

Parameters:

• noise_bound (int)

• samples (int)

• stat_param (int)

Return type:

int

pyfe4ai.schemes.threshold.kl.kl_divergence_log2(noise_bound, samples, sigma)

log2 of the KL bound samples * noise_bound^2 / (2 sigma^2).

Parameters:

• noise_bound (int)

• samples (int)

• sigma (int)

Return type:

float

pyfe4ai.schemes.threshold.kl.gaussian_tail_log2(cut)

An upper bound on log2 Pr[|Z| > cut] for a standard normal Z (Mills’ ratio: sqrt(2 / pi) exp(-cut^2 / 2) / cut), cut >= 1.

Parameters:

cut (float)

Return type:

float

pyfe4ai.schemes.threshold.kl.kl_tail_cut(samples, stat_param, sigma=None)

Smallest integer cut T >= 12 with N Pr[|D| > T sigma] <= 2^-(stat_param + 6).

The bound is evaluated at T - 1 / sigma (rounding) and doubled (the discrete Gaussian’s tail; the rounded one needs no factor).

Parameters:

• samples (int)

• stat_param (int)

• sigma (int | None, default: None)

Return type:

int

pyfe4ai.schemes.threshold.kl.kl_sampler_precision(sigma, samples, stat_param)

Bits of the rounded Gaussian sampler for "kl": bits(sigma) + stat_param + ceil(log2 samples) + 11, and at least the sampler’s default bits(sigma) + BIGINT_GUARD_BITS.

Parameters:

• sigma (int)

• samples (int)

• stat_param (int)

Return type:

int

pyfe4ai.schemes.threshold.kl.facct_max_log_samples(stat_param)

Largest log2 N for which FACCT’s deviation, summed over N samples, stays below 2^-(stat_param + 6).

Parameters:

stat_param (int)

Return type:

int

class pyfe4ai.schemes.threshold.kl.KLFlooding(pp, coefficients)

Bases: object

Flooding parameters of "kl" public parameters, as the servers use them.

Parameters:

• pp (dict) – Public parameters with flooding_accounting = "kl".

• coefficients (int) – Flooded coefficients per partial decryption.

Raises:

FESchemeError – If pp has t != s or a tail cut other than kl_tail_cut() derives.

check_sampler()

Raise unless the flooding sampler (FLOODING_SAMPLER, pinned) covers N samples.

Raises:

FEValidationError – If it were FACCT and log2 N exceeded facct_max_log_samples().

Return type:

None

sample(count, rng)

count flooding values: D_{Z, sigma_f} cut at tail_cut sigma_f, in order.

Parameters:

count (int)

Return type:

list

pyfe4ai.schemes.threshold.kl.kl_flooding(pp, coefficients)

KLFlooding of pp, or None for the per-sample accounting.

Parameters:

• pp (dict)

• coefficients (int)

Return type:

KLFlooding | None

pyfe4ai.schemes.threshold.kl.flooding_samples(sigma, count, rng, tail_cut=12, precision=None)

count samples of D_{Z, sigma} cut at tail_cut sigma, drawn in order by FLOODING_SAMPLER (precision bits, default bigint_precision()).

Parameters:

• sigma (int)

• count (int)

• tail_cut (int, default: 12)

Return type:

list

class pyfe4ai.schemes.threshold.kl.PartialDecryptionBudget(limit, used=0)

Bases: object

How many partial decryptions a server may still produce under "kl".

The deployment creates one per server and passes it to every crypto object that answers for that server (partial_budget in the crypto config); its limit may not exceed the public parameters’ max_partial_decryptions. The count only grows, and consume() checks and increments it as one step under a lock, so the threads of a process can share a budget. Every partial decryption a server produces counts, repeated ones too; refused requests do not. 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 it, for instance by subclassing with an atomic, durable consume() and starting from the stored used. A budget cannot be copied or pickled (a copy would count separately), and check() and consume() refuse to run in another process than the one that made it: after os.fork() the parent and the child would each count from the copied used and together exceed the limit. Make the budget in the process that answers for the server (a forked child gets a new lock for the copy it holds, so reading remaining there does not block).

Parameters:

• limit (int) – At most max_partial_decryptions of the public parameters.

• used (int, default: 0) – Partial decryptions already produced (0 <= used <= limit).

Raises:

FEValidationError – For non-integer or out-of-range values.

property limit: int

property used: int

property remaining: int

check(count=1)

Raise unless count more partial decryptions fit (consumes nothing).

Raises:

FESchemeError – If they would exceed the limit, or in another process than the one that made the budget.

Parameters:

count (int, default: 1)

Return type:

None

consume(count=1)

Account for count partial decryptions about to be produced.

Raises:

FESchemeError – If they would exceed the limit (nothing is consumed then), or in another process than the one that made the budget.

Parameters:

count (int, default: 1)

Return type:

None

pyfe4ai.schemes.threshold.kl.server_budget(pp, budget, flood)

The budget a "kl" server counts against: budget, checked against pp.

Raises:

• FESchemeError – If there is none (the deployment must decide where a server’s count lives).

• FEValidationError – If it is not a PartialDecryptionBudget or allows more than max_partial_decryptions.

Parameters:

• pp (dict)

• flood (KLFlooding)