Gröbner Basis Cryptosystems

§ 1 Gröbner Bases in Free Associative Algebras

K (commutative ) field Σ = {x_{1}, …, x_{n}} finite alphabet Σ^{∗} set of terms (or words) over Σ A term w is of the form w = x_{i_{1}}x_{i_{2}} ⋯ x_{i_{s}} K[Σ^{∗}] free associative K-algebra f ∈ K[Σ^{∗}] is of the form f = a_{1}w_{1} + ⋯ + a_{r}w_{r} with a_{i} ∈ K and w_{i} ∈ Σ^{∗}

Definition. A term ordering on Σ^{∗} is a well-ordering σ such that

1) w_{1} ≥_{σ} w_{2} ⇒ w_{3}w_{1}w_{4} ≥_{σ} w_{3}w_{2}w_{4}

2) w_{1}w_{2}w_{3} ≥_{σ} w_{2}

Examples. a) σ = llex length-lexicographic ordering

b) σ = tlex total lexicographic ordering

Definition. a) For f = a_{1}w_{1} + ⋯ + a_{r}w_{r} ∈ K[Σ^{∗}] \ {0}, the leading term of f is LT_{σ}(f) = max_{σ}{w_{i}}.

b) For a right-ideal I ⊆ K[Σ^{∗}], the leading term ideal of I is

LT_{σ}(I) = ⟨LT_{σ}(f) | f ∈ I \ {0}⟩

and the right leading term ideal of I is

LT_{σ}^{r}(I) = ⟨LT_{σ}(f) | f ∈ I \ {0}⟩_{r}

c) A subset G ⊆ I is called a σ-Gröbner basis of I if LT_{σ}(I) = ⟨LT_{σ}(g) | g ∈ G⟩. It is called a right σ-Gröbner basis of I if LT_{σ}^{r}(I) = ⟨LT_{σ}(g) | g ∈ G⟩_{r}.

Questions: 1) Do Gröbner bases exist?

2) Can they be computed?

3) What are they good for?

Definition. Let I ⊆ K[Σ^{∗}] be a right ideal and G ⊆ I.

a) The rewrite rule ⟶^{G} defined by G is the reflexive, transitive closure of all ⟶^{g} with g ∈ G, where f ⟶^{g} h means that there is a term w ∈ Supp (f) such that w = LT_{σ}(g)w′ and h = f − cgw′ with c ∈ K such that w ∉ Supp (h).

b) The rewrite rule ⟶^{G} is called Noetherian if every chain

f_{1} ⟶^{g_{1}} f_{2} ⟶^{g_{2}} ⋯ with g_{1}, g_{2}, …, ∈ G becomes eventually

stationary.

c) The rewrite rule ⟶^{G} is called confluent if f_{1} ⟶^{G} f_{2} and f_{1} ⟶^{G} f_{3} implies that there exists f_{4} such that f_{2} ⟶^{G} f_{4}

and f_{3} ⟶^{G} f_{4}.

Proposition 1.1. Let I ⊆ K[Σ^{∗}] be a right ideal and G ⊆ I.

a) The rewrite rule ⟶^{G} is Noetherian.

b) G is a right σ-Gröbner basis of I iff ⟶^{G} is confluent.

c) If ⟶^{G} is confluent, every element f ∈ K[Σ^{∗}] has a unique normal form NF_{σ,I}(f) such that f ⟶^{G} NF_{σ,I}(f) and such that NF_{σ,I}(f) cannot be reduced further.

Definition. Given f_{1}, f_{2} ∈ K[Σ^{∗}] and w_{1}, w_{2} ∈ Σ^{∗} such that 1) LT_{σ}(f_{1})w_{1} = w_{2} LT_{σ}(f_{2}),

2) w_{1} is not a multiple of LT_{σ}(f_{2}) and w_{2} is not a multiple of LT_{σ}(f_{1}), we call S(f_{1}, f_{2}, w_{1}, w_{2}) = \frac{1}{LC_{σ}(f_{1})} f_{1}w_{1} − \frac{1}{LC_{σ}(f_{2})} w_{2}f_{2} the S-polynomial of f_{1} and f_{2}.

Theorem 1.2. (Buchberger Criterion) Let I ⊆ K[Σ^{∗}] be a two-sided ideal and G ⊆ I an LTreduced subset. Then G is a σ-Gröbner basis of I if and only if S(g_{1}, g_{2}, w_{1}, w_{2}) ⟶^{G} 0 for all S-polynomials of elements g_{1}, g_{2} ∈ G.

Theorem 1.3. (Buchberger’s Algorithm) Let I = ⟨f_{1}, …, f_{s}⟩ be a two-sided ideal in K[Σ^{∗}]. Consider the following instructions.

1) Start with G = {g_{1}, …, g_{s}}, where g_{i} = f_{i}, and let B be the set of all S-polynomials involving elements of G.

2) If B = ∅, return G and stop. Otherwise, choose S = S(g_{i}, g_{j}, w_{i}, w_{j}) ∈ B and remove it from B.

3) Compute S′ = NR_{σ,G}(S). If S′ = 0, continue with step 2).

4) Append S′ to G and all S-polynomials involving S′ and previous elements of G to B. Continue with step 2).

This is a procedure such that G = {g_{1}, g_{2}, …} is a σ-Gröbner basis of I. If the procedure stops, the resulting set G is a finite σ-Gröbner basis of I.

Remarks. a) A finite σ-Gröbner basis of I need not exist.

b) If I has a finite Gröbner basis, we can effectively compute in the residue class ring K[Σ]/I.

c) If I is a finitely generated right ideal, it has a finite right σ-Gröbner basis which can be computed in finitely many steps.

§ 2. Gröbner Bases for Monoid Rings

M finitely presented monoid, i.e. M = Σ^{∗}/ ∼_{R}, where Σ^{∗} is the monoid of all terms in the alphabet Σ ∼_{R} is the congruence relation on Σ^{∗} generated by finitely many relations w_{1} ∼ w′_{1}, …, w_{r} ∼ w′_{r}. I_{M} = ⟨w_{1} − w′_{1}, …, w_{r} − w′_{r}⟩ ⊆ K[Σ^{∗}] K[M] = K[Σ^{∗}]/I_{M} monoid ring We assume that I_{M} has a finite Gröbner basis, i.e. that we can effectively compute in K[M]. Many computational problems for monoids and groups can be treated using Gröbner bases.

Proposition 2.1. (The Word Problem for Monoids) For w_{1}, w_{2} ∈ Σ^{∗}, the following conditions are equivalent:

1) w̄_{1} = w̄_{2} in M

2) w_{1} − w_{2} ∈ I_{M} (“ideal membership”)

Proposition 2.2. (The Generalized Word Problem for Monoids) Let S ⊆ M, and let ⟨S⟩ be the submonoid of M generated by S. For w ∈ Σ^{∗}, the following conditions are equivalent:

1) w̄ ∈ ⟨S⟩

2) w̄−1 ∈ K[s−1 | s∈S] ⊆ K[M] (“subalgebra membership”)

Prop. 2.3. (Generalized Word Problem for Groups) Let M be a group, S ⊆ M a finite subset, and U = ⟨S⟩ the subgroup of M generated by S. For w̄ ∈ K[M], the following conditions are equivalent:

1) w̄ ∈ U

2) w̄−1 ∈ ⟨s−1 | s ∈ S⟩_{r} ⊆ K[M] (“right ideal membership”)

Definition. Let f̄_{1}, …, f̄_{s} ∈ K[M].

a) The right K[M]-submodule Syz_{K[M]}^{r}(f̄_{1}, …, f̄_{s}) = {(ḡ_{1}, …, ḡ_{s}) ∈ K[M]^{s} | f̄_{1}ḡ_{1} + ⋯ + f̄_{s}ḡ_{s} = 0} of K[M]^{s} is called the right syzygy module of (f̄_{1}, …, f̄_{s}).

b) The right K[M]-module Syz_{K[M]}(f̄_{1}, …, f̄_{s}) = {(ḡ_{1}, …, ḡ_{s}, h̄_{1}, …, h̄_{s}) ∈ (K[M]^{op})^{s}⊕K[M]^{s} | ḡ_{1}f̄_{1}h̄_{1}+⋯+ ḡ_{s}f̄_{s}h̄_{s} = 0} is called the (two-sided) syzygy module of (f̄_{1}, …, f̄_{s}).

Prop. 2.4. (The Conjugation and the Conjugator Search Problem for Groups) 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, −w̄, w̄, e) | w̄ ∈ M} ≠ ∅

Proof: w̄_{1} = w̄_{3} w̄_{2} w̄_{3}^{−1} ⟺ e·w̄_{1} ·w̄_{3} −w̄_{3} ·w̄_{2} ·e = 0 □

§ 3. Gröbner Bases for Right Modules

F = ⨁_{λ∈Λ} K[Σ^{∗}] free K[Σ^{∗}]-module {e_{λ} | λ ∈ Λ} canonical basis of F U ⊆ F right submodule

Definition. a) A term in F is an element of the form e_{λ}w with λ ∈ Λ and w ∈ Σ^{∗}.

b) A module term ordering τ is a well-ordering on the set of terms in F such that

1) e_{λ}w_{1} ≤_{τ} e_{μ}w_{2} ⇒ e_{λ}w_{3}w_{1}w_{4} ≤_{τ} e_{μ}w_{3}w_{2}w_{4}

2) e_{λ} ≤_{τ} e_{λ}w for all w ∈ Σ^{∗}

c) For v = ∑_{λ∈Λ} e_{λ}w_{λ} ≠, the leading term of v is LT_{τ} (v) = max_{τ} {v_{λ} | v_{λ} ≠ 0}

d) The leading term module of U is the right submodule LT_{τ} (U) = ⟨LT_{τ} (v) | v ∈ U \ {0}⟩_{r} of F.

e) G ⊆ U is called a right τ-Gröbner basis of U if LT_{τ} (U) = ⟨LT_{τ} (g) | g ∈ G⟩_{r}.

Remarks. a) One can extend Buchberger’s Algorithm to right modules. Instead of S-polynomials one has to consider S-vectors S(v_{1}, v_{2}, w_{1}, w_{2}) = \frac{1}{LC_{τ} (v_{1})} v_{1} − \frac{1}{LC_{τ} (v_{2})} v_{2}w.

b) U has a finite right τ-Gröbner basis G. One can decide submodule membership and compute effectively in F/U. c) Every v ∈ F has a unique normal form v′ = NF_{τ,U}(v) which can be computed using G.

Proposition 3.1. (Macaulay Basis Theorem) The residue classes of the terms in

O_{τ} (U) = {e_{λ}w | λ ∈ Λ, w ∈ Σ^{∗}} \ LT_{τ} (U)

form a K-basis of F/U.

§ 4. Gröbner Basis Cryptosystems

M = Σ^{∗}/ ∼_{R} finitely presented monoid F = ⨁_{λ∈Λ} K[Σ^{∗}] free K[Σ^{∗}]-module τ module term ordering F̄ = F/I_{M} F free K[M]-module U ⊆ F right submodule which represents a right submodule Ū ⊆ F̄, i.e. such that I_{M} F ⊆ U

Public: F, τ, O_{τ} (U), vectors u_{1}, …, u_{s} ∈ U Secret: G right τ-Gröbner basis of U Encoding: A plaintext unit is a vector v ∈ ⟨O_{τ} (U)⟩_{K}, i.e. a linear combination v = c_{1}e_{λ_{1}}w_{1} + ⋯ + c_{r}e_{λ_{r}}w_{r} such that c_{i} ∈ K, λ_{i} ∈ Λ, and w_{i} ∈ Σ^{∗}. The corresponding ciphertext unit is w = v+u_{1}f_{1}+⋯+u_{s}f_{s} with “randomly” chosen f_{1}, …, f_{s} ∈ K[Σ^{∗}]. [Variant: w = (f_{0}, vf_{0} + u_{1}f_{1} + ⋯ + u_{s}f_{s})] Decoding: Using ⟶^{G}, compute v = NF_{σ,G}(w). [Variant: NF_{σ,G}(w) = vf_{0} and v = (vf_{0})/f_{0}.] Remarks. a) If the attacker can compute G, he can break the cryptosystem.

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

c) The computation of Gröbner bases is EXTSPACE-hard. (I.e. the amount of memory it requires increases exponentially with the size of the input.)

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

e) The free module F is not required to be finitely generated. Any concrete calculation will involve only finitely many components.

Example 1. K = 𝔽_{q} finite field M = ℕ^{n} = Σ^{∗}/ ∼_{R} where R = {x_{i}x_{j} ∼ x_{j}x_{i}} F = K[Σ^{∗}] non-commutative polynomial ring

τ = llex

K[M] = K[x_{1}, …, x_{n}] commutative polynomial ring

Public: F, τ, O_{τ} (U) = {1}, ū_{1}, …, ū_{s} ∈ K[M] commutative polynomials such that ū_{i}(a_{1}, …, a_{n}) = 0 Secret: (a_{1}, …, a_{n}) ∈ 𝔽_{q}^{n}, corresponding to the Gröbner basis {x_{1} − a_{1}, …, x_{n} − a_{n}} of the ideal Ū = (x_{1} − a_{1}, …, x_{n} − a_{n}) Encoding: A plaintext unit c ∈ 𝔽_{q} is encrypted as w = c + u_{1}f_{1} + ⋯ + u_{s}f_{s} with “randomly chosen” polynomials f_{1}, …, f_{s} ∈ K[M]. Decoding: c = w(a_{1}, …, a_{n}) = NF_{τ,G}(w)

This is Neil Koblitz’ polly cracker cryptosystem. Its disadvantage is that the attacker knows that there is an element in w + u_{1} · K[M] + ⋯ + u_{s} · K[M] which has support {1}. Hence many coefficients have to vanish. This allows a linear algebra attack.

Example 2. K = 𝔽_{2}, Σ = {x}, M = Σ^{∗} = ℕ K[M] = K[x] polynomial ring in one indeterminate p ≫ 0 prime number

F = ⨁_{i=1}^{p−1} K[x]ϵ_{i} ⊕ ⨁_{j=1}^{p−1} K[x]e_{j}

g generator of 𝔽_{q}^{∗} τ = PosDeg such that ϵ_{g^{p−1}} >_{τ} ⋯ >_{τ} ϵ_{g} >_{τ} ϵ_{1} >_{τ} >_{τ} e_{1} >_{τ} e_{g} >_{τ} ⋯ >_{τ} e_{g^{p−1}}

Public: F, τ, O_{τ} (U) = {e_{1}, e_{2}, …, e_{p−1}}, b = g^{a}(mod p), {u_{1}, …, u_{s}} = {ϵ_{1} −e_{1}, xϵ_{i} −ϵ_{gi}, xe_{j} −e_{bj} | i, j = 1, …, p−1} where all indices are computed modulo p. Secret: a ∈ {1, …, p − 1}, G = {u_{1}, …, u_{s}} ∪ {ϵ_{i} − e_{i^{a}} | i = 1, …, p − 1} τ-Gröbner basis of U = ⟨G⟩ Encryption: A plaintext unit is of the form e_{1} + e_{c} with c ∈ {0, …, p − 1}. Using the variant, we randomly choose k ∈ {0, …, p − 1} and form x^{k}(e_{1} + e_{c}). By adding suitable elements u_{i} we compute x^{k}(e_{1}+e_{c}) = x^{k}ϵ_{1}+x^{k}e_{c} = ϵ_{g^{k}} +e_{cb^{k}} in F/⟨u_{1}, …, u_{s}⟩. The ciphertext unit is w = ϵ_{g^{k}} + e_{cb^{k}}. Decryption: NF_{τ,U}(w) = NF(e_{b^{k}} + e_{cb^{k}}) = NF(x^{k}(e_{1} + e_{c})). In order to divide this vector by x^{k}, it suffices to compute c = (cb^{k})/(b^{k}) in 𝔽_{p} and to form e_{1} + e_{c}.

This is the Gröbner basis version of the ElGamal cryptosystem. 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, the attacker has to 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 ϵ_{i} by using just one reduction step ϵ_{g^{k}} ⟶ ϵ_{g^{ka}}.

Example 3. Let K = 𝔽_{2}, Σ = {x, y}, M = ℕ^{2} K[M] = K[Σ^{∗}]/⟨xy − yx⟩ = K[x, y] polynomial ring p, q ≫ 0 prime numbers, n = pq

F̄ = ⨁_{i∈(ℤ/nℤ)^{∗}} K[x, y]ϵ_{i}, τ = DegLexPos

Public: F (and thus n), τ, O_{τ} (U) = {ϵ_{i} | i ∈ (ℤ/nℤ)^{∗}}, e ∈ (ℤ/(p − 1)(q − 1)ℤ)^{∗}, {u_{1}, …, u_{s}} = {xϵ_{i} − ϵ_{i^{e}}, xyϵ_{j} − ϵ_{j} | i, j ∈ (ℤ/nℤ)^{∗}} Secret: p, q, a number d ∈ {1, …, n − 1} which satisfies de = 1(mod p−1) and de = 1(mod q −1), and the τ-Gröbner basis G = {u_{1}, …, u_{s}}∪{yϵ_{i} −ϵ_{i^{d}} | i ∈ (ℤ/nℤ)^{∗}} of U = ⟨G⟩. Encryption: A plaintext unit is a vector ϵ_{c} ∈ O_{τ} (U). To encrypt it, we form xyϵ_{c} and add elements of {u_{1}, …, u_{s}} to obtain the cyphertext unit w = yϵ_{c^{e}}. Decryption: Compute NF_{τ,U}(yϵ_{c^{e}}) = NF_{τ,U}(ϵ_{c^{ed}}) = ϵ_{c}.

This is the Gröbner basis version of the RSA cryptosystem. If the attacker is able to factor n, he can break the code. It is easy to see that this is equivalent to being able to find d. In the Gröbner basis version, the problem the attacker faces is that he doesn’t know the Gröbner basis elements yϵ_{i} − ϵ_{i^{d}} which are not even elements of the submodule ⟨u_{1}, …, u_{s}⟩ that he knows.

Example 4: Let K be a field and M = Σ^{∗}/ ∼_{R} a finitely presented group. K[M] = K[Σ^{∗}]/I_{M} F̄ = ⨁_{w̄∈M} ϵw̄ K[M] ⊕ ⨁_{w̄∈M} ew̄ K[M] free right K[M]-module τ = llex such that ϵw̄ >_{τ} eū for all w, u ∈ Σ^{∗}

Public: F, τ, g, g′ ∈ M such that g′ = a^{−1}ga, O_{τ} (U) = {ew̄ | w̄ ∈ M}, and {u_{λ} | λ ∈ Λ} = {ϵ_{i}h − ϵ_{h^{−1}ih}, ϵ_{g} − e_{g′}, e_{j}k − e_{k^{−1}jk} | i, j, h, k ∈ M} Secret: a ∈ M, or equivalently, the τ-Gröbner basis G = {u_{λ} | λ ∈ Λ} ∪ {ϵ_{i} − e_{a^{−1}ia} | i ∈ M} of U = ⟨G⟩_{r} ⊆ F Encryption: A plaintext unit m ∈ M is written in the form ϵ_{g} + e_{g′m̃}, where m̃ = bmb^{−1}. Then we multiply by the “randomly” chosen element b ∈ {c ∈ M | ca = ac} and use the elements u_{λ} to compute w = ϵ_{b^{−1}gb} + e_{b^{−1}g′m̃b}.

Decryption: Compute NF_{τ,G}(w) = NF_{τ,G}(e_{a^{−1}g′′a}+e_{b^{−1}g′bm}) = NF_{τ,G}(e_{b^{−1}g′b} + e_{b^{−1}g′b m}), where g′′ = b^{−1}gb. Then determine m from the relation m = (b^{−1}g′bm)/(b^{−1}g′b). This is Gröbner basis version of an ElGamal like cryptosystem based on a group with a “hard” conjugator search problem (e.g. braid groups). The attacker can break the code if he can determine a from g and g′ = a^{−1}ga. The advantage of knowing the Gröbner basis of 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.

§ 5. A Possible Generalization

• If one wants to have a theory of Gröbner bases for a ring (like K[Σ^{∗}] or K[M]), it has to be a residue class ring of a path algebra.

• The ring K[Σ^{∗}] is the path algebra of the graph

• By using path algebras of more general graphs Γ, it is possible to build “hard” computational problems from graph theory into the computation of Gröbner bases for ideals or modules over the ring K[Γ].

Conclusions

• For two-sided ideals in K[Σ^{∗}], Gröbner bases exist, but they may not be finite.

• For finitely generated right ideals and right submodules of free modules over K[Σ^{∗}], finite right Gröbner bases exist and are computable.

• If the appropriate Gröbner basis exists, one can solve — the word problem for monoids

— the generalized word problem for monoids and groups — the conjugation problem for groups

— the conjugator search problem for groups

• Gröbner basis cryptosystems rely on the inherent difficulty of computing certain Gröbner bases.

• Many classical cryptosystems can be viewed as Gröbner basis cryptosystems:

— Koblitz’ polly cracker (and its generalizations)

— ElGamal (based on discrete log)

— RSA (based on integer factorization)

— Conjugator search cryptosystems (e.g. in braid groups)

• The difficulty of computing the Gröbner basis in question can be based on a number of factors:

— computing Gröbner bases is EXTSPACE-hard

— the attacker does not know the submodule U whose Gröbner basis he needs

— the free module has a large (or infinite) rank

— the operation of K[Σ^{∗}] on the basis vectors of F encodes difficult computational problems (e.g. discrete log or integer factorization)

— the structure of the base ring K[Γ] encodes difficult computational tasks (e.g. from graph theory or combinatorics)

• For certain Gröbner basis computations, there are guaranteed lower complexity bounds.