Re: bilinear pairing between special groups

Hi,

Sigh. First, turns out that you do NOT have a way of efficiently
working in the cyclic group of order q that is sitting inside of
(Z_{n^2})^*, because you do not have a way of FINDING that
group. Then, you do not have a way of relating this algorithm from
this paper to the problem you would ->then<- have, so you do not have
an efficient algorithm even for the situation to which you cannot get
in an efficient manner. Then, you are asking whether there is an
efficient way of calculating the discrete logarithm of a product,
given that you know the two factors, in that setting.   If there were,
then the discrete logarithm problem would be simple: pick an element
whose discrete logarithm you know ahead of time (e.g., the generator,
whose discrete logarithm is 1), multiply it by the element whose
discrete logarithm you want to know; efficient calculate the answer to
the discrete logarithm problem for this product. Then subtract the
known discrete logarithm from this answer (which can be done
efficiently, obviously). So: IF such a method were known, then the
original problem would have a known efficient solution. Since it
doesn't, no such method exist.

So: you don't know how to get to where you said you want to be, you do
not know what to do once you get there, and then finally, you want to
solve a problem which is just as hard as the original one once you do
get there and figure out what to do. Doesn't sound like a very
well-formed or promising plan to me.
Yes...sadly. So with the bilinear pairing it doesn't work, but maybe with this more straightforward solution:

Assume we have 3 parties. Every party i \in {1,2,3} has a secret m_i \in Z_n. Parti 1 further knows the values x_{1,2} and x_{1,3}, Party 2 knows x_{1,2} and x_{2,3} and Party 3 knows x_{1,3} and x_{2,3}. Further the values r \in Z*_n, n=pq and the following values are publicly known:
c_1= r^{x_{1,2} + x_{1,3}}*(n+1)^{m_1} mod n^2
c_2= r^{x_{2,3} - x_{1,2}}*(n+1)^{m_2} mod n^2
c_3= r^{-x_{1,3} - x_{2,3}}*(n+1)^{m_3} mod n^2

So now everyone can reconstruct the value m_1+m_2+m_3, but noone can calculate m_1, m_2 and m_3 by its own?

Btw. Aldar told in his posting, that there are weak curves on which a bilinear pairing is defined. Can I maybe use them to solve my problem?

Thanks in advance,
Zsuzsi
.

Relevant Pages

  • Re: bilinear pairing between special groups
    ... the units modulo n^2 do not form a cyclic group (when n is of the form ... The units modulo k ... Let a be a generator for G, and let b be an element ... The "discrete logarithm of b to the base a", log_a, is the ...
    (sci.math)
  • Re: A new hard problem
    ... On input g^a, g^b, a/b, to compute a. ... Let's suppose that g is the generator for a finite, cyclic group G. ... Then your problem is equivalent to discrete logarithm. ... Choose a random integer v modulo q and decide that a = vx and b = x. ...
    (sci.crypt)
  • Re: A new hard problem
    ... Let's suppose that g is the generator for a finite, cyclic group G. ... Then your problem is equivalent to discrete logarithm. ... Choose a random integer v modulo q and decide that a = vx and b = x. ...
    (sci.crypt)
  • Re: bilinear pairing between special groups
    ... you can let G_2 be ANY group that contains a cyclic group ... discrete logarithm". ... It's that the discrete logarithm problem ... exponential time). ...
    (sci.math)