4
$\begingroup$

In pairing based cryptography (PBC) we restrict the pairing domains to be subgroups of the $r$-torsion group $E[r]$. This arises two questions to me:

  1. Why do we restrict them to subgroups of $E[r]$? Couldn't we use, for instance, the whole group of points $E$? Or a mixture between various torsion groups? (As long as they are sufficiently large to ensure security)
  2. If so, what happens if I evaluate pairings ouside the two subgroups?
$\endgroup$

1 Answer 1

3
+25
$\begingroup$

First, for cryptographic purposes we will always want to work in groups of finite order. Now suppose that we have a pairing $e(.,.)$ that bilinearly maps pairs of elements of an abelian groups $G_1$ and $G_2$ to $r$th roots of unity in some field. Considering cosets of the subgroup $rG_1$, we can write any element of $G_1$ in the form $rP+R$ where the coset representative $R$ is in the $r$-torsion subgroup. Now pick any other element $S\in G_2$

By bilnearity, we have $$e(rP+R,S) = e(rP,S)e(R,S)=e(P,S)^re(R,S)=e(R,S)$$ so that the pairing depends only on $R$. A similar argument applies to $G_2$. Thus even if we can adapt the construction of $e(.,.)$ to the whole group, there is no security benefit and the additional information in $P$ could be a malicious channel.

Theres no reason that $r$ cannot be composite, but the cryptographic strength of the pairing is no greater than the difficulty of a generic group or order $r$ which (by Pohlig-Hellman) is no greater than the square-root of the largest prime factor of $r$, with partial information being available for smaller subgroups with less work. Thus taking $r$ to be prime is the most efficient construction.

$\endgroup$
2
  • $\begingroup$ Here, you assume that $e(\cdot,\cdot)$ maps to some group of $r$-th roots of unity. Why can we assume that? What if this is not the case? $\endgroup$
    – Bean Guy
    Apr 11, 2023 at 6:30
  • 1
    $\begingroup$ The same analysis applies when the output is in any cyclic group of order $r$. I'm not familiar with any non-commutative pairing constructions and almost all cryptography uses cyclic groups. $\endgroup$
    – Daniel S
    Apr 11, 2023 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.