# 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. Commented Nov 18, 2019 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. Commented Nov 18, 2019 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. Commented Nov 18, 2019 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. Commented Nov 18, 2019 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. Commented Nov 19, 2019 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$. Commented Nov 19, 2019 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... Commented Nov 20, 2019 at 4:30
The text passage describes a mathematical problem in the field of cryptography, specifically dealing with polynomials in a ring modulo \(x^3-1\) and a prime \(p\). It introduces a function \(f\) and a series based on this function, and then poses a question about the difficulty of recovering a secret value \(A\) given certain parameters.
single_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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. Commented Nov 18, 2019 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. Commented Nov 18, 2019 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. Commented Nov 18, 2019 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. Commented Nov 18, 2019 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. Commented Nov 19, 2019 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$. Commented Nov 19, 2019 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... Commented Nov 20, 2019 at 4:30
user
The text passage describes a mathematical problem in the field of cryptography, specifically dealing with polynomials in a ring modulo \(x^3-1\) and a prime \(p\). It introduces a function \(f\) and a series based on this function, and then poses a question about the difficulty of recovering a secret value \(A\) given certain parameters.

TYPE: SINGLE_QUESTION