Re: bilinear pairing between special groups

Hi,

thanks for your detailed explanation!

Is q still a prime? You might want to mention that explicitly, you know. 
Sorry, I forget ;). Yes q is a prime.

Obviously, you can let G_2 be ANY group that contains a cyclic group
of order q, or any group that is isomorphic to G_2. 

Assuming that, as in your post of June 7, q is a prime so G_1 is
cyclic of prime order, then what is n supposed to be?
n is the product of 2 primes, for example n=pq, with the q used as the order of G_1.


However, the pairing will be surjective ONLY IF phi(n^2) = q.
The only time this happens is if n=2. For if n has any odd prime
factors, then phi(n^2) cannot be a prime, so n =2^a for some a, in
which case you get phi(2^{2a}) = 2^{2a-1} = 2^a if and only if a=1.

The problem I want to solve is the following:

In general it is not possible to calculate the discrete logarithm in groups of prime order (correct me if I am wrong). So in fact, for 2 given points Q_1, Q_2 \in G_1 (G_1 is of prime order q) and a given value a=e(Q_1,Q_2)^x in G_2, where G_2 is of prime order q, I can't calculate the value x (x in Z_q).

As far as I know, it is possible to calculate the discrete logarithm of a=g^x mod n^2, where g has order n. Then it is possible to calculate the value x mod n.

What I now wanna do is the following:
Given the values:
c_1= e(Q_1, Q_2)^x * g^{m_1} mod n^2
c_2= e(Q_1, Q_2)^{-x} * g^{m_2} mod n^2
it is impossible to calculate m_1 and m_2 and x, but it is possible to calculate the following:
c_1 * c_2 = e(Q_1, Q_2)^x * g^{m_1} * e(Q_1, Q_2)^{-x} * g^{m_2} mod n^2
= g^{m_1+m_2} mod n^2, where g has order n, then it is possible to calculate m_1+m_2 mod n.

Can I do such things?

Bye and thanks,
Zsuzsi
.

Loading