Alternating Moduli

The alternating moduli assumption (also called Crypto Dark Matter¹ 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.

Assumption

The main candidates from BIP+18 use a two-layer structure: a secret linear map $A$ over ${\mathbb{Z}}_2$ followed by a public linear map $B$ over ${\mathbb{Z}}_3$. Given $n,m,\ell \in \mathrm{poly}(\lambda )$, the function $f_A:\{0,1{\}}^n\to {\mathbb{Z}}_3^{\ell }$ is defined by

$$f_A(x)=B\cdot (A\cdot x\mathrm{mod}2)\mathrm{mod}3,$$

where $A\stackrel{\$}{\leftarrow }{\mathbb{Z}}_2^{m\times n}$ is the secret key and $B\stackrel{\$}{\leftarrow }{\mathbb{Z}}_3^{\ell \times m}$ is public. The weak PRF version assumes hardness for uniformly random inputs.

Weak alternating moduli (random-input) assumption

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{weak-am}}_{\calA}(\secpar)$}
\begin{algorithmic}
\State $A \getsr \ZZ_2^{m \times n}$; $B \getsr \ZZ_3^{\ell \times m}$
\State $b \getsr \bits$
\State $\calO_0() := (x \getsr \bits^n;\; (x,\; B \cdot (A \cdot x \bmod 2) \bmod 3))$
\State $\calO_1() := (x \getsr \bits^n;\; y \getsr \ZZ_3^\ell;\; (x, y))$
\State $b' \gets \calA^{\calO_b}(1^\secpar, B)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

Weak-AM is hard if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathcal{A}}^{\text{weak-am}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\text{weak-am}}(\lambda )=1\right]-1\right|$$

is negligible.

Strong alternating moduli (chosen-input) assumption

The chosen-input analogue for $f_A$ is false, since $f_A(0^n)=0$ for every key; BIP+18 put forward a separate depth-3 strong PRF candidate.

Known Results

• Weak alternating moduli ⇒ weak PRF
• The candidates admit distributed-evaluation protocols with better round and/or communication complexity than MPC evaluation of AES, LowMC or Rasta, most so with an honest majority or with preprocessing — BIP+18
• The assumption is not known to follow from or imply standard lattice assumptions

Variations

Low-complexity PRFs (in ${\mathrm{NC}}^1$ / ${\mathrm{TC}}^0$)

Separate from the alternating moduli assumption, there is interest in PRFs computable by low-complexity circuits. PRFs in ${\mathrm{TC}}^0$ follow from DDH and from factoring — NR97.

Pseudorandom correlation generators (PCG)

See PCG. Pseudorandom correlation functions for OT correlations follow from a constrained Naor–Reingold PRF whose constraint class contains a low-complexity weak PRF, and the BIP+18 candidate is one instantiation of that weak PRF — BCM+24.

Attacks

• Ongoing cryptanalytic attention; several early candidates have been partially broken or weakened
• Algebraic attacks exploiting the mixed-moduli structure (Gröbner basis methods, linearization) remain the primary avenue

Participates in

Builds on Alternating moduli assumption

• Weak alternating moduli ⇒ weak PRF (via Weak alternating moduli (random-input) assumption)

Footnotes

1. The name “Crypto Dark Matter” reflects the idea that large regions of the cryptographic assumption landscape remain unexplored. ↩