Re: bilinear pairing between special groups

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


>>>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.
>Yes, that was what I want to say.
>
>>>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 wanted to say, with the sentence above was:
>Given the value g,n and a=g^x mod n^2, where g has order n and x \in
>Z_n, one can efficiently calculate the value x mod n. So that's the
>discrete log of a mod n^2, or am I missunderstanding something?

Technically, you don't have a "discrete log" problem modulo n^2, since
the units modulo n^2 do not form a cyclic group (when n is of the form
you specified, pq with p and q distinct odd primes). The units modulo k
form a cyclic group if and only if k is a prime power or twice a
prime.

This is taken from the "Handbook of Applied Cryptography", by Alfred
J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. You can
access it via the web at

http://www.cacr.math.uwaterloo.ca/hac/

Definition: Let G be a cyclic group of order m [written
multiplicatively]. Let a be a generator for G, and let b be an element
of G. The "discrete logarithm of b to the base a", log_a(b), is the
unique integer x, 0<= x <= n-1 such that b = a^x.

Definition. The 'Discrete Logarithm Problem' (DLP) is the following:
given a prime p, a generator a of (Z_p)^*, and an element b of
(Z_p)^*, find the integer x, 0<= x <= p-2, such that a^x = b (mod p).

Definition. The 'Generalized Discrete Logarithm Problem' (GDLP) is the
following: given a finite CYCLIC [emphasis added] group G of order n,
a generator a of G, and an element b of G, find the integer x,
0<= x <= n-1 such that b = a^x.


So, what you describe is neither the DLP nor the GDLP. (Never mind
that you never specified a generator; let's assume that's given
somewhere). You are working with a group which is NOT cyclic. You can
generalize the GDLP further, but then it may not always have
solutions.

For example, let's say p=3 and q=5. Then n=15, n^2 = 225, and the
group of elements prime to 225 is of order 3*2*5*4 = 120. But it is
not cyclic. If it were cyclic, then there would be one and only one
element of order 2. Yet 224, 199, and 26 all have multiplicative order
2 modulo 225.

Now, you are in a better position in terms of a subgroup of order 5,
since then there is only one choice: if x^5 = 1 (mod 225), then x^5 =
1 (mod 9), hence x = 1 (mod 9), and x^5 = 1 (mod 25), so x=1, 6, 11,
16, 21 (mod 25). Using the Chinese Remainder Theorem gives you the
only solutions modulo 225:

1, 181, 136, 91, 46.

So will you be working inside of <181> in (Z_{225})^*?

On what grounds do you say that the problem of (i) finding out the
cyclic group of order q in (Z_{n^2})^*; and (ii) solving the GDLP
there, is "easy"?

Of course, if p<q, then since q is prime to p(p-1), the order of the
group of units modulo p^2, this will always happen, so you will have a
unique group of order q sitting inside (Z_{n^2})^*. If you have a
nontrivial solution to x^q = 1 (mod q^2), then you can use the Chinese
Remainder Theorem to find a generator for this group.

Do you have an efficient way of solving that problem?

>>>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,
>
>> You keep using that word ("impossible"). I do not think it means what
>> you think it means.
>Yes... with impossible, I wanted to say, that you can't calculate it
>efficiently, and possible means: it can be calculated efficiently.

On what grounds do you assert that, having found the unique cyclic
subgroup of order q sitting inside (Z_{n^2})^*, you have an efficient
way of solving the GDLP ->there<-?

Solving the GDLP in an arbitrary cyclic group G of order n is
essentially equivalent to finding an isomorphism between G and
Z_n. While not an expert on cryptography, I do not see why it would be
simpler to solve this problem in the group (Z_{n^2})^*, which will
necessarily involve larger numbers, than in the group (Z_q)^*.


>>>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?
>So I wanna know 2 things:
>1.) Given the values c_1, c_2, Q_1, Q_2, n, is it hard to calculate the
>values x, m_1, m_2?

I would expect so. What makes you think it would be easy?


>2.) Given the values c_1, c_2, Q_1, Q_2, n, is it "possible" to
>calculate efficiently the value m_1+m_2 mod n?


--
======================================================================
"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: 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: 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: bilinear pairing between special groups
    ... working in the cyclic group of order q that is sitting inside of ^*, 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 such a method were known, then the original problem would have a known efficient solution. ...
    (sci.math)
  • 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)
  • Re: Properties of Automorphisms
    ... generator to a generator. ... theres always a phi that takes b to a1 and another phi that takes a1 to a2 ... Let = G be a group and phi be an automorphism of G, ... cyclic group in which 1 and -1 are both generators. ...
    (sci.math)