## BLS12-381 # Hash-to-Curve * https://eprint.iacr.org/2019/403.pdf * https://wahby.net/bls-hash-ches19-talk.pdf * https://www.youtube.com/watch?v=uvTnMu_cFhU * https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16 --- <style> .reveal { font-size: 32px; } </style> ## Motivation - BLS signatures BLS12-381 is a pairing friendly curve. $$ \begin{align*} e: \mathbb{G}_1 \times \mathbb{G}_2 &\rightarrow \mathbb{G}_T\\ e(a\cdot G_1, b\cdot G_2) &= e(G_1, G_2)^{ab}\\ e(G_1, G_2) &\neq 1 \end{align*} $$ $G_1, G_2$ are generators of $\mathbb{G}_1, \mathbb{G}_2$ resp. --- <section style="text-align: left;"> ### BLS Protocol #### Keygen: $$ \DeclareMathOperator{dollar}{\$} sk \overset{\dollar}\leftarrow \mathbb{Z}_{|\mathbb{G_1}|}\\ pk = sk\cdot G_1 $$ #### Sign: $$ \sigma = sk\cdot H(m) $$ #### Verify: $$e(G_1, \sigma) \overset{?}{=} e(pk, H(m))$$ </section> --- ### How do we instantiate $H(m)$? * We need a "random oracle" mapping strings to elements of $\mathbb{G}_2$ * Naive idea: $H(m) = \text{SHA3}(m) \cdot G_2$ - This is (almost) uniformly distributed, hard to invert, hard to collide. What could go wrong? --- #### BLS is totally broken with this hash function. * Random oracles don't output elements with _known discrete logs_. $$ \begin{align*} \sigma(m) &= sk \cdot \overbrace{\text{SHA3}(m) \cdot G_2}^{H(m)}\\\\\\ \sigma(m') &= \frac{\text{SHA3}(m')}{\text{SHA3}(m)}\cdot \sigma(m) \end{align*} $$ --- ### A second attempt * Interpret $\text{SHA3}(m)$ as $x$-coordinate of EC point, find $y$. * BLS12-381 equation: $y^2 = x^3 + 4$ * What if $[\text{SHA3}(m)]^3 + 4$ isn't a square? * We could do rejection sampling * Not constant time - important when $m$ is secret[^1^](https://eprint.iacr.org/2019/383) * Easy to spam with messages that take a long time to sign --- ### General approach $$ \{0,1\}^* \overset{\text{Hash-to-Field}}{\rightarrow} \mathbb{F}_{p^2} \overset{\text{Map-to-Curve}}{\rightarrow} E'(\mathbb{F}_{p^2}) \overset{\text{isogeny}}{\rightarrow} E(\mathbb{F}_{p^2}) \overset{\text{cofactor clearing}}{\rightarrow} \mathbb{G}_2 $$ --- ### Hash-to-Field * Just use an XOF, mod by $p$ * Be sure to use $k$ extra bits to avoid modulo bias * IRTF spec strongly recommends against rejection sampling * See the new [ZKDocs](https://shiny-system-a853bb08.pages.github.io/docs/cryptodocs/protocol-primitives/random-sampling/#almost-uniform-sampling-in-zq-using-modular-reduction) article --- ### Deterministic Map-to-Curve * Want to take a base field element and deterministically turn it into an EC point * Lots of solutions exist for special forms of elliptic curves. * SWU, Elligator, etc. --- ### "Simplified SWU" * Works for curves of the form $y^2 = x^3 + ax +b$ with $ab \neq 0$. * Only requires 1 field exponentiation * Simple constant time implementation --- ### Main Idea * Let $f(x) = x^3 + ax +b$. * Let $u \in \mathbb{F}$ be a field element we want to map to the curve. * For any $u$ we can find some $x_u \in \mathbb{F}$ such that $$f(ux_u) = u^3f(x_u)$$ * If $u$ is nonsquare, exactly one of $f(x_u), f(ux_u)$ is a square. --- * How do we find $x_u$? $$ \begin{align*} f(ux_u) &= u^3f(x_u)\\ u^3x_u^3 + aux_u + b &= u^3(x_u^3 + ax_u + b)\\ aux_u + b &= au^3x_u + bu^3\\ aux_u(1-u^2) &= b(u^3-1)\\ x_u &= \frac{b(u^3 - 1)}{au(1-u^2)}\\ &=\boxed{-\frac{b}{a}\left(1 + \frac{1}{u^2 + u}\right)} \end{align*} $$ --- * How do we get rid of the condition that $u$ be nonsquare? * Pick an arbitrary nonsquare constant $\xi$. * For any $t$, $\xi t^2$ is nonsquare. * Replace $u$ with $\xi t^2$ everywhere in the previous slide $$ x_t = -\frac{b}{a}\left(1 + \frac{1}{\xi^2t^4 + \xi t^2}\right) $$ --- ### Putting it together * Given $t\in \mathbb{F}$ $$ \begin{align*} x_0 &\leftarrow -\frac{b}{a}\left(1 + \frac{1}{\xi^2t^4 + \xi t^2}\right)\\ x_1 &\leftarrow \xi t^2x_0\\ y^2_0 &\leftarrow f(x_0)\\ y^2_1 &\leftarrow \xi^3t^6f(x_t)\\ x, y^2 &\leftarrow \text{is_square}(y^2_0)\ ?\ (x_0, y^2_0)\ :\ (x_1, y^2_1)\\ &\text{return }(x, \sqrt{y^2}) \end{align*} $$ --- ### Is this uniform? * No - only maps to a subset of $E$ * Can solve this by mapping two field elements to points on $E$ and adding them together * Actually pretty fast compared to, say, scalar multiplication on $E$ --- ### Isogenies * BLS $E(\mathbb{F}_{p^2})$ twist equation: $y^2 = x^3 + (4i + 4)$ * SWU requires $ab\neq 0$! * Instead of mapping directly $\mathbb{F} \rightarrow E$, we choose an isogenous curve $E'$ with $ab \neq 0$ and map to that. Then we use the isogeny to map from $E'$ to $E$. * $E$ has a 3-isogeny with another curve * Rational function of coordinates w/ degree-3 polynomials * Cheap to compute --- ### Cofactor Clearing * We want a point in $\mathbb{G}_2$, which has order $r$ while $|E| = hr$. * $SWU(t)$ maps to a general point on $E$, of the form $a\cdot G_2 + b\cdot H$. * To clear the cofactor we could do $h\cdot SWU(t) = ha\cdot G_2 + hb\cdot h = (ha \mod r)\cdot G_2$ * $h$ is really big - BLS12-381 has faster tricks to clear the cofactor --- ### Putting it all together, for real this time Given message $m \in \{0, 1\}^*$ $$ \begin{align*} h_1, h_2 &\leftarrow \text{OS2IP}(\text{XOF}(m||0)), \text{OS2IP}(\text{XOF}(m||1))\\ P_1, P_2 &\leftarrow \text{OptSimpleSWU2}(h_1 \%\ p), \text{OptSimpleSWU2}(h_2\%\ p)\\ P &\leftarrow \Psi(P_1 + P_2)\\ \text{return}\ \ &\text{ClearCofactor}(P) \end{align*} $$