trapdoor scheme based on bilinear pairings

From: Zsuzsanna Doncho (zsuzsidoncho_spamfree_at_msn.com)
Date: 07/26/05 

Date: Tue, 26 Jul 2005 13:35:22 +0200

Hi,

I had a question about this theme a month ago. I was now reading some
stuff about ECC, but still couldn't find any solution. Maybe someone of
you, can help me, cause I am getting a bit frustrated... Maybe there is
no solution to my problem, then it would be also nice to know.

For any hints, advices, etc. I would be very happy.

So my question is the following:

Scenario:
---------
Let G_1 be an additive group with order p (p is prim). Let G_2 be a
multiplicative group of order p. Further let e: G_1 x G_1 -> G_2 be an
admissible, bilinear pairing.
Now let x \in Z_p be a secret value and P, Q two points on G_1, which
are known publicly. Further let g \in G_2 and m_1, m_2 two natural numbers.
Given 2 values (publicly known):
c_1 = e(P,Q)^x * g^{m_1}
c_2 = e(P,Q)^{-x} * g^{m_2}
it is surely easy to calculate:
c_1 * c_2 = g^{m_1 + m_2}.

Desired properties:
-------------------
1. Given c_1, c_2, g, P, Q, p one can efficiently calculate the value
m_1 + m_2.
2. It is hard to calculate m_1, m_2 and x speratly.

My problem is now, whether it is possible to construct the groups or the
curve so, that in my scenario 1. and 2. can be satisfied. For this, you
are allowed to choose a special value g, change the order of the groups,
etc. So in fact you are allowed to change the scenario in
some way to satisfy the conditions. There are two assumption, which have
two be true in every scenarion:
1. c_1 and c_2 are in a multiplicative group
2. Computing the bilinear pairing is efficient.

I think the second property is already true in the scenario I described
above. Condition 1 is surely not satisfied. I don't know, if there are
groups of prim order p, for which 1 is easy. That was the reason why I
was talking about the n2 stuff.

To sum it up:
I am trying to find group G_1, G_2, a bilinear
pairing e, points P,Q, and an x in G_1 such that given the values of
c_1 and c_2, I can easily calculate the discrete logarithm to the
base g of their product, but it is not easy to find m_1 and m_2.

So in other words I am trying to come up with some sort of trapdoor
scheme for transmitting m_1 + m_2.

Thanks for your help in advance,
Zsuzsi

Relevant Pages

  • Re: bilinear pairing on curves where discrete log is easy
    ... > real problem, and not the problem you ran into while trying to solve ... that in my scenario 1. ... some way to satisfy the conditions. ... Computing the bilinear pairing is efficient. ...
    (sci.crypt)
  • Re: bilinear pairing between special groups
    ... Sorry, sorry, sorry Arturo for describing everything so ... that in my scenario 1. ... >are allowed to choose a special value g (that was the reason why I was ... >some way to satisfy the conditions. ...
    (sci.math)
  • Re: bilinear pairing between special groups
    ... My problem is now, if it is possible to construct the groups or the curve so, that in my scenario 1. ... For this, you are allowed to choose a special value g (that was the reason why I was never specifying what g really is), change the order of the groups, etc. So in fact you are allowed to change the scenario in some way to satisfy the conditions. ... Computing the bilinear pairing is efficient. ...
    (sci.math)