Alternating moduli assumption ⇒ PRF

Alternating moduli assumption implies PRF.

Statement

Migrated verbatim from alternating-moduli § Alternating Moduli:

The alternating moduli assumption (also called Crypto Dark Matter[^1] after BIP+18) posits that mixing linear operations over different moduli — specifically ${\mathbb{Z}}_2$ (XOR) and ${\mathbb{Z}}_3$ (mod-3 addition) — yields candidate PRF constructions that are computationally indistinguishable from random, under assumptions not known to reduce to standard assumptions like LWE or LPN.

Migrated verbatim from alternating-moduli § Known Results:

• Low-complexity PRF candidates (in ${\mathrm{NC}}^1$ / ${\mathrm{TC}}^0$) based on mixed-moduli assumptions — BIP+18

Notes

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

This relation is stated on 2 pages; the statements above are all of them.

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• Candidate construction, not a proved reduction: the assumption IS that the construction is a PRF, so hypothesis and conclusion nearly coincide (definitional).
• The same sentence also asserts a non-relation to LWE and LPN, recorded separately.
• Candidate, not a reduction — no security proof from a separate assumption.
• Complexity-class qualifiers NC^1 / TC^0 cannot be carried by a plain conclusion identifier.
• Duplicates the intro claim at line 14.