Score:4

Why pairing domains are subgroups of the r-torsion group?

in flag

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?
Score:3
ru flag

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.

Bean Guy avatar
in flag
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?
Daniel S avatar
ru flag
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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.