Re: Poly1305 vs. UMAC vs. new MAC1071

xmath <xmath.news@xxxxxxxxx> wrote:
Or is there a more straighforward way of using this "rational
preparation" in all cases? Unfortunately the paper is too old to be
found anywhere online...

A summary is in the 26 October 1995 entry on page 130 of Knuth's
``Changes to volume 2'' (err2-2e) available online. I see that Knuth
credits this particular approach to a 1970 technical report by Winograd
without Rabin. Anyway, Winograd's goal is to map _surjectively_ to
polynomials, whereas message authentication needs to map _injectively_
to polynomials, so there's no reason to think that the corner cases
should be handled the same way.

The underlying principle is that the polynomial (x^n + c) f(x) + g(x)
determines (n, c, f, g) if f and g are monic, deg f = deg g < n, and n
is a power of 2. The proof is constructive:

* determine n from the degree being in {n,...,2n-1};
* divide by x^n, obtaining quotient f and remainder cf+g;
* extract the coefficient of x^(deg f) from cf+g, obtaining c+1;
* subtract 1 from c+1, obtaining c;
* subtract cf from cf+g, obtaining g.

It's of course nicest if a message splits evenly between f and g, with
an extra coefficient in c. The simplest way I see to handle the non-nice
cases is to set c = 0, assuming as usual that real message coefficients
are nonzero; then f and g remain balanced. Some examples:

x+m0;
(x+m0)x^2 + (x+m1);
(x+m0)(x^2+m2) + (x+m1);
((x+m0)x^2+(x+m2))x^4 + (x+m1)x^2+(x+m3);
((x+m0)x^2+(x+m2))(x^4+m4) + (x+m1)x^2+(x+m3);
((x+m0)(x^2+m4)+(x+m2))x^4 + (x+m1)(x^2+m5)+(x+m3);
((x+m0)(x^2+m4)+(x+m2))(x^4+m6) + (x+m1)(x^2+m5)+(x+m3);
etc.

The rule here is that f encodes even coefficients, g encodes odd
coefficients, and c encodes the remaining coefficient if there is one.
But I can imagine all sorts of tweaks.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago
.

Relevant Pages

  • Integrating Rational Functions
    ... as a linear combination of a rational function, ... tangents of polynomials of degree 1, ... of which will have real number coefficients. ... has complex roots that show up in complex conjugate ...
    (sci.math)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: Genetic Algorithms for factorize multivariate polynomials
    ... integer powers rather than integer coefficients, ... and both of the candidate factor polynomials for these values. ... selection and no selection. ... and X and Y are different then in the offspring replace them with one ...
    (comp.ai.genetic)
  • functional translations and coefficient extraction (exponential sum decompositions)
    ... is the functional relation between exponentiation and translation ... and then coefficients of the inverse can be extracted ... which is precisely what is needed for the generalised berneulers ... also notice that this can be used on generalised trigonometric polynomials ...
    (sci.math)
Quantcast