The pseudonymous authors of an earlier paper [1] purport to show “why you cannot even hope to use Gröbner bases in cryptography,” although what they show, in fact, is that a particular scheme, often referred to as Polly Cracker, does not work. This scheme involves publishing some polynomials pi but keeping secret a term ordering and the corresponding Gröbner base B. Encryption involves adding a random combination of the pi to the message m, yielding c, and decryption consists of computing the normal form of c, which is m. In this paper, the authors show that if pi has three (or more) terms, then an attack based on the sparsity of the support can break the system. The authors, therefore, look at the case where all of the pi are binomials, that is X&agr;-X&bgr;. (This therefore ignores the case of hybrids of binomials and true polynomials. I am not convinced by this, nor by the dismissal of coefficients other than 1.)
Such a binomial corresponds to the vector &agr;-&bgr; in Zn, and so binomial ideals correspond to lattices and vice versa. The Goldreich-Goldwasser-Halevi scheme [2] is considered from this point of view, and a signature scheme that relies on the fact that the Gröbner base is small for an appropriate (hidden) term ordering is proposed. The NTRU encryption algorithm [3], although proposed as a polynomial system modulo Xn-1 rather than a lattice system, has lattice attacks. This paper considers a multivariate (in practice bivariate) version, Gröbner base NTRU (GB-NTRU), with a secret ideal I⊃ (Xn-1,Yn-1). The public key and encryption are identical to a bivariate NTRU, but more robust, since the parameters can have greater support, since decryption has extra knowledge I.
Was the earlier paper [1] wrong? This paper shows that there are other ways of using Gröbner bases that do seem to be useful. However, the jury is still out.
