Re: bilinear pairing between special groups

In article <d96u7e$1q0$00$1@xxxxxxxxxxxxxxxxx>,
Zsuzsanna Doncho <nospam@xxxxxxxxxx> wrote:

>
>I think I can now, at least a bit, understand what is the problem in my
>formulations. Sorry, sorry, sorry Arturo for describing everything so
>unclear. I can understand, why you got crazy of me. In fact, I was
>always trying to give a part solution of my problem, without really
>specifying my problem.
>
>Hopefully I can now explain the problem more clearer and correct. Please
>forget the most things I wrote in other posting. I will start again from
>ground:
>
>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}.
>
>Conditions:
>-----------
>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, if it is possible to construct the groups or the
>curve so, that in my scenario 1. and 2. can be satisfied.

In other words, you are 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, you 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
(because, knowing m_1 and m_2, you could presumably find out x, which
is what you want to keep secret).

So you are trying to come up with some sort of trapdoor scheme for
transmitting x.

Is this correct?

>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 (that
>was the reason why I was suddenly computing mod n^2, what is really
>nonsense), 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 condition is already true in the scenario I described
>above. Condition 1 is surely not satisfied.

Which condition 1? You have two "conditions 1": the one listed about
how you can efficiently calculate the value of m1+m2, and then the one
you just listed, that "c_1 and c_2 are in a multiplicative group". I
suspect you mean the original.

>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 n^2 stuff, cause I read in the paper I mentioned
>in one of my posts, that such a calculation is easy in (Z_{n^2})^*.

There are several places where discrete logarithm per se is relatively
easy, such as finite fields where index calculus can be used. Whether
or not the twist you add in c_1 and c_2 is sufficient to obscure m_1
and m_2 is something I am not qualified to judge; you'd be better
served in sci.crypt. I would suggest Koblitz's book on cryptosystems
with elliptic curves. But if you do go to sci.crypt, I suggest you
specify FIRST what it is you want to accomplish, as you did here, and
then how you hope to accomplish it. The "conditions" you list are not
really "conditions"; rather, they are the "desired properties".


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • 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)
  • Re: The Vinland Maps Ink
    ... >>> The reason why you and I seem to be slowly becoming at loggerheads is ... > But I'm not arguing the VM on a professional level with Ken Towe. ... > Ken Towe wants those who argue for authenticity to set out a scenario ...
    (sci.archaeology)
  • Re: Nuclear Plot of "Jericho"
    ... at the world today, the biggest danger right now is from international terrorist gangs and/or their state sponsors, rather than from a superpower attack like in ... Russia has no reason to nuke us at this moment. ... politics in any way they want to create the scenario they gave us. ...
    (rec.arts.tv)
  • Re: Born To Run: What Humans Really Evolved To Do
    ... keep chimps in trees. ... It would be apparent in your scenario. ... Nope -- it's the same reason as peasants in Afghanistan ... apparent reason. ...
    (sci.anthropology.paleo)
  • trapdoor scheme based on bilinear pairings
    ... Desired properties: ... that in my scenario 1. ... some way to satisfy the conditions. ... Computing the bilinear pairing is efficient. ...
    (sci.crypt)
Quantcast