Oracle-supported drawing of the Groebner {\em escalier}

The aim of this note is to discuss the following quite queer Problem: \noindent GIVEN \noindent i) the free non-commutative polynomial ring, ${\Cal P} := {\Bbb F}\langle X_1,\ldots,X_n\rangle$ {\em (public)}, \noindent ii) a bilateral ideal $\mathsf{I}\subset \mathbb{F}⟨X_1,\dots ,X_n⟩$ {\em (private)}, \noindent iii) a finite set $G:=\{g_1,\dots ,g_l\}\subset \mathsf{I}$ of elements of the ideal $\mathsf{I}$ {\em (public)}, \noindent a noetherian semigroup term-ordering $\prec ,$ {\rm (private)}, on the word semigroup ${\Cal T} := < X_1,\ldots,X_n>$,\text{noindent}COMPUTE\text{noindent}--afinitesubset$H\subset\Gamma({\sf I})$oftheGr\ddot{o}bnerbasis$\Gamma({\sf I})$of${\sf I}$w\mathrm{.}r\mathrm{.}t\mathrm{.}$\prec$s\mathrm{.}t\mathrm{.},foreach$g_i\in G$its\text{em}normalform$NF(g_i,H)$w\mathrm{.}r\mathrm{.}t\mathrm{.}$H$ is zero, \noindent “by means of a finite number of queries to an oracle”, which, \noindent given a term $\tau \in \text{Cal}T$ returns its {\em canonical form} $\text{Can}(\tau ,\mathsf{I},\prec )$ w.r.t. the ideal $\mathsf{I}$ and the term-ordering $\prec$. \qed 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).