Re: bilinear pairing on curves where discrete log is easy

Hi,

Zsuzsanna Doncho wrote:

>> I think such curves are anomalous, but not supersingular, and hence
>> probably not much use for bilinear pairings. For supersingular curves
>> the group order should be p+1, not p.
>
> So such curves won't work in my scenario, cause I need the bilinear
> pairings?
>
> As I described my problem:
> Let P,Q \in G_1, x, m_1, m_2 \in Z_q and g \in G_2. Given the values
> c_1= e(P,Q)^x * g^{m_1}
> c_2= e(P,Q)^{-x} * g^{m_2}
> the following holds, where x, m_1, m_2 are secrets:
> 1. It is hard to calculate m_1, m_2 and x seperatly
> 2. It is easy to calculate m_1+m_2
>
> Maybe there is another kind of solutin, then using a weak curve (where
> the discrete log problem is easy). Maybe there is a special value g \in
> G_2 for which the discrete log of g^x can be easily evaluate, what do
> you think?
I read, that it is easy to calculate the discrete log mod n, where n is
the product of 2 primes p,q (which are publicly known). If I define now
the bilinear pairing as follows:
e: G_1 x G_1 -> Z_n,
where G_1 is of order q. In fact e only maps to elements in a subgroup
of Z_n, called G_2 of order q, for which a generator g \in G_2 is
publicly known. Cause g is the generator of a group of order q, it has
order q, too.

So now I have 2 values c_1 and c_2 in Z_n, calculated as above (in fact
c_1 and c_2 are only in the subgroup G_2 of Z_n).
Then in multiplying c_1 and c_2, I get:
g^{m_1 + m_2} mod n.
I can then easily calculate the discrete log and get m_1 + m_2 mod q
(cause g has order q).

What do you think about this, or is it wrong? Or are there any problems,
I don't see?

Thanks and have a nice weekend,
Zsuzsi
Received on Thu Sep 29 21:44:43 2005