AAECC manuscript No. (will be inserted by the editor)

Gröbner Basis Cryptosystems

Peter Ackermann and Martin Kreuzer

Fachbereich Mathematik, Universität Dortmund, D-44221 Dortmund, Germany

e-mail: peter.ackermann, martin.kreuzer@mathematik.uni-dortmund.de

January 14, 2005

Abstract In the first sections we extend and generalize Gröbner basis theory to submodules of free right modules over monoid rings. Over free monoids, we adapt the known theory for right ideals and prove versions of Macaulay’s basis theorem, the Buchberger criterion, and the Buchberger algorithm. Over monoids presented by a finitely generated convergent string rewriting system we generalize Madlener’s Gröbner basis theory based on prefix reduction from right ideals to right modules. After showing how these Gröbner basis theories relate to classical group-theoretic problems, we use them as a basis for a new class of cryptosystems that are generalizations of the cryptosystems described in [2] and [8]. Well known cryptosystems such as RSA, El-Gamal, Polly Cracker, Polly Two and a braid group cryptosystem are shown to be special cases. We also discuss issues related to the security of these Gröbner basis cryptosystems.

Key words Gröbner basis, cryptosystem, monoid ring

Mathematics Subject Classification (1991): Primary 94A60; Secondary 11T71, 13P10, 16-08

1 Introduction

In recent years, algebraic cryptosystems experienced a considerable increase in active interest, mainly due to the braid group based cryptosystem suggested in [1]. In this paper we want to unite recent attempts at group based cryptosystems with earlier suggestions by Neal Koblitz and others in a commutative setting (see [8] and [14]). Unfortunately, these earlier suggestions met a very polemic response by the Gröbner basis community (see the paper by Boo Barkee et al. [2]; note that Boo was the name of Moss Sweedler’s former dog). In the following years, there were only scattered attempts to rescue these Polly Cracker type cryptosystems, for instance in [29] and [18]. We find it particularly ironic that one of the authors of that polemic paper [2], Teo Mora aka. Theo Moriarty, had already helped to develop the very Gröbner basis theory for non-commutative rings which we feel is destined to overcome those initial objections (see [23], [24], and [25]).

Let us explain the basic setup. For non-commutative rings, there are several types of Gröbner basis theories. The natural way of defining Gröbner bases for free associative algebras (i.e. non-commutative polynomial rings) has been generalized to so-called basic algebras by Edward Green and his co-workers (see [6], [10], and [11]). These algebras are characterized by the property that they have a multiplicative vector space basis on which there exists a term ordering. Alas, for the monoid and group rings we are interested in such bases are usually not available. Thus we resort to another generalization of Mora’s approach: Klaus Madlener, Birgit Reinert, and their co-workers (see [19], [20], [21], [22], and [27]) have successfully described a Gröbner basis theory for monoid and group rings based on a presentation of the monoid or group by a convergent term rewriting system.

In Sections 2, 3, and 4 we extend this theory to the case of submodules of finitely generated right or two-sided free modules over monoid rings. Furthermore, we prove a general version of Macaulay’s basis theorem (see 2.2) which plays a key role in our cryptosystems, and we formulate generalizations of Buchberger’s algorithm for enumerating Gröbner bases (see 2.7 and 4.12). In Section 5 we show how one can solve well-known problems (such as the word problem, the subgroup problem, the conjugacy problem, and the conjugator search problem) if one succeeds in computing a Gröbner basis of the appropriate module.

Then we introduce a new class of Gröbner basis cryptosystems in Section 6. We show that this class contains the original Polly Cracker cryptosystems (see [8] and [14]), Ly’s Polly Two system (see [29] and [30]), the RSA cryptosystem (see [28]), the ElGamal cryptosystem (see [5]), and certain group based cryptosystems derived from [15]. Other special cases are the non-commutative polynomial cryptosystems of [26]. The underlying idea of our cryptosystems is straightforward: the plain text units are normal forms of elements w.r.t. a finitely generated module, encryption is achieved by adding a random element of the module, and decryption uses a Gröbner basis of the module and a reduction process to compute the normal form again. The security of such cryptosystems is based on a number of facts:

• Gröbner bases are usually difficult to compute

• the attacker knows only part of the module for which he wants to compute a Gröbner basis; the Gröbner basis of this part may be infinite

• the action of the monoid ring on the module can encode hard combinatorial and number theoretic problems

• the structure of the base ring may encode hard algebraic and combinatorial problems

In Section 7 we consider the efficiency of the computations that are involved when using the cryptosystem. Moreover we discuss how one can meet various attacks on the system.

A more general discussion about these and related issues follows in the last section, together with some suggestions for generating further secure instances of Gröbner basis cryptosystems.

2 Gröbner Bases for Right Modules over Free Monoid Rings

In the following we let Σ = {x_{1}, …, x_{n}} be a finite alphabet. The monoid of words (or terms) generated by Σ will be denoted by Σ^{∗}. Its elements are of the form w = x_{i_{1}} ⋯ x_{i_{s}} with i_{1}, …, i_{s} ∈ {1, …, n}. Its neutral element is the empty word λ, and its multiplication is given by concatenation.

Let K be a field. The free monoid ring (or the free associative algebra or the non-commutative polynomial ring) of Σ^{∗} over K is the set consisting of all formal sums ∑_{i=1}^{s} c_{i}w_{i} with c_{i} ∈ K and w_{i} ∈ Σ^{∗} together with the obvious addition and the multiplication defined by extending the multiplication in Σ^{∗} linearly.

Our goal in this section is to develop some parts of a Gröbner basis theory for submodules of finitely generated free right modules over the free monoid ring K[Σ^{∗}]. We shall content ourselves with introducing those results that are necessary to define and study the cryptosystems in Section 6. We begin by recalling the basics of the Gröbner basis theory for two-sided and right ideals of K[Σ^{∗}] described in [20], [21], [22], and [27].

Let σ be a term ordering on Σ^{∗}, i.e. a total ordering such that:

1. The inequality w_{1} ≤_{σ} w_{2} implies w_{3}w_{1}w_{4} ≤_{σ} w_{3}w_{2}w_{4} for all elements w_{1}, w_{2}, w_{3}, w_{4} ∈ Σ^{∗}.

2. Every descending chain of terms w_{1} ≥_{σ} w_{2} ≥_{σ} ⋯ in Σ^{∗} is eventually stationary, i.e. σ is a well-ordering.

Then every f ∈ K[Σ^{∗}] \ {0} has a unique representation f = ∑_{i=1}^{s} c_{i}w_{i} with c_{i} ∈ K\{0} and w_{i} ∈ Σ^{∗} such that w_{1} >_{σ} w_{2} >_{σ} ⋯ >_{σ} w_{s}. The term LT_{σ}(f) = w_{1} is called the leading term of f. Moreover, we let LC_{σ}(f) = c_{1} be the leading coefficient of f and LM_{σ}(f) = c_{1}w_{1} .

Given a two-sided ideal I ⊆ K[Σ^{∗}], the leading term ideal of I is defined to be the two-sided ideal generated by the leading terms of the non-zero elements of I and is denoted by LT_{σ}^{∗}(I) = ⟨LT_{σ}(f) | f ∈ I \ {0}⟩. A set of elements {f_{i} | i ∈ Λ} ⊆ I is called a σ -Gröbner basis of I if LT_{σ}^{∗}(I) = ⟨LT_{σ}(f_{i}) | i ∈ Λ⟩.

Similarly, given a right ideal I ⊆ K[Σ^{∗}], the right leading term ideal of I is defined to be the right ideal generated by the leading terms of the nonzero elements of I and is denoted by LT_{σ}(I) = ⟨LT_{σ}(f) | f ∈ I \ {0}⟩_{ϱ}. (The subscript ϱ will be used to denote right modules, right generation, etc.) A set of elements {f_{i} | i ∈ Λ} ⊆ I is called a right σ -Gröbner basis of I if LT_{σ}(I) = ⟨LT_{σ}(f_{i}) | i ∈ Λ⟩_{ϱ}.

Now we extend this theory to submodules of free right modules over the ring K[Σ^{∗}]. Let Φ be a finite or countably infinite set, and let F_{ϱ} be the free right K[Σ^{∗}]-module with basis {e_{i} | i ∈ Φ}. The elements of F_{ϱ} can be represented as formal sums ∑_{i∈Φ} e_{i}f_{i} where all but finitely many of the elements f_{i} ∈ K[Σ^{∗}] are zero. Furthermore, let U ⊆ F_{ϱ} be a finitely generated right submodule. In this situation we introduce Gröbner bases as follows.

Definition 2.1 A term in F_{ϱ} is an element of the form e_{i}m with i ∈ Φ and m ∈ Σ^{∗}. The set of all terms in F will be denoted by 𝕋(F_{ϱ}). If t = e_{i}m ∈ 𝕋(F_{ϱ}) is a term and c ∈ K by ct we will mean e_{i}cm.

A module term ordering on 𝕋(F_{ϱ}) is a total ordering τ such that:

1. The inequality t_{1} ≤_{τ} t_{2} implies t_{1}w ≤_{τ} t_{2}w for all t_{1}, t_{2} ∈ 𝕋(F_{ϱ}) and w ∈ Σ^{∗}.

2. Every descending chain of terms t_{1} ≥_{τ} t_{2} ≥_{τ} ⋯ in 𝕋(F_{ϱ}) is eventually stationary, i.e. τ is a well-ordering.

Given a module term ordering τ and an element v = ∑_{i=1}^{s} c_{i}t_{i} ∈ F_{ϱ}\{0} with c_{i} ∈ K \ {0} and t_{i} ∈ 𝕋(F_{ϱ}) satisfying t_{1} >_{τ} ⋯ >_{τ} t_{s}, we say that LT_{τ} (v) = t_{1} is the leading term of v and LC_{τ} (v) = c_{1} its leading coefficient. Moreover, we let LM_{τ} (v) = c_{1}t_{1} .

The right submodule LT_{τ} (U) = ⟨LT_{τ} (v) | v ∈ U \ {0}⟩_{ϱ} of F_{ϱ} is called the (right) leading term module of U, the set LT_{τ} {U} = {LT_{τ} (v) | v ∈ U \ {0}} the leading term set of U.

Finally, a set of non-zero vectors {v_{i} | i ∈ Λ} in U is called a (right) τ -Gröbner basis of U if we have LT_{τ} {U} = {LT_{τ} (v_{i})w | i ∈ Λ, w ∈ Σ^{∗}}.

Note that G = {v_{i} | i ∈ Λ} is a right τ -Gröbner basis of U if and only if LT_{τ} (U) = ⟨LT_{τ} (v_{i}) | i ∈ Λ⟩_{ϱ}.

The following result will become essential for our cryptosystems.

Proposition 2.2 (Macaulay’s Basis Theorem) Let τ be a module term ordering on 𝕋(F_{ϱ}) and U ⊆ F_{ϱ} a right submodule. Then the residue classes of the terms in 𝕋(F_{ϱ}) \ LT_{τ} {U} form a K-basis of F_{ϱ}/U.

Proof For b ∈ F_{ϱ} let b̄ ∈ F_{ϱ}/U denote the corresponding residue class. First suppose the residue classes of 𝕋(F_{ϱ}) \ LT_{τ} {U} do not generate F_{ϱ}/U. Let m ∈ F_{ϱ} such that m̄ ∉ ⟨b̄ | b ∈ 𝕋(F_{ϱ}) \ LT_{τ} {U}⟩_{K} =: A. Since τ is a well ordering we may assume that m has minimal leading term with respect to τ among all elements of F whose residue classes are not contained in A. If LT_{τ} (m) ∈ 𝕋(F_{ϱ}) \ LT_{τ} {U} then m − LM_{τ} (m) also has residue class not in A, but has a smaller leading term, a contradiction. If LT_{τ} (m) ∈ LT_{τ} {U} then there exists u ∈ U with LT_{τ} (u) = LT_{τ} (m). But then m− \frac{LC_{τ} (m)}{LC_{τ} (u)}u has residue class not in A but has a smaller leading term than m, giving again a contradiction. Therefore the residue classes of 𝕋(F_{ϱ}) \ LT_{τ} {U} generate F_{ϱ}/U.

Now suppose that ∑_{i=1}^{k} c_{i}b̄_{i} = ¯0 with k ≥ 1, c_{i} ∈ K \ {0}, and terms b_{i} ∈ 𝕋(F_{ϱ}) \ LT_{τ} {U}. This means that ∑_{i=1}^{k} c_{i}b_{i} ∈ U. But then LT_{τ} (∑_{i=1}^{k} c_{i}b_{i}) ∈ LT_{τ} {U} ∩ (𝕋(F_{ϱ}) \ LT_{τ} {U}), a contradiction. ⊓ ⊔

A Gröbner basis of U allows us to compute for each residue class in F_{ϱ}/U a representative that is a K -linear combination of elements of 𝕋(F_{ϱ}) \ LT_{τ} {U}. Gröbner bases can be characterized via the corresponding reduction systems.

Definition 2.3 Let v, w ∈ F_{ϱ}. If there exist a term e_{i}m_{1} ∈ Supp(w) and m_{2} ∈ Σ^{∗} such that LT_{τ} (v)m_{2} = e_{i}m_{1} then we say that v reduces w to w′ = w − c LC_{τ} (v)^{−1}vm_{2} in one step, denoted by w ⟶^{v} w′. Here c ∈ K is the coefficient of e_{i}m_{1} in w. If G ⊆ F_{ϱ} is a set of vectors we let ⟶^{G} denote the reflexive and transitive closure of ⋃_{g∈G} ⟶^{g}. This means that we

write v ⟶^{G} w if there exists a sequence v ⟶^{g_{1}} v_{1} ⟶^{g_{2}} ⋯ ⟶^{g_{k}} w of reduction steps where k ≥ 0, g_{i} ∈ G. By ⟷^{G} we denote the reflexive, symmetric, and transitive closure of ⋃_{g∈G} ⟶^{g}.

A reduction system ⟶^{G} is called Noetherian if there are no infinite rewriting sequences. It is called confluent if for all v, w_{1}, w_{2} such that v ⟶^{G} w_{1} and v ⟶^{G} w_{2} there exists w_{3} such that w_{1} ⟶^{G} w_{3} and w_{2} ⟶^{G} w_{3} . It is called locally confluent if for all g_{1}, g_{2} ∈ G and all v, w_{1}, w_{2} such that

v ⟶^{g_{1}} w_{1} and v ⟶^{g_{2}} w_{2} there exists w_{3} such that w_{1} ⟶^{G} w_{3} and w_{2} ⟶^{G} w_{3} .

A reduction system that is Noetherian and confluent is called convergent.

If ⟶^{G} is a Noetherian reduction system then ⟶^{G} is confluent if it is locally confluent. In general this implication does not hold.

Proposition 2.4 Let τ be a module term ordering on 𝕋(F_{ϱ}), let U ⊆ F_{ϱ} be a right submodule, and let G = {g_{1}, …, g_{s}} ⊆ U \{0} be a generating set for U. Furthermore we assume that the field K has effective arithmetic.

1. The term rewriting system ⟶^{G} is convergent if and only if G is a τ - Gröbner basis of U.

2. Let G be a τ -Gröbner basis of U, and let v ∈ F_{ϱ}. There exists a unique element NF_{U}(v) ∈ F_{ϱ} with v ⟶^{G} NF_{U}(v) and such that NF_{U}(v) is irreducible with respect to ⟶^{G}. This element is effectively computable. It is called the normal form of v w.r.t. U. It does not depend on the choice of the Gröbner basis G.

3. For every v ∈ F_{ϱ}, the normal form NF_{U}(v) is a K -linear combination of the elements in 𝕋(F_{ϱ}) \ LT_{τ} {U}.

Proof ¿From the fact that τ is a module term ordering it immediately follows that the term rewriting system ⟶^{G} is Noetherian.

Suppose that G is a τ -Gröbner basis for U. Let m ∈ F_{ϱ} and suppose that m′, m′′ ∈ F_{ϱ} are irreducible w.r.t ⟶^{G} and m ⟶^{G} m′, m ⟶^{G} m′′. Then m′−m′′ is irreducible as well and m′−m′′ ∈ U. But since G is a τ -Gröbner basis we must have m′ − m′′ = 0 showing that ⟶^{G} is confluent.

Now suppose that ⟶^{G} is convergent. For all u ∈ U, we have u ⟷^{G} 0. But if two elements are equivalent with respect to some convergent rewriting system they have the same irreducible normal form, so u ⟶^{G} 0, and hence LT_{τ} (u) ∈ {LT_{τ} (v_{i})w | i = 1, …, s, w ∈ Σ^{∗}}. Altogether, we have shown the first claim.

Macaulay’s Basis Theorem yields the equality of vector spaces F_{ϱ} = U ⊕ ⟨𝕋(F_{ϱ}) \ LT_{τ} {U}⟩_{K}. An element v = u + w ∈ F with u ∈ U and w ∈ ⟨𝕋(F_{ϱ}) \ LT_{τ} {U}⟩_{K} is reduced by ⟶^{G} to w in finitely many steps, yielding the second and third claim. ⊓ ⊔

Definition 2.5 Let v, v′ ∈ F_{ϱ}. If there exists a term r ∈ Σ^{∗} such that LT_{τ} (v)r = LT_{τ} (v′) or LT_{τ} (v) = LT_{τ} (v′)r then the vector S(v, v′) = LC_{τ} (v)^{−1}vr − LC_{τ} (v′)^{−1}v′ or S(v, v′) = LC_{τ} (v)^{−1}v − LC_{τ} (v′)^{−1}v′r, respectively, is called the S-vector of v and v′.

In this setting we have the following criterion for Gröbner bases.

Proposition 2.6 (The Buchberger Criterion) A set of generators G of a right submodule U ⊆ F_{ϱ} is a τ -Gröbner basis of U if and only if we have S(g_{1}, g_{2}) ⟶^{G} 0 for every S-vector S(g_{1}, g_{2}) of elements g_{1}, g_{2} ∈ G.

Proof If G is a τ -Gröbner basis then by Proposition 2.4 ⟶^{G} is convergent. Since every S-vector S(g_{1}, g_{2}) of elements g_{1}, g_{2} is in U or, equivalently, S(g_{1}, g_{2}) ⟷^{G} 0 this implies that S(g_{1}, g_{2}) ⟶^{G} 0.

Now suppose that S(g_{1}, g_{2}) ⟶^{G} 0 for every S-vector of elements g_{1}, g_{2} ∈ G. We want to show that ⟶^{G} is confluent. Since ⟶^{G} is Noetherian it suffices to show that ⟶^{G} is locally confluent, i.e. if a vector m ∈ F_{ϱ} can be reduced to both m_{1} = m−c_{j}g_{j}w_{j} and m_{2} = m−c_{k}g_{k}w_{k} in one step where c_{j}, c_{k} ∈ K \ {0}, g_{j}, g_{k} ∈ G and w_{j}, w_{k} ∈ Σ^{∗} then there exists m_{3} ∈ F_{ϱ} such that m_{1} ⟶^{G} m_{3} and m_{2} ⟶^{G} m_{3} . First suppose that in this situation LT_{τ} (g_{j})w_{j} ≠ LT_{τ} (g_{k})w_{k}. Without loss of generality let LT_{τ} (g_{j})w_{j} >_{τ}

LT_{τ} (g_{k})w_{k}. If LT_{τ} (g_{k})w_{k} is not a term in g_{j}w_{j} then m_{1} ⟶^{g_{k}} m − c_{j}g_{j}w_{j} −

c_{k}g_{k}w_{k} and m_{2} ⟶^{g_{j}} m − c_{j}g_{j}w_{j} − c_{k}g_{k}w_{k}. If LT_{τ} (g_{k})w_{k} is a term in g_{j}w_{j}

with coefficient c ∈ K \ \{0\} then m_{1} ⟶^{g_{k}} m − c_{j}g_{j}w_{j} − (c_{k} − \frac{c_{j}c}{LC_{τ} (g_{k})})g_{k}w_{k}

and m_{2} ⟶^{g_{j}} m − c_{j}g_{j}w_{j} − c_{k}g_{k}w_{k} ⟶^{g_{k}} m − c_{j}g_{j}w_{j} − (c_{k} − \frac{c_{j}c}{LC_{τ} (g_{k})})g_{k}w_{k}. So,

if LT_{τ} (g_{j})w_{j} ≠ LT_{τ} (g_{k})w_{k} then m_{3} exists independently on any conditions

on ⟶^{G}.

Now suppose LT_{τ} (g_{j})w_{j} = LT_{τ} (g_{k})w_{k}. Then m_{2} − m_{1} = c_{j}g_{j}w_{j} − c_{k}g_{k}w_{k} is a multiple of S(g_{j}, g_{k}) so by our assumption we have m_{2} −

m_{1} ⟶^{G} 0. Let m_{2} − m_{1} ⟶^{g_{i_{1}}} f_{1} = (m_{2} − m_{1}) − c_{i_{1}}g_{i_{1}}w_{i_{1}} ⟶^{g_{i_{2}}} ⋯ ⟶^{g_{i_{l}}} 0 with

g_{i_{j}} ∈ G be a sequence of reduction steps. Then LT_{τ} (g_{i_{1}})w_{i_{1}} ∈ Supp(m_{1}) or LT_{τ} (g_{i_{1}})w_{i_{1}} ∈ Supp(m_{2}). Let c′_{1} and c′_{2} be the coefficient of LT_{τ} (g_{i_{1}}w_{i_{1}}) in m_{1} and m_{2} respectively where at most one of c′_{1} and c′_{2} is zero. With a slight abuse of notation in the case that one of the coefficients is zero we have

c_{i_{1}} = c′_{2} − c′_{1} , m_{1} ⟶^{g_{i_{1}}} h′_{1} = m_{1} − c′_{1}g_{i_{1}}w_{i_{1}} and m_{2} ⟶^{g_{i_{1}}} h′_{2} = m_{2} − c′_{2}g_{i_{1}}w_{i_{1}} ,

so f_{1} = h′_{2} − h′_{1} . By induction on l there exist h_{1}, h_{2} ∈ F_{ϱ} such that m_{1} ⟶^{G} h_{1} , m_{2} ⟶^{G} h_{2} and h_{2} − h_{1} = 0 yielding the confluence of ⟶^{G}. ⊓ ⊔

Easy examples show that not every right submodule of F_{ϱ} has a finite Gröbner basis, even if both F_{ϱ} and the submodule are finitely generated. However, the following generalization of Buchberger’s algorithm (and of the Knuth-Bendix completion procedure) provides us at least with a procedure for enumerating a Gröbner basis. We say that a selection strategy for elements from a set B is fair if no element stays in B forever, i.e. if it is not possible that the addition of new elements to B delays the selection forever.

Theorem 2.7 (The Buchberger Algorithm) Let U be a right submodule of F_{ϱ}, and let G = {g_{1}, …, g_{s}} be a system of generators of U. Consider the following sequence of instructions:

1. Let s′ = s and B = {(i, j) | 1 ≤ i < j ≤ s′ and g_{i}, g_{j} have a nontrivial S-vector}.

2. If B = ∅, return the result G. Otherwise choose a pair (i, j) ∈ B using a fair strategy and delete it from B.

3. Using ⟶^{G}, reduce S(g_{i}, g_{j}) as much as possible, i.e. until we reach an element S′(g_{i}, g_{j}) that is irreducible with respect to ⟶^{G}. If the result is zero, continue with step 2.

4. Increase s′ by one. Append g_{s′} = S′(g_{i}, g_{j}) to G, and append the set of pairs {(i, s′) | g_{i}, g_{s′} have a nontrivial S-vector} to B. Then continue with step 2.

This is a procedure that enumerates a τ -Gröbner basis G of U. If U has a finite τ -Gröbner basis, it stops after finitely many steps and the resulting tuple G is a finite τ -Gröbner basis of U.

Proof For every pair g, g′ in the output G we have S(g, g′) ⟶^{G} 0 by construction of G if the S-vector of g, g′ exists. By Proposition 2.6 the set G is a Gröbner basis.

If there exists a finite Gröbner basis G′ = {g′_{1}, …, g′_{k}} then, since the procedure enumerates a Gröbner basis G, for each j = 1, …, k there is g_{i_{j}} ∈ G such that LT_{τ} (g_{i_{j}}) divides LT_{τ} (g′_{j}). But then LT_{τ} {U} = {LT_{τ} (g′_{j})w | j = 1, …, k, w ∈ Σ^{∗}} ⊆ {LT_{τ} (g_{i_{j}})w | j = 1, …, k, w ∈ Σ^{∗}} ⊆ {LT_{τ} (g_{i})w | i = 1, …, max{i_{1}, …, i_{k}}, w ∈ Σ^{∗}} ⊆ LT_{τ} {U} shows that {g_{1}, …, g_{max{i_{1},...,i_{k}}}} is a Gröbner basis of U. Therefore, after the

procedure has appended g_{max{i_{1},...,i_{k}}} to G, we have S(g_{i}, g_{j}) ⟶^{G} 0 for all (i, j) ∈ B. Thus no element is appended to G anymore and the procedure halts after treating all (i, j) ∈ B. ⊓ ⊔ 3 Gröbner Bases for Two-Sided Modules over Free Monoid Rings

In this section we give a brief account of a Gröbner basis theory for submodules of two-sided free modules over free monoid rings, since this theory will be applied in Section 5 to the conjugator search problem.

Let F be a two-sided free module over K[Σ^{∗}] with basis {e_{i} | i ∈ Φ} where Φ is finite or countably infinite. By this we mean the K[Σ^{∗}]-bimodule consisting of elements of the form ∑_{i∈Φ} ∑_{j∈ℕ} f_{ij}e_{i}g_{ij} where all but finitely many of the elements f_{ij}, g_{ij} ∈ K[Σ^{∗}] are zero and where we identify cfe_{i}g and fe_{i}cg for c ∈ K and f, g ∈ K[Σ^{∗}]. Multiplication is defined by (h_{1}, h_{2})fe_{i}g = h_{1}fe_{i}gh_{2} for (h_{1}, h_{2}) ∈ K[Σ^{∗}] × K[Σ^{∗}]. Furthermore, let U ⊆ F be a two-sided submodule. In this setting, Definition 2.1 can be adjusted as follows.

Definition 3.1 A term in F is an element of the form me_{i}m′ with i ∈ Φ and m, m′ ∈ Σ^{∗}. The set of all terms in F will be denoted by 𝕋(F).

A module term ordering on 𝕋(F) is a total ordering τ such that:

1. The inequality t_{1} ≤_{τ} t_{2} implies w_{3}t_{1}w_{4} ≤_{τ} w_{3}t_{2}w_{4} for all t_{1}, t_{2} ∈ 𝕋(F) and w_{3}, w_{4} ∈ Σ^{∗}.

2. Every descending chain of terms t_{1} ≥_{τ} t_{2} ≥_{τ} ⋯ in 𝕋(F) is eventually stationary, i.e. τ is a well-ordering. Given a module term ordering τ and a non-zero element v = ∑_{i=1}^{s} c_{i}t_{i} ∈

F with c_{i} ∈ K \ {0} and t_{i} ∈ 𝕋(F) satisfying t_{1} >_{τ} ⋯ >_{τ} t_{s}, we say that LT_{τ}^{∗}(v) = t_{1} is the leading term of v and LC_{τ}^{∗}(v) = c_{1} its leading coefficient. Moreover, we let LM_{τ}^{∗}(v) = c_{1}t_{1} .

The two-sided submodule LT_{τ}^{∗}(U) = ⟨LT_{τ} (v) | v ∈ U \ {0}⟩ of F is called the (two-sided) leading term module of U, the set LT_{τ}^{∗}{U} = {LT_{τ}^{∗}(v) | v ∈ U \ {0}} the leading term set of U.

Finally, a set of vectors {v_{i} | i ∈ Λ} in U \ {0} is called a (twosided) τ -Gröbner basis of U if we have LT_{τ}^{∗}{U} = {w_{1} LT_{τ}^{∗}(v_{i})w_{2} | i ∈ Λ, w_{1}, w_{2} ∈ Σ^{∗}}.

Since we are not going to use them, we leave it to the reader to write down the two-sided versions of Propositions 2.2 and 2.4. However, we want to explain the computation of two-sided Gröbner bases. The definition of S-vectors and critical pairs now reads as follows.

Definition 3.2 Let f, g ∈ F. If there exist ℓ, r ∈ Σ^{∗} such that we have LT_{τ}^{∗}(f) = ℓ LT_{τ}^{∗}(g)r or LT_{τ}^{∗}(f)r = ℓ LT_{τ}^{∗}(g) or ℓ LT_{τ}^{∗}(f) = LT_{τ}^{∗}(g)r or ℓ LT_{τ}^{∗}(f)r = LT_{τ}^{∗}(g) then the vector S(f, g) = LC_{τ}^{∗}(f)^{−1}f −LC_{τ}^{∗}(g)^{−1}ℓgr or S(f, g) = LC_{τ}^{∗}(f)^{−1}fr−LC_{τ}^{∗}(g)^{−1}ℓg or S(f, g) = LC_{τ}^{∗}(f)^{−1}ℓf−LC_{τ}^{∗}(g)^{−1}gr or S(f, g) = LC_{τ}^{∗}(f)^{−1}ℓfr−LC_{τ}^{∗}(g)^{−1}g, respectively, is called the S-vector of f and g.

Using this definition, both the Buchberger Criterion 2.6 and the Buchberger Algorithm 2.7 hold true without modifications and with the same proofs. Thus there is also a procedure for enumerating a two-sided Gröbner basis of a two-sided submodule of the two-sided free module F.

4 Gröbner Bases for Modules over Monoid Rings

In this section we consider a finitely presented monoid M = Σ^{∗}/ ∼_{W} where ∼_{W} is the equivalence relation on Σ^{∗} generated by a finite number of relations w_{1} ∼ w′_{1} , …, w_{r} ∼ w′_{r}. We shall use a multiplicative notation for M. Let K be a field. The monoid ring of M over K is the K -algebra

K[M] = {∑_{i=1}^{s}a_{i}t_{i} | a_{1}, …, a_{s} ∈ K \ {0}, t_{1}, …, t_{s} ∈ M}

with K -basis M and multiplication induced by extending the multiplication of M linearly.

Remark 4.1 For a finitely presented monoid M as above, the monoid ring of M has a presentation K[M] ≅ K[Σ^{∗}]/I_{M} where K[Σ^{∗}] is the free monoid ring and I_{M} is the two-sided ideal I_{M} = ⟨w_{1} − w′_{1}, …, w_{r} − w′_{r}⟩.

Assumptions. From now on we shall always assume that there exists a term ordering σ on Σ^{∗} such that w_{i} >_{σ} w′_{i} for i = 1, …, r, i.e. for the relations defining M, implying that the string rewriting system ⟶^{W} generated by w_{i} ⟶^{W} w_{i′} for i = 1, …, r is Noetherian. Moreover, we require that this string rewriting system is convergent. Unless explicitly stated otherwise, the elements of M shall be presented by the corresponding irreducible words in Σ^{∗} with respect to ⟶^{W}. For a, b ∈ M, let ab denote the product of a and b in M, a ⊙ b denote the concatenation of the corresponding words in Σ^{∗}, and ≡ denote the identity of words. In particular it follows that ab is the normal form of a ⊙ b w.r.t. ⟶^{W}.

Remark 4.2 The assumption that ⟶^{W} is a convergent string rewriting system implies that the ideal I_{M} has a finite two-sided σ -Gröbner basis G = {g_{1}, …, g_{r}} where g_{i} = w_{i} − w′_{i} for i = 1, …, r, and every element f ∈ K[Σ^{∗}] can be effectively reduced via ⟶^{G} to a unique normal form NF_{I_{M}} (f).

The remainder of this section is devoted to introducing and studying Gröbner bases for submodules of right free modules over K[M]. In the following we collect the necessary results generalizing the theory of prefix rewriting and prefix Gröbner bases for one-sided ideals of K[M] developed in [20], [21], [22], and [27]. A Gröbner basis theory for the two-sided case can be introduced in a similar way. However, we do not need it here so we omit it. Assumption. Let Φ be a finite or countably infinite set, and let \overline{F}_{ϱ} be the free right K[M]-module with basis \{ē_{i} | i ∈ Φ\}. The elements of \overline{F}_{ϱ} are of the form ∑_{i∈Φ} ē_{i}f_{i} where only finitely many of the elements f_{i} ∈ K[M] are non-zero. Furthermore, let \overline{U} ⊆ \overline{F}_{ϱ} be a finitely generated right submodule, and let τ be a module term ordering on 𝕋(F_{ϱ}) that is compatible with the term ordering σ on Σ^{∗}, i.e. for all i ∈ Φ and w_{1}, w_{2} ∈ Σ^{∗} with w_{1} <_{σ} w_{2} we have e_{i}w_{1} <_{τ} e_{i}w_{2} . Using the above assumption, we can view τ as an ordering on the set of terms

𝕋(\overline{F}_{ϱ}) = \{ē_{i} m | i ∈ Φ, m ∈ M\}

of \overline{F}_{ϱ}. Although τ is a module term ordering, we cannot expect an inequality ē_{i}m_{1} ≤_{τ} ē_{i}m_{2} to imply ē_{i}m_{1}m_{3} ≤_{τ} ē_{i}m_{2}m_{3} where i ∈ Φ and m_{1}, m_{2}, m_{3} ∈ M because the reductions via ⟶^{W} may destroy the inequality. So, for v ∈ \overline{F}_{ϱ} and m ∈ M, we may have LT_{τ} (vm) ≠ LT_{τ} (v)m. To get a Noetherian rewriting system, the appropriate definition of reduction is the following.

Definition 4.3 Let v, w ∈ \overline{F}_{ϱ} \ \{0\}. If there exist a term ē_{i}m_{1} ∈ Supp(w) and m_{2} ∈ M such that LT_{τ} (vm_{2}) = ē_{i}m_{1} then we say that v strongly reduces w to w − c LC_{σ}(vm_{2})^{−1}vm_{2} in one step. Here c ∈ K is the coefficient of ē_{i}m_{1} in w.

Unfortunately, in general one cannot decide whether an equation sx = t is solvable for x in the monoid M. Therefore one cannot decide whether a vector w ∈ \overline{F}_{ϱ} can be strongly reduced by another one. To make this decision feasible, we introduce a weaker kind of reduction.

Definition 4.4 Let v, w ∈ \overline{F}_{ϱ} \ \{0\}. If there exist a term ē_{i} m_{1} ∈ Supp(w) and m_{2} ∈ M such that LT_{τ} (v) ⊙ m_{2} ≡ ē_{i}m_{1} , we say that v prefix reduces w to w′ = w − c LC_{τ} (v)^{−1}vm_{2} in one step and we write w ⟶^{v}_{π} w′. Here c ∈ K is the coefficient of ē_{i}m_{1} in w.

In the situation of this definition we have LT_{τ} (vm_{2}) = LT_{τ} (v) ⊙ m_{2} . Therefore the term rewriting system generated by prefix reduction steps is Noetherian. By using prefix reduction instead of strong reduction we gain computability, but another problem arises. We have to pay the price that given a set of generators G of U and a vector v ∈ U we do not necessarily have v ⟷^{G}_{π}0. This additional property can be achieved by prefix saturation.

Definition 4.5 A subset S ⊆ \overline{F}_{ϱ} is called prefix saturated if we have vm ⟶^{S}_{π} 0 in one step for all v ∈ S and all m ∈ M.

Proposition 4.6 Let S ⊆ \overline{F}_{ϱ} be prefix saturated. Then we have v ⟷^{S}_{π} 0 for all v ∈ ⟨S⟩_{ϱ}.

Proof Let v ∈ ⟨S⟩_{ϱ}. We write v = ∑_{i=1}^{k} c_{i}w_{i}m_{i} with c_{i} ∈ K, w_{i} ∈ S, and m_{i} ∈ M. We proceed by induction on k. For k = 0, the claim holds obviously true. Since S is prefix saturated, there exists an element w̃ ∈ S such that w_{k}m_{k} ⟶^{w̃}_{π} 0. Hence we have c_{k}w_{k}m_{k} = c̃w̃m̃ for some element m̃ ∈ M. Now we distinguish two cases. If LT_{τ} (w̃) ⊙ m̃ is not a term in the support of v then we have ∑_{i=1}^{k−1} c_{i}w_{i}m_{i} ⟶^{w̃}_{π} v. Otherwise, we have v ⟶^{w̃}_{π} v − c̃w̃m̃ ⟵^{w̃}_{π} ∑_{i=1}^{k−1} c_{i}w_{i}m_{i}. The assertion now follows from the inductive hypothesis. ⊓ ⊔

There are examples for vectors v ∈ \overline{F}_{ϱ} for which there does not exist a finite prefix saturated set S such that ⟨v⟩_{ϱ} = ⟨S⟩_{ϱ}. However, the following procedure enumerates such a set.

Proposition 4.7 Let M = Σ^{∗}/ ∼_{W} be a finitely presented monoid, where the eqivalence relation ∼_{W} corresponds to the convergent term rewriting system ⟶^{W} generated by w_{i} ⟶ w′_{i} for i = 1, …, r. Given a vector v ∈ \overline{F}_{ϱ}, consider the following sequence of instructions.

1. Let Sat(v) = {v} and A = {v}.

2. Using a fair strategy, choose a vector w ∈ A and delete it from A. Write t = LT_{τ} (w) = ē_{i}m with i ∈ Φ and m ∈ M. Let C(t) = {m′ ∈ Σ^{∗} | m ≡ m′′ ⊙ r and r ⊙ m′ ≡ w_{j} for some j ∈ {1, …, r}, r ≠ λ}.

3. If C(t) = ∅, continue with step 5). Otherwise, choose m′ ∈ C(t) and delete it from C(t).

4. Compute the normal form w̃ of wm′ with respect to ⟶^{W}. If w̃ ≠ 0

and w̃ does not reduce to zero in one step using ⟶^{Sat(v)} then append w̃ to Sat(v) and to A and continue with step 3.

5. If A = ∅ then return Sat(v) and stop. Otherwise, continue with step 2.

This is a procedure that enumerates a prefix saturated set Sat(v) that generates the right module ⟨v⟩_{ϱ}.

Proof For a contradiction, suppose that the resulting set Sat(v) is not prefix saturated. Then there exist w ∈ Sat(v) and m ∈ M such that the term LT_{τ} (w) ⊙ m ∈ F_{ϱ} is minimal among all elements for which wm does not

reduce to zero via ⟶^{Sat(v)}. Then LT_{τ} (w) ⊙ m ∈ F_{ϱ} is necessarily reducible with respect to ⟶^{W}. Let LT_{τ} (w) = e_{i}m′ with m′ ∈ M. Since m′m is reducible with respect to ⟶^{W}, there exist decompositions m′ ≡ m′_{1} ⊙ m′_{2} and m ≡ m_{1}⊙m_{2} such that m_{1}, m_{2}, m′_{1}, m′_{2} ∈ M and m′_{2} ≠ λ and m′_{2}⊙m_{1} is the left side of ⟶^{W}.

Consequently, we have m_{1} ∈ C(LT_{τ} (w)). Let w̃ = NF_{W} (w ⊙ m_{1}). In step 4 of the procedure there are two possibilities. Either w̃ reduces to

zero via ⟶^{Sat(v)} or w̃ is appended to Sat(v) and A. In the former case there exists an element v′ ∈ Sat(v) such that LT_{τ} (wm_{1}) ≡ LT_{τ} (v′) ⊙ m_{3} and wm_{1} = cv′m_{3} for some c ∈ K and m_{3} ∈ M. Then the relations LT_{τ} (w)⊙m >_{τ} LT_{τ} (wm_{1})⊙m_{2} ≡ LT_{τ} (v′)⊙m_{3} ⊙m_{2} ≥_{τ} LT_{τ} (v′)⊙(m_{3}m_{2}) and the minimality of LT_{τ} (w) ⊙ m imply that wm reduces to zero via

⟶^{Sat(v)}_{π} , a contradiction. It remains to consider the case that w̃ does not

reduce to zero via ⟶^{Sat(v)} and hence is appended to Sat(v). The relations LT_{τ} (w) ⊙ m ≡ LT_{τ} (w) ⊙ m_{1} ⊙ m_{2} >_{τ} LT_{τ} (wm_{1}) ⊙ m_{2} ≡ LT_{τ} (w̃) ⊙ m_{2} and the minimality of LT_{τ} (w) ⊙ m imply that wm = w̃m_{2} reduces to zero via

⟶^{Sat(v)}_{π} , a contradiction again. ⊓ ⊔

In analogy to Proposition 2.4 we now introduce Gröbner bases for prefix rewriting.

Definition 4.8 Let \overline{U} be a right submodule of \overline{F}_{ϱ}. A set G ⊆ \overline{U} is called a prefix Gröbner basis of \overline{U} if we have u ⟷^{G}_{π} 0 for all u ∈ \overline{U} and if ⟶^{G} is confluent.

Remark 4.9 In analogy to Definition 2.1 the following holds: A set G ⊆ \overline{U} is a Gröbner basis of \overline{U} if and only if LT_{τ} \{\overline{U}\} = \{LT_{τ} (g) ⊙ m | g ∈ G, m ∈ M}.

Macaulay’s Basis Theorem also holds: If \overline{U} is a right submodule of \overline{F}_{ϱ} then the residue classes of the terms in 𝕋(\overline{F}_{ϱ}) \ LT_{τ} (\overline{U}) form a K -basis of \overline{F}_{ϱ}/\overline{U}.

In order to characterize prefix Gröbner bases by a Buchberger criterion, we need to define the proper notion of S-vectors.

Definition 4.10 Let v, w ∈ \overline{F}_{ϱ}. If there exists an element m ∈ M such that LT_{τ} (v)⊙m ≡ LT_{τ} (w) or LT_{τ} (v) ≡ LT_{τ} (w)⊙m then the element S(v, w) = LC_{τ} (v)^{−1}vm − LC_{τ} (w)^{−1}w or S(v, w) = LC_{τ} (v)^{−1}v − LC_{τ} (w)^{−1}wm, respectively, is called the S-vector of v and w.

Proposition 4.11 (Buchberger Criterion for Prefix Gröbner Bases) Let G ⊆ \overline{F}_{ϱ} be a prefix saturated set. Then the set G is a prefix τ -Gröbner basis for ⟨G⟩_{ϱ} if and only if we have S(v, w) ⟶^{G}_{π} 0 for all S-vectors of elements v, w ∈ G.

Proof Let G be a prefix Gröbner basis, and let S(v, w) be an S-vector of elements v, w ∈ G. Since S(v, w) ∈ ⟨G⟩_{ϱ}, by Proposition 4.6 we have S(v, w) ⟷^{G}_{π} 0. Now the fact that 0 is irreducible with respect to ⟶^{G}_{π} easily implies that we actually have S(v, w) ⟶^{G}_{π} 0.

Conversely, assume that S(v, w) ⟶^{G}_{π} 0 for all S-vectors of v, w ∈ G. If we want to show that ⟶^{G}_{π} is confluent it suffices to consider the critical situations as in Proposition 2.6. These critical situations correspond to Svectors of elements of G and resolve if for all S-vectors S(v, w) we have S(v, w) ⟶^{G}_{π} 0. The remaining claim follows from Proposition 4.6. ⊓ ⊔

Finally, we provide a procedure for computing prefix Gröbner bases.

Theorem 4.12 (Buchberger Algorithm for Prefix Gröbner Bases) Let \overline{U} be a right submodule of \overline{F}_{ϱ}, let G = \{g_{1}, …, g_{s}\} by a system of generators of \overline{U}, and let τ be a module term ordering on 𝕋(F). Consider the following sequence of instructions.

1. Let H = G, A = G, S_{h} = {h} for all h ∈ G, s′ = s and B = {(i, j) | 1 ≤ i < j ≤ s′, g_{i}, g_{j} have a non-trivial S-vector}.

2. If A is empty, return H and stop. Otherwise start a computation of Sat(h) using Proposition 4.7 for every h ∈ A. If this procedure yields Sat(h) = S_{h}, remove h from A. Otherwise, stop the procedure when it has computed a finite subset S′_{h} of Sat(h) consisting of S_{h} and at least one more element. Append the elements of ⋃_{h∈A}(S′_{h} \ S_{h}) to H, increase s′ by the number s′′ of these new elements, and write H = {h_{1}, …, h_{s′}}. Set S_{h} = S′_{h} and append {(i, j) | 1 ≤ i < j ≤ s′, j > s′ − s′′, h_{i}, h_{j} have a non-trivial S-vector} to the set B.

3. If B = ∅, continue with step 2. Otherwise, use a fair strategy to choose a pair (i, j) ∈ B and delete it from B.

4. Using ⟶^{H}_{π} , reduce S(h_{i}, h_{j}) as much as possible and call the result S′(h_{i}, h_{j}). If S′(h_{i}, h_{j}) = 0, continue with step 2. Otherwise, increase s′ by one, set h_{s′} = S′(h_{i}, h_{j}) and append h_{s′} to H and A. Set S_{h_{s′}} = {h_{s′}}, append {(i, s′) | 1 ≤ i < s′, h_{i}, h_{s′} have a non-trivial S-vector} to the set B and continue with step 2.

This is a procedure that enumerates a prefix τ -Gröbner basis H of \overline{U}.

Proof The set H enumerated by the procedure is prefix saturated as it is the union of prefix saturated sets Sat(h). By construction we have S(h_{i}, h_{j}) ⟶^{H}_{π} 0 for all h_{i}, h_{j} ∈ H for that S(h_{i}, h_{j}) exists. The assertion now follows from Propositions 4.6 and 4.11. ⊓ ⊔

5 Some Classical Problems

As above, we let M = Σ^{∗}/ ∼_{W} be a finitely presented monoid, we let Φ be a finite or countably infinite set, and we let \overline{F}_{ϱ} be the free right K[M]- module with basis {ē_{i} | i ∈ Φ}. We continue to operate under the general assumptions introduced above. Moreover, we suppose that a right submodule \overline{U} ⊆ \overline{F}_{ϱ} is given by a finite tuple of generators U = (ū_{1}, …, ū_{s}) and that we know a prefix Gröbner basis of \overline{U}.

In this setting a number of classical problems for groups and monoids can be solved using Gröbner basis techniques. Therefore the original computational problem becomes the problem to find the correct Gröbner basis. Let us illustrate the method with some examples.

Proposition 5.1 (The Word Problem for Free Right Modules) Given two vectors v̄, w̄ ∈ \overline{F}_{ϱ}, we write v̄ − w̄ = ∑_{i∈Φ} ē_{i}f_{i} with f_{i} ∈ K[M]. Then the following conditions are equivalent:

1. v̄ = w̄

2. For all i ∈ Φ we have NF_{I_{M}} (f_{i}) = 0.

Notice that if we write the terms in the support of f_{i} in their normal form with respect to ⟶^{W}, we only have to check whether these normal forms are zero.

In free right K[M]-modules, we can solve the submodule membership problem as follows.

Proposition 5.2 (The Submodule Membership Problem) For a vector v̄ ∈ \overline{F}_{ϱ} the following conditions are equivalent:

1. v̄ ∈ \overline{U}

2. v̄ + \overline{U} = 0 in the module \overline{F} /\overline{U}

3. v̄ ⟶^{G}_{π} 0 for some prefix Gröbner basis G of \overline{U}.

Proof This follows immediately from Proposition 4.6.

The generalized word problem (also called the submonoid membership problem) was discussed in [20]. It was shown that it leads to a subalgebra membership problem in K[M]. For groups the situation is somewhat more accessible, since the subgroup membership problem is equivalent to a right ideal membership problem in K[M].

The next interesting monoid and group theoretic problems are the conjugacy problem and the conjugator search problem. Let us indicate some methods for solving them using Gröbner bases.

Definition 5.3 Let f_{1}, …, f_{s} ∈ K[M]. The two-sided submodule of the two-sided free module F = ⊕_{i=1}^{s} K[M]e_{i}K[M] generated by all elements ∑_{i=1}^{s} g_{i}e_{i}h_{i} such that g_{1}f_{1}h_{1} + ⋯ + g_{s}f_{s}h_{s} = 0 is called the syzygy module of the tuple (f_{1}, …, f_{s}). We shall denote it by Syz_{K[M]}(f_{1}, …, f_{s}).

In the case M = Σ^{∗}, there exist explicit descriptions of algorithms to compute syzygy modules (see [7] and [10]). For the general case, we can either lift the computation to K[Σ^{∗}] or construct a similar algorithm (see [3]). The computation of syzygy modules and the following easy proposition help us achieve our goal.

Proposition 5.4 Let M be a group. For w̄_{1}, w̄_{2} ∈ M, the following conditions are equivalent:

1. w̄_{1} = w̄_{3}w̄_{2}w̄_{3}^{−1} for some w̄_{3} ∈ M

2. Syz_{K[M]}(w_{1}, w_{2}) ∩ {e_{1}w̄ − w̄e_{2} | w̄ ∈ M} ≠ ∅

Proof It suffices to note that we have w̄_{1} = w̄_{3}w̄_{2}w̄_{3}^{−1} if and only if w̄_{1}w̄_{3} = w̄_{3}w̄_{2} , i.e. if and only if e_{1}w̄_{3} − w̄_{3}e_{2} is a syzygy of (w̄_{1}, w̄_{2}). ⊓ ⊔

Hence the conjugacy and the conjugator search problems have been reduced to finding certain very simple elements in a syzygy module. The latter task can be achieved by a straightforward generalization of the method in the commutative case (see [16] and [17]).

6 Gröbner Basis Cryptosystems

In this section we will propose a public key cryptographic primitive based on the Gröbner basis theory in the setting described so far. Note that to actually use this Gröbner basis cryptosystem one has to find instances that guarantee efficient computations where needed and security under certain assumptions. We show how one can realize well known public key cryptosystems as special cases of this cryptographic framework. Besides these examples we do not give concrete instances, however we will discuss how one can meet various attacks on the system in the next section.

In the following we continue to work in the described setting and use the assumptions of the earlier sections. In particular, we let M = Σ^{∗}/ ∼_{W} be a finitely presented monoid and assume that elements of M can be represented by normal forms that can be efficiently computed, e.g. by a convergent term rewriting system ⟶^{W}. Let σ be a ⟶^{W}-admissible term ordering on Σ^{∗}, F_{ϱ} be the free right K[Σ^{∗}]-module with basis {e_{i} | i ∈ Φ} and let τ be a module term ordering on 𝕋(F_{ϱ}) that is compatible with σ. Let \overline{F}_{ϱ} be the free right K[M]-module with basis \{ē_{i} | i ∈ Φ\} and let \overline{U} be a right submodule of \overline{F}_{ϱ}. Finally, we assume that we know a τ -Gröbner basis G of \overline{U} w.r.t. some reduction system that allows efficient computations of normal forms, and therefore the set O_{τ} (\overline{U}) = 𝕋(\overline{F}_{ϱ}) \ LT_{τ} \{\overline{U}\}.

Definition 6.1 A Gröbner basis cryptosystem consists of the following data.

1. Public information: the free module \overline{F}_{ϱ}, the set O_{τ} (\overline{U}), and finitely many vectors ū_{1}, …, ū_{s} ∈ \overline{U}

2. Secret key: a prefix Gröbner basis G of \overline{U}.

3. Encryption procedure: A plaintext is a vector m ∈ ⟨O_{τ} (\overline{U})⟩_{K}, i.e. a linear combination m = ē_{λ_{1}}c_{1}w_{1} + ⋯ + ē_{λ_{r}}c_{r}w_{r} such that c_{i} ∈ K, λ_{i} ∈ Φ, w_{i} ∈ M, and ē_{i}w_{i} ∈ O_{τ} (\overline{U}). Then the corresponding ciphertext is the vector w = m + ū_{1}f_{1} + ⋯ + ū_{s}f_{s} with suitably (e.g. randomly) chosen f_{1}, …, f_{s} ∈ K[M].

4. Decryption procedure: Using ⟶^{G}, compute m = NF_{τ,Ū}(w).

Note that the right choice of f_{1}, …, f_{s} ∈ K[M] in the encryption procedure can be crucial for the security of the cryptosystem and will depend on the concrete setting in which the primitive is used. For some settings this issue will be discussed in the next section.

Remark 6.2 We shall also consider the following variant: for the ciphertext we construct a pair w = (f_{0}, mf_{0} +ū_{1}f_{1} +⋯+ū_{s}f_{s}) where f_{0} ∈ K[M] is a further randomly chosen element. Then the decoding procedure consists of computing NF_{τ,Ū}(mf_{0} + ū_{1}f_{1} + ⋯ + ū_{s}f_{s}) = NF_{τ,Ū}(mf_{0}) and “dividing” by f_{0} to obtain m. In this way we achieve some additional data hiding: the summand mf_{0} on the right hand-side has the same shape as the other summands. However there is no general method for performing the “division” NF_{τ,Ū}(mf_{0}) ↦ m. We have to provide an explicit procedure in every individual example.

Let us collect some easy remarks about the merits of such a cryptosystem.

Remark 6.3 Let a Gröbner basis cryptosystem be given as above.

1. If an attacker can compute G, he can break the cryptosystem. In general, the computation of Gröbner bases is EXPSPACE-hard.

2. The attacker knows ū_{1}, …, ū_{s} and O_{τ} (\overline{U}), but not a system of generators of \overline{U}. We can make his task difficult by choosing ū_{1}, …, ū_{s} such that a Gröbner basis of ⟨ū_{1}, …, ū_{s}⟩_{ϱ} is hard to compute.

3. The advantage of using modules (rather than ideals in K[M]) is that one can encode hard combinatorial or number theoretic problems in the action of the terms on the canoncial basis vectors (see the examples below).

4. The free module F_{ϱ} is not required to be finitely generated. Any concrete calculation will involve only finitely many components.

Now we give some examples of Gröbner basis cryptosystems. In particular, we show that many classical cryptosystems can be realized as Gröbner basis cryptosystems.

Example 6.4 Let K = 𝔽_{q} be a finite field, where q = p^{e} with a prime number p and e > 0. Let M be the monoid M = ℕ^{n} = Σ^{∗}/ ∼_{W} where Σ = {x_{1}, …, x_{n}} and we require the relations W = {x_{j}x_{i} ∼ x_{i}x_{j} | 1 ≤ i < j ≤ n}. We use the free right module of rank one, i.e. \overline{F}_{ϱ} = K[M] = K[x_{1}, …, x_{n}] is the commutative polynomial ring. Choose a point (a_{1}, …, a_{n}) ∈ 𝔽_{p}^{n}. Let \overline{U} = (x_{1} − a_{1}, …, x_{n} − a_{n}) and choose elements ū_{1}, …, ū_{s} ∈ \overline{U}, i.e. ū_{i}(a_{1}, …, a_{n}) = 0. Consider the following Gröbner basis cryptosystem.

1. Public information: The one-dimensional free right module \overline{F}_{ϱ}, the set O_{τ} (\overline{U}) = \{1\}, and the commutative polynomials ū_{1}, …, ū_{s}.

2. Secret key: The point (a_{1}, …, a_{n}) ∈ 𝔽_{q}^{n} corresponding to the Gröbner basis G = \{x_{1} − a_{1}, …, x_{n} − a_{n}\} of the ideal \overline{U}.

3. Encryption procedure: A plaintext m ∈ 𝔽_{q} is encrypted as the polynomial w = m + ū_{1}f_{1} + ⋯ + ū_{s}f_{s} with randomly chosen polynomials f_{1}, …, f_{s} ∈ K[M].

4. Decryption procedure: Compute m = w(a_{1}, …, a_{n}) = NF_{τ,Ū}(w).

This is Neal Koblitz’ polly cracker cryptosystem (cf. [8] and [14]). Its disadvantage is that the attacker knows that there is an element in the set w+ū_{1}·K[M]+⋯+ū_{s}·K[M] that has support {1}. Hence many coefficients have to vanish. This allows a linear algebra attack (see [2], [8] and [14]).

A number of improvements of Koblitz’ original approach have been proposed (see for instance [18] and [29]). Many of them fit our scheme.

Example 6.5 In the setting of the preceding example, choose a second commutative polynomial ring Q = K[y_{1}, …, y_{m}] and polynomials g_{1}, …, g_{m} in K[M]. In this way there is a K -algebra homomorphism ϕ : Q ⟶ K[M] given by ϕ(y_{i}) = g_{i} for i = 1, …, m. Choose a point (ξ_{1}, …, ξ_{n}) ∈ 𝔽_{p}^{n} and elements f_{1}, …, f_{s} ∈ Q such that ϕ(f_{1}), …, ϕ(f_{s}) ∈ \overline{U} = (x_{1} −ξ_{1}, …, x_{n} − ξ_{n}). Now construct the following Gröbner basis cryptosystem.

1. Public information: The rings K[M] and Q, the homomorphism ϕ, the term O_{τ} (\overline{U}) = \{1\}, and the polynomials f_{1}, …, f_{s} ∈ Q.

2. Secret key: The point (ξ_{1}, …, ξ_{n}) ∈ K^{n}, or equivalently, the Gröbner basis {x_{1} − ξ_{1}, …, x_{n} − ξ_{n}} of the ideal Ū = (x_{1} − ξ_{1}, …, x_{n} − ξ_{n}) in K[M].

3. Encryption procedure: We proceed in a similar way to the variant above. A plaintext is an element m ∈ K. We choose random polynomials h ∈ (f_{1}, …, f_{s}) and h′ ∈ ker(ϕ) and a random exponent κ ∈ ℕ^{n}. Then we send (y^{κ}, my^{κ} + h + h′) where y = (y_{1}, …, y_{m}). In other words, an attacker knows the pair (ϕ(y)^{κ}, mϕ(y)^{κ} + ϕ(h)).

4. Decryption procedure: Compute v̄ = [mϕ(y)^{κ} + ϕ(h)](ξ_{1}, …, ξ_{n}) = mϕ(y)^{κ}(ξ_{1}, …, ξ_{n}) and obtain m = v̄/[ϕ(y)^{κ}(ξ_{1}, …, ξ_{n})].

This is Le Van Ly’s Polly Two cryptosystem (cf. [29]). Compared to Polly Cracker, it has the advantage that the usual linear algebra attacks do not work. It appears that an attacker has no choice but to compute a (possibly hard) Gröbner basis. Supposedly hard concrete instances of this cryptosystem have been suggested (see [30]).

Example 6.6 Let K = 𝔽_{2} , let Σ = {x, y}, and let M = ℕ^{2} = Σ^{∗}/ ∼_{W} with W = {yx ∼ xy}. Then K[M] = K[Σ^{∗}]/⟨yx − xy⟩ = K[x, y] is a commutative polynomial ring in two indeterminates. Moreover, let p, q ≫ 0 be two distinct prime numbers, let n = pq, and let Π = (ℤ/nℤ)^{×} be the set of residue classes prime to n. We use the free module \overline{F}_{ϱ} = ⨁_{i=0}^{n−1} e_{i} K[x, y] and the term ordering τ = DegLexPos. Choose a number ϵ ∈ (ℤ/(p−1)(q − 1)ℤ)^{×} and compute the inverse d of ϵ in (ℤ/(p − 1)(q − 1)ℤ)^{×}.

1. Public information: The module \overline{F}_{ϱ} (and thus the number n), the set O_{τ} (\overline{U}) = \{e_{0}, …, e_{n−1}\}, the number ϵ and the vectors \{u_{1}, …, u_{s}\} = {e_{i}x − e_{i^{ϵ}mod n} | i = 0, …, n − 1} ∪ {e_{i}xy − e_{i} | i = 0, …, n − 1}.

2. Secret key: The secret key consists of the primes p and q and the number d. Equivalently, the secret key is the τ -Gröbner basis G = {u_{1}, …, u_{s}}∪ \{e_{i}y − e_{i^{d}mod n} | i = 0, …, n − 1\} of \overline{U} = ⟨G⟩.

3. Encryption procedure: A plaintext is a vector e_{m} ∈ O_{τ} (\overline{U}). To encrypt it, we form e_{m} + (e_{m}xy − e_{m}) − (e_{m}x − e_{m^{ϵ}mod n})y ∈ e_{m} + \overline{U} to obtain the ciphertext w = e_{m^{ϵ}mod n}y.

4. Decryption procedure: Compute NF_{τ,Ū}(e_{m^{ϵ}mod n}y) = e_{m^{ϵd}mod n} = e_{m}.

It is easy to see that this is the Gröbner basis version of the RSA cryptographic primitive (see [28]) which is used to derive concrete instances of practical cryptosystems that are widely used in practice. If an attacker is able to factor n, he can break the code. This is equivalent to being able to find d. In the Gröbner basis version, the problem the attacker faces is that he does not know the Gröbner basis elements e_{i}y − e_{i^{d}mod n} .

Also discrete logarithms can be used in Gröbner basis cryptosystems.

Example 6.7 Let K = 𝔽_{2} , let Σ = {x}, and let M = Σ^{∗} = ℕ. Then K[M] = K[x] is a polynomial ring. Moreover, let p ≫ 0 be a prime number.

We use the K[x]-module F_{ϱ} = ⨁_{i=1}^{p−1} ϵ_{i} K[x] ⊕ ⨁_{j=1}^{p−1} e_{j}K[x] where ϵ_{i}, e_{j} are the standard basis vectors. Let g be a generator of the multiplicative group 𝔽_{p}^{×}, and let τ = DegPos with ϵ_{i} >_{τ} e_{j} for all i, j = 1, …, p − 1. Choose a number a ∈ {1, …, p − 1} and compute b = g^{a}mod p. Now we introduce the following Gröbner basis cryptosystem.

1. Public information: The module F_{ϱ}, the set O_{τ} (U) = {e_{1}, e_{2}, …, e_{p−1}}, the number b, and the vectors {u_{1}, …, u_{s}} = {ϵ_{1} − e_{1}} ∪ {ϵ_{i}x − ϵ_{gi} | i = 1, …, p − 1} ∪ {e_{j}x − e_{bj} | j = 1, …, p − 1} where all indices are computed modulo p.

2. Secret key: The number a ∈ {1, …, p − 1}, or equivalently, the τ -Gröb-ner basis G = \{u_{1}, …, u_{s}\} ∪ \{ϵ_{i} − e_{i^{a}} | i = 1, …, p − 1\} of \overline{U} = ⟨G⟩.

3. Encryption procedure: A plaintext is of the form e_{1} + e_{m} with a number m ∈ {0, …, p − 1}. Using the variant, we randomly choose a number k ∈ {0, …, p − 1}, form (e_{1} + e_{m})x^{k} and send the ciphertext w = ϵ_{g^{k}} + e_{mb^{k}} ∈ (e_{1} + e_{m})x^{k} + ⟨u_{1}, …, u_{s}⟩_{ϱ}.

4. Decryption procedure: We compute NF_{τ,Ū}(w) = e_{b^{k}} + e_{mb^{k}}. Since e_{b^{k}} +

e_{mb^{k}} ⟷^{G}(e_{1} + e_{m})x^{k}, we have to “divide” this vector by x^{k}. To this end, it suffices to compute m = (mb^{k})/(b^{k}) in 𝔽_{p} and to form e_{1} + e_{m}.

Clearly, this is the Gröbner basis version of the ElGamal cryptosystem (see [5]). It can be broken if the attacker is able to compute the discrete logarithm a of b = g^{a} or k of g^{k}. In the Gröbner basis version, an attacker can only reduce using ϵ_{g^{k}} ⟶^{u_{i}} ⋯ ⟶^{u_{j}} x^{k}ϵ_{1} ⟶^{u_{1}} x^{k}e_{1} which takes k ≫ 0 reduction steps. If one knows a, one can get rid of the vector ϵ_{g^{k}} by using just one reduction step ϵ_{g^{k}} ⟶ e_{g^{ka}} = e_{b^{k}}.

The next example uses non-commutative polynomials. In order to prevent linear algebra attacks (see next section) T. Rai suggested in his recent doctoral thesis [26] to construct Gröbner basis cryptosystems based on twosided ideals. The corresponding Gröbner basis theory was sketched in [20], [21], [22], [27] and Section 3.

Example 6.8 Let K be a (finite) field, let Σ = {x_{1}, …, x_{n}}, and let M = Σ^{∗}. Then K[M] is a non-commutative polynomial ring. We choose a twosided ideal I ⊆ K[M] for which we know a finite (two-sided) Gröbner basis G = {g_{1}, …, g_{t}} with respect to some term ordering τ.

1. Public information: The ring K[M], the set O_{τ} (U), and a finite subset {u_{1}, …, u_{s}} ∈ I such that computing a Gröbner basis of ⟨u_{1}, …, u_{s}⟩ is infeasible.

2. Secret key: The τ -Gröbner basis G of I.

3. Encryption procedure: A plaintext m is an element in ⟨O_{τ} (U)⟩_{K}. The corresponding ciphertext is w = m + f_{1}u_{1}g_{1} + ⋯ + f_{s}u_{s}g_{s} where the non-commutative polynomials f_{i}, g_{i} are suitably chosen so that in the computation of w leading term cancellation occurs (see [26], Section 4.1).

4. Decryption procedure: Compute m = NF_{τ,Ū}(w) using the Gröbner basis G.

In [26] several concrete instances of these cryptosystems are proposed. They offer good resistence to linear algebra attacks because using indeterminate coefficients for the polynomials f_{i} and g_{j} leads to systems of quadratic equations in these coefficients which cannot be solved using linear algebra. However, one has to take great care to make these cryptosystems secure against attackers who are able to compute partial Gröbner bases (see [26], Chapter 4).

Our approach is flexible enough to include recent attempts at group based cryptosystems. For instance, the following Gröbner basis cryptosystem relies on the difficulty of solving the conjugator search problem in certain groups.

Example 6.9 Let K be a field, and let M = Σ^{∗}/ ∼_{W} be a finitely presented group. We use the free right K[M]-module \overline{F} = ⨁_{w̄∈M} ϵw̄ K[M] ⊕ ⨁_{w̄∈M} ew̄ K[M] (possibly of infinite rank). Moreover, let τ = llexPos be such that ϵw̄ >_{τ} eū for all w, u ∈ M. Choose a, g ∈ M and compute g′ = a^{−1}ga. Now consider the following Gröbner basis cryptosystem.

1. Public information: The module \overline{F}_{ϱ}, the elements g, g′ ∈ M, a set B ⊆ {c ∈ M | ca = ac}, the set O_{τ} (U) = {ew̄ | w̄ ∈ M}, and the vectors {u_{λ} | λ ∈ Λ} = {ϵ_{i}h − ϵ_{h^{−1}ih} | i, h ∈ M} ∪ {ϵ_{g} − e_{g′}} ∪ {e_{j}k − e_{k^{−1}jk} | j, k ∈ M}.

2. Secret key: The element a ∈ M, or equivalently, the τ -Gröbner basis G = \{u_{λ} | λ ∈ Λ\} ∪ \{ϵ_{i} − e_{a^{−1}ia} | i ∈ M\} of the submodule \overline{U} = ⟨G⟩_{ϱ} of \overline{F}_{ϱ}.

3. Encryption procedure: Randomly choose an element b ∈ B. A plaintext m ∈ M is written in the form ϵ_{g} + e_{g′m̃}, where m̃ = bmb^{−1} . Then we multiply by b and use the elements u_{λ} to obtain the ciphertext w = ϵ_{b^{−1}gb} + e_{b^{−1}g′m̃b}.

4. Decryption procedure: Find NF_{τ,Ū}(w) = e_{a^{−1}g′′a} + e_{b^{−1}g′bm} = e_{b^{−1}g′b} + e_{b^{−1}g′b m} first, where g′′ = b^{−1}gb. Then determine m from m = (b^{−1}g′b)^{−1}(b^{−1}g′bm).

As one can readily check, this is a Gröbner basis version of an ElGamal like cryptosystem based on a group with a “hard” Diffie-Hellman conjugacy problem, i.e. the problem to find a^{−1}b^{−1}gba given g, a^{−1}ga and b^{−1}gb where a and b commute. One can solve this problem if given g and g′ = a^{−1}ga one can find a_{1}, a_{2} such that a_{1}ga_{2} = g′ and a_{1}, a_{2} commute with the elements from B. The advantage of knowing the Gröbner basis is that one can pass from ϵ_{g′′} to the corresponding e_{i} without going through ϵ_{g} ⟶ e_{g′}. The computation of that Gröbner basis is equivalent to finding a.

To perform the encryption step explicitly one has to perform the following simple computations in the group: Conjugate g′ with b to obtain b^{−1}g′b and multiply by the plaintext m. Conjugate g with b to obtain b^{−1}gb.

If we want to decrypt the ciphertext ϵ_{b^{−1}gb}+e_{b^{−1}g′m̃b} knowing the secret a an explicit decryption amounts to performing the following: Conjugate b^{−1}gb with a to obtain the Gröbner basis element ϵ_{b^{−1}gb}−e_{a^{−1}b^{−1}gba}, reduce w via this element in one step to NF_{τ,Ū}(w) = e_{a^{−1}b^{−1}gba} + e_{b^{−1}a^{−1}gabm} and obtain m by multiplying the inverse of the first index by the second index.

So all computations performed to encrypt and decrypt are actually computations in the group M.

In [15] braid groups have been suggested for this kind of cryptosystems. However in [4] it is shown that there is a polynomial time algorithm solving the Diffie-Hellman conjugacy problem in braid groups. If one chooses reasonable parameters this algorithm is not feasible today but it seems that a braid group based version of this cryptosystem is not secure in the future.

7 Efficiency and Security Considerations

Although we are not going to propose concrete examples of Gröbner basis cryptosystems, we are now going to discuss some issues one has to confront if one tries to construct hard instances. A. Efficiency. Both for encryption and decryption, the users of Gröbner basis cryptosystems have to be able to compute efficiently in the ring K[M] where K is a computable field and M a finitely presented monoid. The complexity of the multiplication in M is controlled by the convergent term rewriting system ⟶^{W}. However, for efficient computations in F_{ϱ} we also have to make sure that the supports of the elements we use do not get too large.

In particular, this constraint has to be taken into account when one has to compute the normal form NF_{τ,G} in the decryption procedure. To make the necessary reduction steps feasible, we have to choose the Gröbner basis G suitably. Some possibilities are apparent from the examples above:

a) If G and w are binomials, all reduction steps yield binomials, i.e. the support of all elements consists of at most two terms.

b) If G and w are homogeneous and have bounded degrees with respect to some grading, there may exist bounds on the number of terms in the support of the elements computed during w ⟶^{W} NF_{τ,Ū}(w) and on the number of reduction steps.

c) If the set 𝕋(F_{ϱ}) \ LT_{τ} {U} is small, the coefficients of NF_{τ,Ū}(w) can be found by applying suitable K -linear maps to the terms in the support of w (see Example 6.4). B. Linear Algebra Attacks. Several types of linear algebra attacks have been proposed that apply to special Gröbner basis cryptosystems.

1) The basic type is the attack proposed in the original paper [8]. In the equation w = m + ū_{1}f_{1} + ⋯ + ū_{s}f_{s}, the attacker regards the coefficients of f_{1}, …, f_{s} as unknowns and tries to solve the resulting linear system of equations. In our setup, it is possible to make this attack infeasible: By choosing a large set O_{τ} (U), we can make the plaintext m “similar” to the ciphertext w. By using a module of large rank, we can make the solution of this linear system infeasible. Moreover, since we are working over a monoid or group ring, many products (e_{i}t)t′ with e_{i}t ∈ Supp(ū_{j}) and t′ ∈ Supp(f_{j}) can be made to yield the same term, so that the corresponding coefficients cannot be recovered.

2) The “intelligent” linear algebra attack suggested by H.W. Lenstra and described in [14] is based on the idea that in the equation w = m + ū_{1}f_{1} + ⋯ + ū_{s}f_{s} one can guess the terms t occuring in the support of ū_{1}, …, ū_{s} if t · Supp(f_{i}) intersects Supp(w), and that the list of all such terms is not too large. As before, in our approach this attack can be repelled in several ways, namely by working over group rings or by using a free module of large rank. In each case sufficient cancellation happens during the computation of the cyphertext.

C. The Differential Attack. In [12] and [13] D. Hofheinz and R. Steinwandt described a “differential” attack on the Polly Cracker cryptosystem. This attack uses the observation that in an expansion w = m + ū_{1}f_{1} + ⋯ + ū_{s}f_{s} the quotients of terms in the support of w sometimes allow conclusions about the shape of the supports of the elements ū_{1}, …, ū_{s}. In our setting, this attack can be repelled in the very same way as the “intelligent” linear algebra attack described above.

D. The Attack Using Characteristic Terms. If a representation w = m+ū_{1}f_{1} +⋯+ū_{2}f_{2} is such that there are terms in w that do not belong to O_{τ} (U) and therefore not to Supp(m) then it is sometimes possible to reveal individual messages by performing suitable linear algebra on the coefficients of w and f_{1}, …, f_{s}, in particular when there exist “characteristic terms”, i.e. terms that occur in just one of the elements f_{i}. By recognizing multiples of these terms in the ciphertext one can reconstruct a constant message unit. As before this attack rests on the fact that plaintext units are small, i.e. that O_{τ} (U) is small. Furthermore, if several products t · t′ with t ∈ Supp(ū_{i}) and t′ ∈ Supp(f_{i}) contribute to one coefficient of w this attack becomes infeasible. Thus the defensive measures described above apply.

E. Chosen Ciphertext Attacks. In the proposed cryptosystems the receiver has no method for detecting invalid ciphertexts. In addition, since decryption is K -linear, the chosen ciphertext attacks described in [9] and [14] are possible. However by using suitable hash functions the system can be made secure in the way described in [30]: The sender appends a suitable random value to his message, computes the hash value of the result, and transmits the ciphertext of the message, the ciphertext of the random value, and the hash value.

8 Discussion and Further Suggestions

Let us point out some reasons for the choices we made in presenting Gröbner basis cryptosystems and some possibilities for further generalization and improvement.

• In the original Polly Cracker cryptosystem, an attacker has several advantages that allow him to use linear algebra methods. For instance, he knows (or guesses) that the normal form of the ciphertext with respect to an unknown Gröbner basis is very simple. Since no cancellation occurs when one multiplies terms in a polynomial ring, this means that many coefficients have to vanish. Using a similar system over the monoid ring of a large monoid with a sufficient amount of cancellation foils this attack. This is the reason why we think it is advisable to use monoid rings as base rings.

• The fact that Gröbner basis theory works for modules and not just rings gives us another degree of freedom: we can encode the action of a monoid on a set (namely the set of basis vectors of a free module). Hard instances of such actions are known.

• By leaving the world of commutative rings, we gain another advantage. In most cases, submodules of free modules over non-commutative rings do not have a finite Gröbner basis, and even the computation of partial (“truncated”) Gröbner bases may not be practical. Therefore it is not difficult to create sets of vectors {u_{1}, u_{2}, …} such that the module ⟨u_{1}, u_{2}, …⟩ has no “reasonable” Gröbner basis whereas a larger module (that is kept secret) does.

• An alternative, large class of non-commutative algebras for which there exists a well-developed Gröbner basis theory is the class of path algebras (see e.g. [10], [11]). Using these algebras as base rings, we can introduce a new kind of complexity: the oriented graph underlying a path algebra can incorporate hard combinatorial problems. We believe that this aspect deserves to be examined further in the future.

• Altogether, we can conclude that Gröbner basis cryptosystems allow us to combine several difficult computational problems coming from separate areas of mathematics. We think they form a suitable framework for searching for new hard instances.

Acknowledgements The authors are grateful to the Graduiertenkolleg “Mathematische und ingenieurwissenschaftliche Methoden für sichere Datenübertragung und Informationsvermittlung” and to H. Dobbertin for supporting the Dortmund workshop. Moreover, we thank D. Grigoriev, G. Rosenberger, and Springer Verlag for enabling us to disseminate these results to a wide audience.

References

1. I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), 287–291 2. Boo Barkee et al., Why you cannot even hope to use Gröbner bases in public

key cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed, J. Symb. Comput. 18 (1994), 497–501

3. H. Bluhm, Syzygienberechnung in nichtkommutativen Polynomringen, Diplomarbeit, Universität Dortmund 2005

4. J.H. Cheon and B. Jun, A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem, in: Advances in Cryptology – CRYPTO 2003, Lect. Notes Comp. Sci. 2729, Springer, 2003, pp. 212–225

5. T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory 31 (1985), 469–472

6. D. Farkas, C. Feustel, and E. Green, Synergy in the theories of Gröbner bases and path algebras, Canad. J. Math. 45 (1993), 727–739

7. D. Farkas, E. Green, E. Kirkman, and J. Kuzmanovich, Constructing projective resolutions, Comm. in Alg. 21 (1993), 1869–1887

8. M. Fellows and N. Koblitz, Combinatorial cryptosystems galore!, Contemp. Math. 168 (1994), 51–61

9. W. Geiselmann and R. Steinwandt, Cryptanalysis of Polly Cracker, IEEE Transactions on Inf. Theory 48 (2002), 2990–2991

10. E. Green, Noncommutative Gröbner bases and projective resolutions, in: P. Dräxler (ed.) et al., Computational methods for representations of groups and algebras, Proc. Euroconference Essen, Germany, April 1–5, 1997, Progress in Math. 173, Birkhäuser, Basel 1999, 29–60

11. E. Green, Multiplicative bases, Gröbner bases, and right Gröbner bases, J. Symb. Comput. 29 (2000), 601–623

12. D. Hofheinz, Angriffe auf das Public-Key-System Polly Cracker, Studienarbeit, Universität Karlsruhe 2003

13. D. Hofheinz and R. Steinwandt, A “differential” attack on Polly Cracker, Extended abstract in Proceedings of the 2002 IEEE International Symposium on Information Theory, p.211

14. N. Koblitz, Algebraic aspects of cryptography, Alg. in Comp. and Math. 3, Springer, Heidelberg 1998

15. K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, and C. Park, New public-key cryptosystems using braid groups, in: Advances in cryptology – CRYPTO 2000, Lect. Notes Comp. Sci. 1880, Springer, 2000, pp. 166–183

16. M. Kreuzer and L. Robbiano, Computational commutative algebra 1, Springer, Heidelberg 2000

17. M. Kreuzer and L. Robbiano, Computational commutative algebra 2, Springer, Heidelberg 2004 (to appear)

18. F. Levy-dit-Vehel and L. Perret, A Polly Cracker system based on satisfiability, Progress Comp. Sci. Applied Logic 23, Birkhäuser, 2004, pp. 177–192

19. K. Madlener and F. Otto, Some applications of prefix-rewriting in monoids, groups, and rings, Reports on Computer Algebra 22, Universität Kaiserlautern 1998

20. K. Madlener and B. Reinert, Computing Gröbner bases in monoid and group rings, in: M. Bronstein (ed.), Proc. Conf. ISSAC 1993, ACM Press, New York 1993, 254–263

21. K. Madlener and B. Reinert, Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings, Theor. Comp. Sci. 208 (1998), 3–31

22. K. Madlener and B. Reinert, String rewriting and Gröbner bases – a general approach to monoid and group rings, in: M. Bronstein, J. Grabmeier, and V.

Weispfenning (eds.), Symbolic Rewriting Techniques, Proc. Workshop Monte Verita 1995, Progress in Comp. Sci. and Appl. Logic 15, Birkhäuser, Basel 1998, pp. 127–180

23. T. Mora, Gröbner bases for non-commutative polynomial rings, in: Proc. Conf. AAECC 4, Lect. Notes Comp. Sci. 229, Springer, Berlin 1986, pp. 353–362

24. T. Mora, Gröbner bases in non-commutative algebras, in: Proc. Conf. ISSAC 1988, Lect. Notes Comp. Sci. 358, Springer, Berlin 1989, pp. 150–161

25. T. Mora, An introduction to commutative and noncommutative Gröbner bases, Theor. Comp. Sci. 134 (1994), 131–173

26. T. Rai, Infinite Gröbner bases and noncommutative Polly Cracker cryptosystems, dissertation, Virginia Polytechnic Institute, Blacksburg 2004

27. B. Reinert, On Gröbner bases in monoid and group rings, dissertation, Universität Kaiserslautern 1995

28. R. Rivest, A. Shamir, and L.N. Adleman, A method for obtaining digital signatures and public key cryptosystems, Comm. of the ACM 21 (1978), 120–126

29. L. Ly, Gröbner Basen und das Kryptoverfahren Polly Two, dissertation, Universität Bochum 2003

30. L. Ly, Polly two – a new algebraic polynomial-based public-key scheme, this volume