Re: bilinear pairing between special groups

In article <d8ppk3$n1c$04$1@xxxxxxxxxxxxxxxxx>,
Zsuzsanna Doncho <nospam@xxxxxxxxxx> wrote:

>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.

Don't you think that would have been something important to mention?


>> 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).

You're wrong. It's not that "it is not possible to calculate the
discrete logarithm". It's that the discrete logarithm problem
->seems<- to be hard (all known deterministic algorithms run in
exponential time).

> 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).

We do not know of any way to ->efficiently<- find it.


>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.

I don't understand this sentence.

Do you mean, there are ->efficient<- algorithms to find the discrete
logarithm base g modulo n^2 when g has order n in (Z_{n^2})^*?

And what does the last sentence mean? An assertion that you can find
x, or a hope?


>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,

>From "The Princess Bride":

Vizzini: Inconceivable!
Inigo: You keep using that word. I do not think it means what you
think it means.

You keep using that word ("impossible"). I do not think it means what
you think it means.


> 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?

I don't know what it is you think you can do, and what it is you hope
you can do, and what it is you think cannot be done, so I'm at a loss.


--
======================================================================
"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
    ... It's that the discrete logarithm problem ->seems<- to be hard (all known deterministic algorithms run in exponential time). ... pairing exists on a weak curve. ...
    (sci.math)
  • Re: bilinear pairing between special groups
    ... It's that the discrete logarithm problem ... > exponential time). ... pairing exists on a weak curve. ...
    (sci.math)
  • Re: Q: discrete logarithms and modular powerseries
    ... Given the modulus & the base, the discrete logarithm is ... discrete logarithm problem on an abstract cyclic group). ... and we can make believe that both are in Z/pZ ...
    (sci.math)
  • 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)
Loading