1
$\begingroup$

Consider a bilinear pairing $e: G_1 \times G_2 \rightarrow G_T$. Let's assume, $G_1 = G_2 = G_T = (\mathbb{Z}_n,+)$, i.e. additive group of integer modulo $n$ and $e(x,y) = xy$ mod $n$. Isn't it an example of bilinear map?

$G_1 = G_2 = G_T = (\mathbb{Z}_n,\ast)$, i.e. multiplicative group of integer modulo $n$ and $e(x,y) = y^x$ mod $n$, is it still a bilinear map?

Can there be other bilinear map defined over $\mathbb{Z}_n$?

EDIT:


Actually all my question were to understand Groth-Sahai proof system. Here, they have recast the general equation to fit the form of a quadratic equation. (See teh highlighted part below). But, how can they remark that all maps with $f(x,y) = xy$ mod $n$ will satisfy properties of bilinear pairing?

enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ The second one is not bilinear: $e(x,y^z) =x^{(y^z)} \neq (x^{yz})} = e(x,y)^z$. For the first one I don't see the problem with bilinearity at the moment, but the group is pretty useless for crypto since discrete log is trivial. $\endgroup$ – Maeher Jan 22 '15 at 6:57
  • $\begingroup$ Exactly that's what I thought, I wanted to verify $\endgroup$ – Holmes.Sherlock Jan 22 '15 at 9:23
  • 1
    $\begingroup$ To be useful in crypto, the bilinear function has to be nondegrading, and the dlog problem has to be hard in all three groups (well, if it is hard in the target group, the other two follow). $\endgroup$ – tylo Jan 22 '15 at 9:51
  • $\begingroup$ I have just edited my original question. Please have a look. $\endgroup$ – Holmes.Sherlock Jan 22 '15 at 10:03
  • $\begingroup$ After the edit, still no hard problem in this group. $\endgroup$ – Vadym Fedyukovych Jan 22 '15 at 10:14
2
$\begingroup$

Not only is $\mathbb G_1 = \mathbb G_2 = \mathbb G_T = \mathbb Z_p$ with $e(x,y) = x \cdot y \pmod{p}$ an example of a "bilinear group" (a triple of groups with a bilinear map) but every bilinear group of prime order is isomorphic to one of this form. So anything you want to know in principle about such groups, you can calculate on this example. I've used it myself before now as a sanity-check for some protocols.

The security of e.g. ECC implementations of bilinear groups rests on the fact that the isomorphisms to the $\mathbb Z_p$ form are not (thought to be) efficiently computable.

Of course it's cryptographically useless --- discrete logs are easy, as commenters have pointed out. But cryptographic definitions usually come in two parts, functionality and security. An encryption scheme for example is a triple (KeyGen, Enc, Dec) with a correctness property; the scheme where Enc and Dec are the identity maps is therefore an encryption scheme. Only when we introduce security requirements in a second step does this scheme turn out to be lacking. The same goes for $\mathbb Z_p$: it certainly is a "bilinear group" but not a particularly secure one.

EDIT: to answer your last question whether one can define other bilinear maps over $(\mathbb Z_p, +) \times (\mathbb Z_p, +)$: note that $1$ is a generator of $\mathbb Z_p$ so $e(x,y)$ is completely determined for all $x,y$ by $e(1,1)$. If you want a non-degenerate bilinear map, $e(1,1)$ has to be a generator of $\mathbb G_T = \mathbb Z_p$ too, and whichever generator you pick, the structures that you get are isomorphic. If you drop the non-degeneracy requirement, the map that sends everything to $0$ is a different, trivially bilinear one.

$\endgroup$
0
$\begingroup$

Commonly, one uses multiplicative groups. When recall definition of a pairing, it must be bilinear, non degenerate, and easily computable. Note that the definition of e(x,y)=x.y can be interpreted as a external product. (x.y = y+...+y: n-times) and not as the internal group law.

I agree with Maeher's answer. The first exemple is a bilinear pairing, but not the second as it's not symetric. However the first exemple, can't be used for cryptographic protocol. Given: x $\ne 0\cdots $, m.x, n.x, and s.x, it would be easy to compute (mns).e(x,x). As example we can build other bilinear pairings, by just considering all linear maps u, v and the pairing (x,y) -> u(x).u(y) which satisfy non degenerency, the computability is obvious. When using multiplicative structure, definition of pairing is still satisfied, but can't be used for crypto, as BDHP is trivial.

EDIT: Consider final conclusion, (x,y)->x.y not a pairing. Any additional suggestion?

$\endgroup$
  • $\begingroup$ I didn't get the last remark, "When using multiplicative structure, definition of pairing is still satisfied..." $\endgroup$ – Holmes.Sherlock Jan 22 '15 at 9:26
  • $\begingroup$ Sorry, I'm not english fluent. I just remarked that if we consider multiplicative groups such as $Z/n.Z$, then then (x,y) -> x.y is a pairing. But in this case BDHP is trivial. $\endgroup$ – Robert NACIRI Jan 22 '15 at 9:32
  • $\begingroup$ According to you, $G_1 = G_2 = G_T = \mathbb{Z}_n^\times$. Also, $e(x,y)=x.y$, where the dot(.) operation represents MULTIPLICATION MODULO $n$. But, is it really a bilinear map? Say, $e(2.3,4) = e(6,4) = 2$ and again $e(2.3,4) = e(2,4).e(3,4) = 8.1 = 8$. Bilinearity fails. $\endgroup$ – Holmes.Sherlock Jan 22 '15 at 9:51
  • 1
    $\begingroup$ Sorry, I made a mess of the notation. Let's denote the inner multiplication as $\ast$ to avoid confusion. Consider, $n = 11$. But, if I want to replay my previous example: $e(2.3,4) = e(3 \ast 3,4) = e(9,4) = 3$. The other way round, $e(2.3,4) = e(3,4)^2 = 1^2 = 1 \ast 1 = 1$. What am I doing wrong? $\endgroup$ – Holmes.Sherlock Jan 22 '15 at 11:32
  • 1
    $\begingroup$ Even if $e$ is defined with respect to those groups of order $2$ and $5$, isn't it incorrect to remark that $e(x,y) = x \ast y$ is a bilinear map on $\mathbb{Z}_p^\ast$? $\endgroup$ – Holmes.Sherlock Jan 22 '15 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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