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; the strong PRF version assumes hardness for adversarially chosen 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)$
\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

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{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 $R \getsr \Funcs(\bits^n, \ZZ_3^\ell)$
\Comment{Can be sampled lazily}
\State $\calO_0(x) := B \cdot (A \cdot x \bmod 2) \bmod 3$
\State $\calO_1(x) := R(x)$
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

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

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

is negligible. AM hardness implies Weak-AM hardness (the strong assumption implies the weak one).

Known Results

• Alternating moduli assumption ⇒ PRF
• Alternating moduli assumption ⇒ MPC
• PRG in NC1 ⇒ iO
• 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. A PRF in ${\mathrm{TC}}^0$ (constant depth, threshold gates) would have strong implications for MPC efficiency.

Pseudorandom correlation generators (PCG)

A related paradigm where short seeds expand to long correlated randomness useful in MPC; alternating-moduli-style assumptions can ground efficient PCG constructions.

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

• Alternating moduli assumption ⇒ MPC
• Alternating moduli assumption ⇒ PRF
• Alternating moduli assumption ⇒ Pseudorandom correlation generators (PCG)

Footnotes

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