# 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. 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. 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. 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. 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. 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$. 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... Nov 20 '19 at 4:30
• Question answered. Thank you. Nov 20 '19 at 11:36