# Is this problem based on discrete polynomials modulo $(x^3-1)$ strong?

We start working with the Ring $$R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right)$$, $$p$$ prime, i.e. degree two polynomials with coefficients modulo $$p$$ modulo $$x^{3}-1$$. As $$x^{3}-1=\left(x-1\right)\left(x^{2}+x+1\right)$$, we choose a subset of $$R$$, $$S\subset R$$, and a public value, $$z\in\mathbb{Z}/p\mathbb{Z},\ z\neq0$$, $$P\in S,\ P\equiv-z\left(mod\ x-1\right)$$.

We can define the transpose operation of elements of $$S$$ as swaping the $$x$$ coefficient with the $$x^{2}$$one of the corresponding polynomial, so $$\left(ax^{2}+bx+c\right)^{T}=bx^{2}+ax+c$$.

Now, we define a function $$f:S\times S\mapsto S$$, as $$f\left(A,B\right)=\left(xA^{T}+z\right)\left(xB^{T}+z\right)-zx$$. It's null element is $$-zx$$ and $$f$$ is a closed map of $$S$$, so $$A,B\in S,\ f\left(A,B\right)\in S$$.

Next, we define a series as follows:

$$A,B\in S,\ s_{0}=A,\ s_{1}=B,\ s_{n}=f\left(s_{n-2},s_{n-1}\right)$$

And for a given element of the series,$$s_{n}$$, a value $$r_{n}=f\left(s_{n},A\right)$$

## The question is

Taking into account that the function $$f$$ is not associative, how difficult is, knowing $$B$$ and $$r_{n}$$, recover the value of a secret $$A$$. As an example of sizes let's say $$n=256,\ p\sim2^{128}$$.

This problem can lead to a cryptosystem described in this two documents:

• I don't understand the downvote, take a look at the problem at least. – daniel Nov 18 '19 at 17:19
• It might be helpful to list some basic approaches/attempts towards solving the problem, what you've tried so far, etc. The question currently reads like a "Here is a novel algorithm, cryptanalyze it for me" type of question, which are not on-topic or well received here. There are ways to make questions about novel algorithms and cryptanalysis on-topic, it involves breaking the question into smaller pieces and asking concisely answerable questions. – Ella Rose Nov 18 '19 at 17:41
• @daniel Could you please think of a better title? You also don't really ask a question. You state a problem, but that's not the same. Such errors do not harm the semantics of the question all that much, but they certainly harm the clarity of it. – Maarten Bodewes Nov 18 '19 at 18:36
• Hmmmm, is $z=0$ forbidden because of a specific weakness? It is easy to show an efficient isomorphism between this "group" (ok, it's not a group, I can't think of a better term) with one specific $z$ value and another; hence if $z=0$ is a weak case, then any $z$ value is weak. – poncho Nov 18 '19 at 20:38
• Thanks for the upvote. Answering @poncho, with $z=0$ the function becomes $f(A,B)=xA^T B^T$, after stepping the function you don't finish with an intractable formula but just with a simple equation like: $A^{e_1}(A^T)^{e_2}=C$, where $C$ is a constant known. This is easy to solve. So you can answer the isomorphism and I will admit the function is weak. – daniel Nov 19 '19 at 10:18

Here's the isomorphism:

$$ax^2 + bx + c$$ (with $$z$$) maps to $$ax^2 + (b + z - z')x + c$$ (with $$z'$$)

The only nonobvious thing about this transform is that it preserves $$f$$, that is, that $$f(A, B)$$ (with $$z$$) is the element that maps to $$f'(A', B')$$ (with $$z'$$, and $$f', A', B'$$ are the mapped versions of $$f, A, B$$)

However, this is not hard to show; we notice that the constraints $$ax^2 + bx + c = -z \pmod {x-1}$$ is equivalent to $$a + b + c = -z$$.

With this in mind, if $$A = ax^2 - (a+b+z)x + b$$ (setting the linear term to the value it must be for it to be consistent with the constraint), and if $$B = cx^2 - (c+d+z)x + d$$, then $$f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd)$$

If we consider the mapped version of those two elements $$A' = ax^2 - (a+b+z')x + b$$ and $$B' = cx^2 - (c+d+z')x + d$$, then the mapped version of $$f'$$ would have $$f'(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z')x + (2ad+2bc+ac+bd)$$

We can see that the element $$f(A, B)$$ maps to the element $$f'(A', B')$$, hence the isomorphism is preserved.

• This is the way, a mapping to a solvable function. I don't understand though what you do with the $-zx$ in the function. It seems to me that the isomorphism is for $f(A,B)=(xA^T+z)(xB^T+z)$, the function I propose is $f(A,B)=(xA^T+z)(xB^T+z)-zx$. – daniel Nov 19 '19 at 17:25
• @daniel: actually, it was in there, but it was a bit subtle. I've revised my proof; take a look at it... – poncho Nov 20 '19 at 4:30
• Question answered. Thank you. – daniel Nov 20 '19 at 11:36