First candidate multilinear map

Parameters:

  • Ring $R = \mathbb{Z}[x]/\langle \Phi_n(x) \rangle$ and big integer $q$.

Secret:

  • Small $g$ from $R$ (with $g^{-1}$ large).

  • Uniform $z$ from $R_q$ ($ \mathbb{Z}_q[x]/\langle \Phi_n(x) \rangle$).

Public:

  • Randomizers: $x_1, x_2, ..., x_m$ such that $x_i = [b_i z^{-1}]_q$ (with $b_i \in I$ small).

    • They are encodings of zero, so, can be added to encodings of elements just to randomize them.

  • Level-1 encoding of $1 + I$: $y = [a z^{-1}]_q$ for any small $a$ from $1+I$.

  • Seed from strong randomnes extractor: $s$.

  • Level-k zero-testing parameter: $p_{zt} = [hg^{-1}z^k]_q$ with $h \leftarrow D_{\mathbb{Z}^n,\sqrt{q}}$.

Functions:

  • Sampling level-0 encodings:: Return (small) $d \leftarrow D_{\mathbb{Z}^n,\sigma_n} \in R$. (note that $d \in d+I$).

  • Encoding level-1: take a level-0 $d$, sample $r_i \leftarrow D_{\mathbb{Z}^n,\sigma_n} \in R$ and return $u = [yd + \sum_{i=1}^mr_ix_i]_q = [(ad + \sum_{i=1}^mr_ib_i) / z]_q$.

  • Zero testing: : Return 1 if $||p_{zt} u ||_\infty < q^{3/4}$ and 0 otherwise. (Note that $p_{zt} \cdot u = h (ad) g^{-1} + hg^{-1}\sum r_ib_i$)

  • Extract: To extract a canonic random representation from a level-k encoding u:
    (1) Multiply by the zero test: $v = [up_{zt}]_q$
    (2) Represent $v$ as a vector $\vec{v} = \psi(v)$
    (3) Take the most significant bits of each entry: $\vec{m} = (MSB(v_1), ..., MSB(v_\ell))$
    (4) Use the strong randomnes extractor and the seed: $E \leftarrow SRE(\vec{m}, s)$
    (5) Return $E$.
References