Home Notes Research Fun Stuffs

28 April 2022

Pairing Schemes

Pairings are special binary maps defined on top of groups that allows transferring exponents from one group to the other. They find broad use in cryptography including design of digital signatures.

Definition. Let \(G_1, G_2, G_3 \cong \Int_p\) be three cyclic groups of order \(p\). They have the same abstract structure but not necessarily the same description. A pairing \(\inner{\cdot}{\cdot}: G_1 \times G_2 \to G_3\) is a polynomial-time computable map satisfying

• bilinearity: \(\inner{g_1 g_1'}{g_2} = \inner{g_1}{g_2} \inner{g_1'}{g_2}\) and \(\inner{g_1}{g_2 g_2'} = \inner{g_1}{g_2} \inner{g_1}{g_2'}\).
• non-degeneracy: \(\inner{g_1}{g_2} \neq 1\) whenever \(g_1 \neq 1\) and \(g_2 \neq 1\).

Exercise. Prove the following properties of a pairing:

• \(\inner{g_1^a}{g_2} = \inner{g_1}{g_2}^a = \inner{g_1}{g_2^a}\) for all \(a \in \Int\); that is the exponent could be transferred from one operand to the other. In particular,
  • \(\inner{1}{g_2} = 1 = \inner{g_1}{1}\);
  • \(\inner{\cdot}{g_2}\) is a bijection \(G_1 \leftrightarrow G_3\) if \(g_2 \neq 1\);
  • \(\inner{g_1}{\cdot}\) is a bijection \(G_2 \leftrightarrow G_3\) if \(g_1 \neq 1\);
• \(\inner{g_1}{g_2} = \inner{g_2}{g_1}\) if \(G_1 = G_2\).

In this chapter we only concern about the symmetric case \(G_1 = G_2 =: G\).

Boneh-Lynn-Shacham Scheme

Let us take a pairing \(\inner{\cdot}{\cdot}: G \times G \to G'\) and an arbitrary generator \(g \in G\). Assume a random oracle \(H: \set{0,1}^* \to G\). The BLS scheme cannot be simpler: hash-then-sign, and verify via the properties of pairing.

• gen generates a random number \(x \in \Int_p\) and lets \((sk,pk) := (x, g^x)\).
• sgn returns \(\sigma := H(m)^x\).
• vrf checks if \(\inner{\sigma}{g} = \inner{H(m)}{g^x}\).

Its correctness is obvious. To prove security, we also need a cryptographic assumption.

People believe that the Diffie-Hellman problem is hard (i.e. any polynomial time algorithm could succeed with negligible probability only):

Given \(g^x, g^y\) where \(x,y \in \Int_p\) are sampled uniformly, compute \(g^{xy}\).

Clearly it can be reduced to discrete logarithm, so its hardness assumption is stronger.

Security proof. Take any \(\ECM^+\) adversary in the random oracle model. Modify it such that it always requests \(H(m_i)\) for every message \(m_i\) which it later requests/forges a signature. Let \(\ell\) upper bounds the number of requests. We construct a solver for the Diffie-Hellman problem:

• The judge samples \(x,y \in \Int_p\) uniformly, and transmits us \(g^x\) and \(g^y\).
• We emulate gen by publishing \(pk := g^x\) to the virtual adversary.
• We guess the index \(j \in [\ell]\) at which the adversary requests the \(H\)-value for his final forgery. This succeeds with probability \(1/\ell\), in which case all the following steps can proceed without trouble.
• We emulate request to \(H\)-values by:
  • return the old value if this request has been answered before;
  • return \(g^y\) if we are at the \(j\)-th request;
  • return \(g^z\) otherwise, for freshly sampled \(z \in \Int_p\).
• We emulate sgn on message \(m_i\) by:
  • return the valid signature \(\sigma_i := (g^x)^z\) where \(z\) was the fresh randomness that we sampled in response to \(H(m_i)\).
• On receipt of a valid forgery \((m, \sigma)\) from the virtual adversary,
  • note \(\inner{\sigma}{g} = \inner{H(m)}{g^x}\), and furthermore \(H(m) = g^y\) provided we guessed the right index \(j\);
  • hence \(\inner{\sigma}{g} = \inner{g^y}{g^x} = \inner{g^{xy}}{g}\), so \(\sigma = g^{xy}\) due to bijectivity;
  • submit \(\sigma\) to the judge and win the game. ∎

The BLS scheme has the special property of aggregability: The messages and signatures coming from \(n\) players can be bundled into a monolithic message/signature pair for a one-pass verification. For this purpose, we add two specialised routines to the signature scheme:

• \(\texttt{agg}((m_1,\sigma_1), \dots, (m_n,\sigma_n))\) aggregates \(m := m_1 \Vert \dots \Vert m_n\) and \(\sigma := \prod_{i=1}^n \sigma_i\).
• \(\texttt{vrf-agg}(m_1 \Vert \dots \Vert m_n, \sigma)\) checks if \(\inner{\sigma}{g} = \prod_{i=1}^n \inner{H(m_i)}{g^{x_i}}\).

The game needs refinement as well:

• The judge generates independent key pairs \((sk_i,pk_i) := \gen(1^k)\) for all \(i \in [n]\). This mimics the practical situation where \(n\) signers use BLS scheme. Publish the public keys to the adversary.
• The adversary can dynamically request polynomially many signatures of any signer to any message;
• Finally he comes up with a forgery \((m,\sigma)\) that passes the aggregated verification vrf-agg.

Exercise. Prove that the BLS scheme is secure in this game.

Waters Scheme

Waters scheme, like the BLS scheme, is based on the Diffie-Hellman assumption. But it is constructed in a more sophisticated manner that allows a security proof without random oracle. The key device is a “programmable hash scheme” that captures essential functionality of a random oracle in security proof.

Programmable hash scheme

Definition. A \(\mu\)-programmable hash scheme is a tuple \((\spl, H, \dec)\):

• The randomised algorithm \(\spl(1^k, g, h)\) is given two generators \(g,h \in G\). It samples the descriptor \(\kappa\) of a concrete hash function and a companion trapdoor \(\tau\).
• The functor \(H\) can be instantiated with descriptor \(\kappa\) into an efficiently-computable function \(H_\kappa: \set{0,1}^k \to G\).
• The deterministic algorithm \(\dec(\kappa,\tau,m)\) returns a pair \((a,b): ~g^a h^b = H_\kappa(m)\). The decomposition is not unique, of course, but the algorithm deterministically picks one.

Moreover we impose a semantic constraint. Fix arbitrary generators \(g, h \in G\) and consider a probability space where we sample \((\kappa,\tau) := \spl(1^k, g, h)\). For any \(m \in \set{0,1}^k\) we define random variables \((A_m, B_m) := \dec(\kappa,\tau,m)\). Note that the randomness comes from spl only. We require

\[\Pr \left( \set{B_m=0} \cap \bigcap_{i=1}^{q} \set{B_{m_i} \neq 0} \middle\vert \kappa \right) \geq \mu.\]

for all conditions \(\kappa\) and any distinct messages \(m, m_1, \dots, m_q \in \set{0,1}^k\).

It’s a good place to make a few clarifications:

• The definition is purely combinatorial – no pairings, no hardness assumptions, nor any security notion.
• Conditioned on \(\kappa\), the hash function \(H_\kappa\) is fixed. So the only randomness of the decomposition comes from the trapdoor \(\tau\). The probabilistic requirement roughly says “\(\tau\) still contains enough randomness so that the \(h\)-component of decomposition has balanced mass on events \(=0\) and \(\neq 0\)”.

A possible construction

We present a simple \(\Theta(\frac{1}{q \sqrt{k}})\)-programmable hash scheme:

• \(\spl(1^k, g, h)\) samples trapdoor \(\tau := (a_0, \dots, a_k, b_0, \dots, b_k)\) and sets descriptor \(\kappa := (u_0, \dots, u_k) := (g^{a_0} h^{b_0}, \dots, g^{a_k} h^{b_k})\). Here
  • each \(a_i \in \Int_p\) is sampled uniformly and independently;
  • each \(b_i \in \Int_p\) is a sum of \(\Theta(q^2)\) many i.i.d. uniform variables over \(\set{-1,0,1}\); that is we perform an unbiased random walk for \(\Theta(q^2)\) steps.
• \(H_\kappa(m) := u_0 \cdot \prod_{\text{bit } i \text{ of } m = 1} u_i\).
• \(\dec(\kappa,\tau,m)\) naturally decomposes \((a,b)\) where \(a := a_0 + \sum_{\text{bit } i \text{ of } m = 1} a_i\) and \(b := b_0 + \sum_{\text{bit } i \text{ of } m = 1} b_i\).

Note that the descriptor \(\kappa = (u_0, \dots, u_k)\) is uniform and independent of variables \((b_0, \dots, b_k)\), due to the “blinding effect” of uniform variables \(a_0, \dots, a_k\). Hence even with the conditioning on \(\kappa\), the variables \(b_0, \dots, b_k\) still have the same “random-walk distribution”, whose behaviour is governed by the lemma below.

Lemma. Let \(X_1, \dots, X_n\) be i.i.d. random variables following uniform distribution on \(\set{-1,0,1}\). Denote \(X := \sum_{i=1}^n X_i\). Then \(\Pr(X=0) = \Theta(1/\sqrt{n})\).

The proof of the lemma involves heavy computations, which we shall not present. But we invite you to at least write down the exact formula. Also, it is rather easy to prove a lower bound \(\Pr(X=0) \geq \Theta(1/\sqrt{n})\) by Chebyshev and the observation that the mass drops monotonically from the centre 0.

Assuming the lemma, we are almost done. For any message \(m\), we have by definition \(B_m = b_0 + \sum_{\text{bit } i \text{ of } m = 1} b_i\), which involves at least one and at most \(k+1\) bulks of random walks. Hence \(\Pr(B_m=0 \mid \kappa) \in [\Theta(\frac{1}{q \cdot \sqrt{k}}), \Theta(\frac{1}{q})]\). Then we condition on this event and consider any other message \(m_i \neq m\). Since the two messages have at least one bit difference, this intuitively provides us with enough randomness that smooths the correlation between \(B_m\) and \(B_{m_i}\), and one could show that \(\Pr(B_{m_i} = 0 \mid B_m = 0, \kappa) \leq \frac{1}{2q}\). Applying union bound we have \(\Pr\left( \bigcup_i \set{B_{m_i} = 0} \middle\vert B_m=0, \kappa \right) \leq \frac{1}{2}\), and the desired lower bound \(\mu = \Theta(\frac{1}{q \sqrt{k}})\) follows.

Back to signature scheme

Now we assume a pairing \(\inner{\cdot}{\cdot}: G \times G \to G'\) and a \(\mu\)-programmable hash scheme \((\spl,H,\dec)\) for non-negligible \(\mu\). We agree upon a fixed generator \(g \in G\). The Waters signature scheme is given by:

• gen:
  • pick a dummy generator \(h \neq g\);
  • sample \((\kappa,\tau) := \spl(1^k,g,h)\) and discard \(h, \tau\) (which are used in security proof only);
  • sample \(sk \in G\) uniformly;
  • let \(pk := \inner{g}{sk} \Vert \kappa\).
• sgn:
  • sample \(r \in \Int_p\) uniformly;
  • return \(\sigma := g^r \Vert sk \cdot H_\kappa(m)^r\).
• vrf:
  • unpack \(\sigma =: \rho \Vert \eta\);
  • check if \(\inner{g}{\eta} = \inner{g}{sk} \cdot \inner{\rho}{H_\kappa(m)}\).

Exercises.

• Justify the correctness.
• Show that if \((m, \rho \Vert \eta)\) passes verification, then \(\rho = g^r\) and \(\eta = sk \cdot H_\kappa(m)^r\) for some unique \(r \in \Int_p\).

Security proof. We construct a solver for Diffie-Hellman problem based on any \(\ECM^+\) adversary.

• The judge samples \(x,y \in \Int_p\) uniformly, and transmits us \(g^x\) and \(g^y\).
• We emulate gen by
  • let \(h := g^x\);
  • sample \((\kappa,\tau) := \spl(1^k, g, h)\);
  • imagine \(sk := g^{xy}\);
  • publish \(pk := \inner{g^x}{g^y} \Vert \kappa\) to the virtual adversary.
• During the whole course of simulated attack, the adversary can observe \(pk\) and a bunch of signatures \(\set{\sigma_i}\). We claim that, for any fixed and distinct \(m, m_1, \dots, m_q\), the probability of the event \(\set{B_m=0} \cap \bigcap_{i=1}^{q} \set{B_{m_i}}\) conditional on \(pk,\set{\sigma_i}\) equals the probability conditional on just \(\kappa\). The reasons are:
  • the event only concerns the decomposition of messages, which depend solely on \(\kappa, \tau\);
  • the random variable \(\tau\) has correlation with \(\kappa\) but is otherwise independent of anything else, including the secret key, the first part of the public key, and the signatures.
• The secret key is imaginary and unknown, so we would come to trouble in sgn. The trick is to utilize the trapdoor to decompose \(H(m_i) = g^a h^b = g^{a+bx}\). By programmability we can assume \(b \neq 0\) (with descent probability). We can thus artificially set \(r := r' - y/b\) (with uniform \(r' \in \Int_p\) to ensure right distribution), so that \(H(m_i)^r = g^{ar+brx} = g^{-xy} \cdot g^{ar'} (g^x)^{br'} (g^y)^{-a/b}\) contains a factor that cancels \(sk\) and save us. Of course we don’t know \(y\) (and hence \(r\)) explicitly, but by sampling \(r'\) we conceptually determine a uniform \(r\) as required. Formally, we emulate sgn by:
  • let \((a,b) := \dec(\kappa,\tau, m_i)\);
  • sample \(r' \in \Int_p\) uniformly (which implicitly determines \(r = r'-y/b\));
  • return \(\sigma := g^{r'} (g^y)^{-1/b} ~\Vert~ g^{ar'} (g^x)^{br'} (g^y)^{-a/b}\).
• Finally, upon receiving a valid forgery \((m, \rho \Vert \eta)\),
  • imagine \(\rho = g^r\) and \(\eta = sk \cdot H_\kappa(m)^r\);
  • let \((a,b) := \dec(\kappa,\tau, m)\), where we can assume \(b=0\) with descent probability;
  • hence \(\eta = sk \cdot g^{ar} = sk \cdot \rho^a\);
  • so we submit \(sk = \eta \cdot \rho^{-a}\) to the judge and win the game. ∎