Oracle-supported drawing of the Groebner escalier

الأصل · EN

The aim of this note is to discuss the following quite queer Problem: GIVEN i) the free non-commutative polynomial ring, P:= F X₁,,Xₙ (public), ii) a bilateral ideal I⊂ F X₁,,Xₙ (private), iii) a finite set G:= {g₁,,gₗ}⊂ I of elements of the ideal I (public), a noetherian semigroup term-ordering, (private), on the word semigroup T:= < X₁,,Xₙ>, COMPUTE --a finite subset H⊂Γ(I) of the Gröbner basis Γ(I) of I w.r.t. s.t., for each gᵢ∈ G its normal form NF(gᵢ,H) w.r.t. H is zero, "by means of a finite number of queries to an oracle", which, given a term τ∈ T returns its canonical form (τ, I,) w.r.t. the ideal I and the term-ordering. This queer problem has been suggested to us by Bulygin (2005) where a similar problem, but with stronger assumptions, is faced in order to set up a chosen-cyphertext attack against the cryptographic system proposed in Rai (2004).