RNS modulus for the Ring-LWE schemes: security review ===================================================== Question: can the NTT-friendly prime ``q`` of the Ring-LWE schemes be replaced by a product ``q = q1 q2`` of distinct NTT-friendly primes (``q_i = 1 mod 2n``), so that the native code works in two u64 residues instead of u128 words, without invalidating BMMS21's proofs or PyFE4AI's own derivations? References: * **BMMS21**: J. M. Bermudo Mera, A. Karmakar, T. Marc, A. Soleimanian, "Efficient Lattice-Based Inner-Product Functional Encryption", PKC 2022; full version `ePrint 2021/046 `__. * **ACFGU18**: M. Abdalla, D. Catalano, D. Fiore, R. Gay, B. Ursu, "Multi-Input Functional Encryption for Inner Products: Function-Hiding Realizations and Constructions without Pairings", CRYPTO 2018; full version `ePrint 2017/972 `__. Summary ------- .. list-table:: :header-rows: 1 :widths: 30 22 48 * - scheme - verdict - rests on * - ``sife/ring_lwe`` (selective, Sec. 4) - safe - Sec. 4.1 games; one step (G6) needs ``gcd(Delta, q) = 1`` or the shift argument below * - ``mife/ring_lwe`` (ACFGU18 compiler) - safe - ACFGU18 Sec. 3.3 / Fig. 4 works over any ``Z_L`` * - ``mcfe/ring_lwe`` (identity-based MCFE) - safe - BMMS21 Sec. 6, Thm. 5, App. D.2: additive group ``Z_q`` only * - ``mcfe/ring_lwe_decentralized`` (GDSum) - safe - BMMS21 App. D.4: masks cancel in ``Z_q``, any ``q`` * - ``mcfe/ring_lwe_threshold`` (own design) - safe, the default since 2026-10 (section 10) - Shamir over ``Z_q`` is Shamir over each ``F_{q_i}`` (CRT) when every ``q_i > s`` (checked); replicated sharing, flooding, label hash and decoding are independent of the factorisation * - ``sife/fullysec_ring_lwe`` (adaptive, Sec. 5) - **not safe without a new argument** - Thm. 2 (Ring-LHL) and App. B are stated and proved for prime ``q`` The prototype (``ring_modulus="rns"``) was first offered for MIFE, MCFE and dMCFE Ring-LWE only (opt-in there); the threshold MCFE takes it since the re-review of section 10 (four factors at its 212 to 218 bits) and has it as its default (``ring_modulus="prime"`` selectable). The SIFE key generators (``sife/ring_lwe``, ``sife/fullysec_ring_lwe``) refuse it. 1. Hardness of RLWE / mhe-RLWE with a composite ``q`` ----------------------------------------------------- * Concrete security, as PyFE4AI uses it. ``RING_LWE_128_LOG_Q`` was produced with the lattice estimator for LWE with ``q = 2^k`` (``tools/params/estimate_ring_lwe.py``), i.e. already for a composite modulus: the attacks it models (primal uSVP, BDD, hybrids, dual) see ``q`` only as a number. The 128-bit bound is a bound on ``log2 q`` whatever the factorisation, which is also how the Homomorphic Encryption Standard tables are read for the RNS moduli of SEAL / OpenFHE. BMMS21's own implementation uses a product of three primes (Sec. 7.1, "CRT representation", and the CRT moduli of Table 1) and estimates it the same way. Re-checked for the prototype's composite moduli by running the estimator on the exact ``q`` (section 9). * Asymptotic reductions. BMMS21 cites LPR10 (App. A.3, Theorem 6), stated for a prime ``q = 1 mod 2n`` bounded by ``poly(n)``. PyFE4AI's moduli are not ``poly(n)``-bounded in that theorem's sense either, and its derivation never used Theorem 6. Decision RLWE is hard for every modulus by Peikert, Regev, Stephens-Davidowitz (STOC 2017, "Pseudorandomness of Ring-LWE for any ring and modulus"). * Attacks through the factors. Reducing a sample ``(a, a s + e)`` mod ``q1`` gives RLWE mod ``q1`` with the same error, i.e. a smaller modulus-to-noise ratio: harder, not easier. The ring ``x^n + 1`` splits completely mod each ``q_i`` exactly as it does mod the prime ``q`` used today, so the known "weak PLWE instance" conditions (roots of small order) are not met either. * Theorem 1 (mhe-RLWE from RLWE, Sec. 3.1). The reduction adds ``a r' + f'`` to the RLWE sample and argues with Gaussians over ``Z^(n + n l)`` (Lemma 1); a uniform ``b`` stays uniform in ``R_q`` for any ``q``. Nothing depends on ``q`` being prime. 2. The selective IPFE (Sec. 4, Theorem 3) ----------------------------------------- Games of Fig. 2: * G0 -> G1, G2 -> G3, G4 -> G5: algebraic identities in the commutative ring ``R_q``; any ``q``. * G1 -> G2: mhe-RLWE (section 1); G5 -> G6: RLWE with secret ``s*`` in two samples ``(a, a s* + e*)``, ``(u, u s* + f*)``: any ``q``. No step needs ``a`` or ``u`` to be a unit. * G3 -> G4: Lemma 1 on ``Z^n`` (the columns of ``S, E, F``); ``q`` does not appear. * G6, the last step: the paper writes ``u'' alpha_i + Delta x^b_i = Delta((Delta^-1 u'' + b) alpha_i + x^0_i)`` with "``Delta^-1`` the inverse of ``Delta = floor(q / K)`` in ``Z_q``", which needs ``gcd(Delta, q) = 1`` (automatic for a prime ``q``). The inverse is not needed: ``u'' alpha_i + Delta x^b_i = (u'' + b Delta 1_R) alpha_i + Delta x^0_i``, and ``u'' -> u'' + b Delta 1_R`` is a bijection of ``R_q`` that keeps ``u''`` uniform; ``u''`` appears nowhere else, so the view does not depend on ``b``. With the batching of Remark 1 the same shift is applied per batch position ``k`` (``u''_k + b Delta 1^k_R``). The prototype also enforces ``gcd(Delta, q) = 1`` (a failure has probability about ``2 / 2^39``; the next prime is taken), so the paper's text applies verbatim. * Sec. 2.1's isomorphism ``R_q = Z_q^n`` holds for ``q = q1 q2`` by CRT, since ``x^n + 1`` splits into distinct linear factors mod each ``q_i``. * Correctness (Sec. 4.2, Lemma 2) is a bound on integers: ``||noise||_inf < floor(q / 2K)``, so ``Dec2`` (centred lift, rounding to a multiple of ``Delta``) decodes for any ``q`` of that size. The Gaussian widths of Sec. 4.2 do not depend on ``q``. 3. MIFE compiler (ACFGU18 Sec. 3.3, Fig. 4, Theorem 3; BMMS21 Sec. 6) --------------------------------------------------------------------- ACFGU18 builds the compiler for an IPFE with a linear encoding into a group of order ``L`` (Property 1) and linear encryption (Property 2), for any integer ``L``; they instantiate it with an RSA modulus ``N``. Here ``L = q``: * the pads ``u_i`` are uniform in ``Z_q^m`` (``rand_uniform_vector``, ``randrange(q)``): a one-time pad in the additive group, perfect for any ``q``; * ``E(gamma, noise) = Delta gamma + noise mod q`` is linear mod ``q`` (``Delta (gamma mod q) = Delta gamma mod q``), and ``Add(Enc(x), x') = Enc(x + x' mod q)`` holds with identical distributions; * the ``3X`` condition of footnote 12 concerns the Gaussian widths, not ``q``. 4. MCFE compiler (BMMS21 Sec. 6, Theorem 5, App. D.2) ----------------------------------------------------- The random oracle is programmed as ``H(u'_i, l') = r_{i,l'} - u_i`` in ``Z_q^k``: uniform for any ``q``. ``label_pad`` reduces blocks of ``bits(q) + 128`` bits mod ``q`` (``hash_to_zq_vector``): statistically ``2^-128``-close to uniform per coefficient for any ``q``, as for the prime. The public ``a`` is expanded the same way (``seeded_polynomial``). 5. Decentralised MCFE (BMMS21 App. D.4, Theorems 7 and 8) --------------------------------------------------------- GDSum masks ``M_i = sum_{j > i} PRF(K_ij) - sum_{j < i} PRF(K_ji)`` cancel in ``Z_q`` and each is uniform when one pairwise key is unknown: additive group only, any ``q``. 6. Threshold MCFE (``mcfe/ring_lwe_threshold``, PyFE4AI's design) ----------------------------------------------------------------- This section is the first review; section 10 supersedes its conclusion. * Shamir over ``Z_q`` with ``q = q1 q2``: by CRT ``Z_q = F_q1 x F_q2``, and uniform polynomial coefficients mod ``q`` are independent uniform coefficients mod each ``q_i``, so the sharing is two independent field sharings. Reconstruction (``lagrange_coefficient_at_zero``) inverts differences ``x_m - x_k`` of the points ``1..s``; privacy of ``t - 1`` shares needs the Vandermonde matrix on ``{0} union S`` to be invertible: both hold when every ``q_i > s`` (all points and differences are units). The Lagrange coefficients ``lambda_k`` are units, so each ``w_k = lambda_k (...) + e_k`` is distributed per prime as in the field case. * Flooding: ``e_k <- D_{Z, 2^kappa B}`` smudges an integer noise of norm ``B``; the argument and the decoding budget are over the integers. * So RNS would be sound under ``s < min q_i``, but the flooded ``q`` has 212 bits at ``ring_n`` 8192 (at least four primes below 2^62), and three quarters of a partial decryption is the flooding sampler. Not adopted; the key generator refuses ``ring_modulus="rns"``. 7. Adaptive IPFE (``sife/fullysec_ring_lwe``, Sec. 5, App. C, App. B) --------------------------------------------------------------------- * Theorem 2 (Ring-LHL) is stated for "``x^n + 1`` splits into ``n`` linear factors modulo a prime ``q``"; its proof (App. B, Lemmas 6-9) counts ideals of ``R_q`` and the fraction ``2^n q^(-eps n) (q^mk / ((q^m - 1)...(q^m - q^(k-1))))^n`` of bad matrices over the field. With ``q = q1 q2`` the ideal lattice and the count change (ideals are pairs of ideals mod ``q1`` and ``q2``). * App. C uses that some element of ``a`` / ``u`` is invertible and that ``f_{a,u}`` is not surjective only if ``u = s a`` for a scalar ``s in Z_q``; over ``Z_q1 x Z_q2``, ``u`` can be proportional to ``a`` modulo one prime only, a larger bad set (the implementation's ``_invertible`` / ``independent_at_every_slot`` checks are written for the field case). * The parameters (``sigma' ~ q^(2/m)``) also depend on ``q``. * A composite-modulus Ring-LHL would be a new result (or a reduction to a regularity lemma for composite moduli whose hypotheses would have to be checked against App. C). Until then: prime ``q`` only. 8. PyFE4AI's derivations and checks ----------------------------------- * ``bmms21_selective_parameters`` derives the lower bound ``L = 2 p (noise + 1) + 1`` as before; the RNS modulus is ``q = q1 q2 >= L`` with ``q1`` the largest NTT prime below ``sqrt(L)``, ``q2`` the smallest NTT prime with ``q1 q2 >= L`` (so ``q1 < q2``, both ``= 1 mod 2n``, both below 2^62), then ``q2`` advanced until ``gcd(floor(q / p), q) = 1``. ``q`` exceeds the prime of the default path by a factor below ``1 + 2^-16`` (``1 + 2^-25`` at 80 bits) and has the same bit length in every configuration tested (``ring_n`` 2048 to 8192, 61 to 88 bits). The 128-bit check (``check_ring_lwe``, ``ring_lwe_auto_n``) reads the same table with this ``q``; ``standard`` picks the same ring dimension. * NTT root. ``_find_primitive_root`` searched ``g^((q - 1) / 2n)`` and accepted it if ``root^(2n) = 1`` and ``root^n != 1``. For a prime this means ``root^n = -1``; for a composite ``q`` it does not (a root ``= 1`` mod one prime passes), and ``g^((q - 1) / 2n)`` rarely has order dividing ``2n``. The check is now ``root^n = -1 mod q`` (the same roots for every prime ``q``), and for an RNS modulus the root is the CRT of the per-prime roots (registered from ``q_factors``, checked: product ``= q``, each factor prime and ``= 1 mod 2n``). ``root^n = -1`` mod each ``q_i`` makes ``root^2`` of order ``n`` mod each prime, so the negacyclic NTT is a ring isomorphism mod ``q``. * Parameter cache: ``_param_verification`` recomputes ``q`` and its factors from the configuration and compares them; the record carries ``"ring_modulus": "rns"`` and ``q_factors``, absent for the default (whose records are unchanged), and is kept in ``param-rns.json`` beside the prime's ``param.json``. A prime record never verifies for an RNS configuration and vice versa; a planted cache cannot choose the factors. The factors are public (there is no trapdoor in them; 40-bit factors of an 80-bit ``q`` are found instantly anyway). * Formats: ciphertexts stay in the standard representation (coefficients in ``[0, q)``): binary format 1 (``wb = ceil(bits(q) / 8)``) and the JSON decimal strings are unchanged; the native code converts residues at the boundary (Garner). The public parameters gain ``q_factors`` (RNS only). 9. 128-bit check of the composite moduli ---------------------------------------- `Lattice estimator `__ (commit 53da598), the attacks and settings of ``tools/params/estimate_ring_lwe.py`` (MATZOV cost model, primal uSVP / BDD / BDD hybrid, dual / dual hybrid; secret and errors ``D_{Z, sigma}``, unlimited samples, ``jobs=1``), run with ``tools/params/estimate_rns_modulus.py`` on the exact moduli of the FL configurations (3 or 10 clients, ``eta = 1``, ``bound_y = 1``; ``sigma`` the RLWE width of Sec. 4.2 that the table is read at): .. list-table:: :header-rows: 1 * - ``ring_n`` - clients, ``bound_x`` - ``sigma`` - ``q`` bits (factors) - table bound - log2 cost, RNS ``q`` - log2 cost, prime ``q`` * - 4096 - 3, 100 - 8.22 - 80 (40 + 40) - 111 - 189.4 - 189.4 * - 4096 - 3, 2 - 8.22 - 63 (32 + 32) - 111 - 251.8 - 251.8 * - 4096 - 10, 100 - 8.22 - 86 (43 + 43) - 111 - 174.2 - 174.2 * - 8192 - 3, 100 - 8.27 - 82 (41 + 41) - 218 - 407.4 - 407.4 The estimator gives the composite modulus and the prime of the same size the same cost (it reads ``q`` only through its size), all far above 128 bits. 10. Threshold MCFE re-review (2026-10) -------------------------------------- Since section 6 the default flooding is uniform (integer, native) and the default sharing for ``t < s`` is replicated (multipliers 0 and 1); the flooded ``q`` (212 to 218 bits under ``standard``) is now the product of ``k = max(2, ceil(bits / 60))`` NTT primes, but ``k = 4`` (factors up to 62 bits) up to 248 bits, the most the native ring holds, with a fifth only where the last would exceed 62 bits (``rns_ntt_modulus_for``, then ``rns_ntt_modulus(..., factors=k)``: ``k - 1`` largest NTT primes below ``L^(1/k)``, the last the smallest with a product ``>= L`` that is none of them, advanced until ``gcd(floor(q / p), q) = 1``; for ``k = 2`` the modulus of the earlier sections). Above 248 bits the modulus has five or more factors and runs on the Python path (the key generator warns; ``ring_modulus="prime"`` stays native below ``2^253``). RNS is the threshold MCFE's default (2026-10, with binary ciphertexts and split key shares; ``ring_modulus="prime"`` selects the prime of earlier versions, whose records stay in ``param.json``). Its moduli have at least three factors (``MIN_RNS_FACTORS``): with two, a flooded ``q`` below ``2^124`` (the ``toy`` profile's, e.g. 115 bits) got the two-prime context of the MIFE / MCFE prototype, which has none of the threshold kernels, and ran on the Python path; with three it runs on the 256-bit ring. The arguments below hold for any number of factors above ``s``. Item by item: * **RLWE hardness, MCFE layer**: sections 1, 3 and 4 (any modulus; the estimator reads ``q`` by size, and ``q`` has the bit length of the prime). * **Shamir sharing** (``t = s``, the default there): CRT, one field sharing per factor; the points ``1..s`` and their differences are units when every ``q_i > s``, which the key generator and every server check (``check_rns_servers``; the factors are about ``2^54``). The Lagrange coefficients are units. * **The Lagrange leak** (the Shamir sharing of the threshold LWE layers with ``t < s``, described in ``SECURITY.md``) concerns the rational multiplier ``M`` of the decryption noise on the integers: 0 or 1 for the replicated sharing and 1 for Shamir with ``t = s``, whatever the factorisation of ``q``. * **Replicated and seeded sharing**: additive in ``Z_q`` (pieces uniform mod ``q``; seeded pieces ``hash_to_zq_vector`` mod ``q``, within ``2^-130`` of uniform per value for any ``q``). * **Flooding**: the smudging bound (uniform: ``|nu| / 2^(tau + 1)`` per value; Gaussian: the statistical distance of ``D_{Z, sigma_f}`` and its shift by ``nu``) is a statement about integers; reducing mod ``q`` is a function of the sum and cannot increase the statistical distance. The decoding budget ``s 2^tau + B < q / (2p)`` uses the size of ``q`` only. * **Label hash**: ``"shake128-rejection"`` samples exactly uniformly on ``[0, q)`` for any ``q``; ``"shake256-wide"`` within ``2^-128`` per value. * **Binding and noise derivation**: ``q`` is in ``pp_binding`` (and with it the noise context); ``q_factors`` is added where present, so key shares of a prime ``q`` and of an RNS ``q`` never serve each other's public parameters, and the digests of prime public parameters are unchanged. Construction ids are unchanged (the sharing and flooding constructions are the same); the parameter records carry ``ring_modulus`` and ``q_factors`` and are recomputed and compared on load; RNS records live in ``param-rns.json``, beside the prime's ``param.json`` (alternating the configurations in one folder loads both). * **FACCT and the Gaussian flooding sampler**: integer samples, independent of ``q``; the native kernels reduce them mod each factor. * **NTT root**: the CRT of the factors' roots with ``root^n = -1`` mod every factor (section 8); the native ring runs one 64-bit NTT per factor and returns standard values, so every result equals the Python code on the composite ``q`` (``tests/threshold/test_threshold_rns.py`` compares NTTs, products, encryption, key shares and partial decryptions). Measured (standard profile, 3 clients, 10^4 values, ``s = t = 3``, 1 thread, host): NTT of 8192 coefficients 1.33 ms (256-bit words) -> 0.59 ms (four 64-bit primes, conversions included), product 4.19 -> 1.47 ms; partial decryption with binary ciphertexts 19 -> 11 ms, JSON 57 -> 45 ms; client 30 -> 26.5 ms.