Re: bilinear pairing between special groups

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

>> 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?
>You can find the algorithm in:
>http://www.daimi.au.dk/~ivan/GenPaillier_finaljour.ps
>on page 6.

pp. 6 of that is the proof that there is a polynomial time algorithm
for inverting the map

Z_{n^s} x (Z_n)^* --> (Z_{n^{s+1}})^*

given by (x,r) |-> (1+n)^x*r^{n^s} (mod n^{s+1}),

PROVIDED that you know the lcm of p-1 and q-1 (where p and q are
primes, and n=pq).

So you would need to know p and q (as far as we know, though it is
possible you may be able to find lcm(p-1,q-1) without factoring n).
But is that the question I asked you? I asked you if you had an
efficient algorithm for finding the cyclic group of order q sitting
inside of (Z_{n^2})^*. How do you obtain it from the fact that the map

Z_{pq} x (Z_{pq})^* --> (Z_{(pq)^2})^*

given by (x,r) |-> (1 + n)^x*r^{n^2}

can be quickly inverted?



>> 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)^*.
>
>To tell you the truth (I think you already recognize it), my
>understanding of math is sadly poor. Although I try to undestand things,
>often I have a lack at the basics. So in fact, although I read the
>paper, I mentioned above, I wasn't able why the algorithm described in
>the paper from above, is correct and works efficiently. In fact, I
>suppose it is correct and does what the authers supposed it does.

But what the authors are saying it does is not what you are saying you
will use it for. The first part of the proof says that they are going
to give an algorithm for solving the very specific problem of

"Finding i from (1+n)^i (mod n^{s+1})"

This is not the discrete logarithm problem, since we do now know the
order of (1+n) in the group in question. Note also that all of the
paper assumes that n is an RSA modulus. so n = pq, and IN GENERAL, you
do not know p and q (so, presumably, you do not know lcm(p-1,q-1)
->either<-).




>>>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?
>The only thing here which gives me a pain, is the thing with the
>bilinear pairing. From the paper, I mentioned above, I know that it
>could be done efficiently, but what happens with the bilinear pairing,
>are there problems in using it in the groups, you need for the
>algorithm, i.e. (Z_{n^2})^*?

The paper EXPLICITLY tells you what the bilinear pairing is. What
exactly is your problem?

--
======================================================================
"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
    ... given a finite CYCLIC group G of order n, a generator a of G, and an element b of G, find the integer x, ... generalize the GDLP further, but then it may not always have ... Do you have an efficient way of solving that problem? ... From the paper, I mentioned above, I know that it could be done efficiently, but what happens with the bilinear pairing, are there problems in using it in the groups, you need for the ...
    (sci.math)
  • Re: Agduria dungeon generation
    ... stage of the algorithm and rise appropriate error, ... A NTAE generator doesn't have to have any ... NTAE will happily accept all valid inputs and RNG states and produce ...
    (rec.games.roguelike.development)
  • Re: Math.random
    ... That's not the only possible algorithm; ... without much difficulty implement a long shift-register generator; ... doublevalue or null/undefined/false for auto reseeding, ... I think 0 to 364 would be better; it goes well with zero-based arrays, ...
    (comp.lang.javascript)
  • Re: Agduria dungeon generation
    ... Depends entirely on the pseudo random number generator, ... algorithm don't suddenly change that probability. ... TAE isn't even obviously less ... algorithms but do understand their NTAE algorithms, ...
    (rec.games.roguelike.development)
  • Re: Recursion problem - Graph theory - Algorithm needed
    ... )> I pose a question here concerning what I think is a classic computer ... but I don't know of an algorithm for solving it. ... here are 15 square tiles arranged in a 4x4 grid, ...
    (comp.programming)