Re: Public Key, Symbolic Calculation

From: Kiuhnm (kiuhnm03_at_yahoo.it.invalid)
Date: 02/04/05 

Date: Fri, 04 Feb 2005 16:21:53 GMT

tomstdenis@gmail.com wrote:
> The problem with this scheme is the set R requires high enough
> precision or you will have a lot of messages you can't decrypt. You
> can mitigate this by limiting the precision or using finite fields
> [e.g. GF(p)] but that's about it.

No, the precision is *absolute* by using symbolic calculation (like in
Mathematica or Maple).

> Also factoring polynomials is much easier than factoring integers. So
> once you factor the polynomial you're done for.
>
> ...Also you don't say what the trap door is. You find r_i from p....
> but p is the public key. Can't an attacker just find them as well?

The trick is to use "symbolic calculation" in order to prevent the use
of numerical algorithms (M has "symbolic" coefficients so the knowledge
of numerical solutions is useless).
As you know (Galois-Abel-Ruffini), is very difficult to find the
"symbolic" solutions of a polynomial equation of degree greater than 4.

But how can I create a polynomial equation with real or complex roots in
a way that those are not obvious?
If I write
34x^5 + 23x^4 + 2x^3 -7x^2 -76x + 43
the solutions are not obvious, but this is true even for who has created
the polynomial!

The sender should create the polynomial by multiplying very difficult to
find solutions:
{x-[(.....)^(1/4)/(......)^(1/3)]^(1/5)} * {x-[.....]} * ....
ecc...
but the polynomial will be "symbolically" very large. After an expansion
and a simplification, are the solutions still evident?

Kiuhnm