Re: Magic Flight: A New Public Key Algorithm stronger? than factoring

From: Francois Grieu (fgrieu_at_micronet.fr)
Date: 07/09/03 

Date: Wed, 09 Jul 2003 08:55:00 +0200

Jim Steuert <pjsteuert@rcn.com> wrote in article <oprr0douvjdwdye5@news.rcn.com>:

> Francois Grieu wrote:
> >
> > Knowing M and alices_public, by Gaussian elimination or some
> > faster method, it is easy to find one of the (possibly several)
> > alices_secret that match this equation.
> >
>
> Gaussian elimination requires that values have
> multiplicative inverses. The basic operation is row-reduction - some
> constant times one row added to the other row makes zero.

Then a discussion he had with Bryan Olson led to him writing
in article <oprr0iv4vjdwdye5@news.rcn.com>:

> Bryan Olson wrote:
> >
> > No problem: use the row beginning with '2' as the pivot.
>
> No it is a problem. It is the crux of the problem.
>
> I'm not surprised that you found pivots for this tiny example.

I second Bryan on this one. We have a fully known square
matrix M and alices_public, such that
      alices_public = M * alices_secret
and are working with elements in the integers mod 2^12.

We know there is a matching alices_secret.

Gaussian elemination can be done as follow: we simplify
columns in some arbitrary order, say right to left.
When we want to eliminate terms in a column, we select
one of the lines among those not previously selected
which in the column under consideration has a non-zero
term with minimal s when the term is writen as u*(2^s),
with u odd.

Values in any other line not previously selected can be
writen as v*(2^s) for some integer v, and to this line we
add the selected line times -v*(u^-1), thus making this
column zero in all lines not previously selected.

Gaussian elimination proceeds until we have a triangular
matrix, within row order.

> In the tabular commutative ring example (below) [..]
> this won't work.

The thread is about Magic Flight, a well defined
algorithm which works with integers mod 2^k (except for
a shift by 1 which is easily dealt with).

And WHY would your new working set make it hard to
exhibit a solution, when there is one, for a sytem
of form a = M * x ?

  François Grieu

Relevant Pages