Re: Magic Flight: latest version of a public-key algorithm using max-plus algebra

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 09/08/03 

Date: 8 Sep 2003 14:25:38 -0700

Mok-Kong Shen wrote:
> Do you have text documents given some explaination
> of the algorithms involved?
>

Sorry, no, but the source codes each have a fairly large text in
comments which explains the algorithms. It should be fairly explanatory.
The source codes have references as well, in particular to the
paper by Monico et.al, at University of Notre Dame.

If you have any more questions, I will elaborate.

It has been fun generating all of these semirings (semigroup ring
without additive inverses). It shouldn't be hard for someone to
come up with additional similar constructions.

I would like to come up with a general statement, that,
without additive inverses, these are in general
"hard" problems to solve.

But there are some notable counter-examples:

For example, if the distributive lattice is a general boolean
algebra, (which I deliberately avoided by not using
"complemented" distributive lattices), then it lends
itself to solution by embedding the boolean equations
in a linear algebra model, as desribed in the Rivest
quasiring reference.

And any embedding attack would not apply to a matrix semiring
(non-cancellative) based on the algebra. (the matlatt.c and
nestedlattice.c variants). The nested versions in particular have
three parameters which would greatly complicate the constraints in
any attack, both of the min/max/min/max/min/max variant
(nestedminmax.c) or the nested matrix lattice variant (nestedlattice.c).

But distributive lattices are themselves only a special case of
general semirings. Except for distributive lattices (genlattice.c) or
the min-max algebra, I have not yet found or constructed a generator of
"general" large commutative/distributive algebras without additive
inverses (semirings).

That distributive lattice table generator (genlattice.c) is on the page:

<URL: http://users.rcn.com/pjsteuert>

 -Jim

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote in message news:<3F5C97CF.5DD9C4FB@t-online.de>...
> Jim Steuert wrote:
> >
>
> > These very simple codes are at:
> >
> > <URL: http://users.rcn.com/pjsteuert>
> [snip]
>
> Do you have text documents given some explaination
> of the algorithms involved?
>
> M. K. Shen

Relevant Pages

  • Re: Multiplication and Division in Triplets; division by zero-sized vectors
    ... be "collapsed" to C3 as a "conservative Hoop algebra". ... Tables with Moufang division properties conserve ... > Then A A^+ is the idempotent generator of the ideal generated ...
    (sci.math.research)
  • Re: Hows this for random dice?
    ... dice rolls on various gammon servers are truly random. ... generator and a truly random generator is irrelevant for backgammon purposes. ... There are some pretty good software based random algorithms out there - not good enough for cryptography, but good enough for a dice simulation. ... Mostly so they don't have to listen to frivilous complaints like yours. ...
    (rec.games.backgammon)
  • Cohomolgy "algebras" of compact surfaces
    ... a "ring over a ring") of manifolds, so I am attempting to understand ... "algebra" structures as some remedial work. ... the authors give the singular homology of the ... H_2 and computing the action of the dual of each generator of H_1 on the ...
    (sci.math.research)
  • Re: PHP mt_srand no longer seeds same number!!!!! aaarrrg
    ... What they mean is a "repeatable sequence of numbers which are ... software alone. ... A software-based generator only creates pseudo-random numbers, ... Such algorithms are usually deterministic - same input, ...
    (comp.lang.php)
  • Algorithm to generate permutations
    ... use as a generator for some computation. ... algorithms is that they do not scale very well if you have to enumerate ... all the mappings of a single permutation. ... sylow subgroups of the powers of 2 times all the remaining odd powers, ...
    (sci.math.symbolic)
Quantcast