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:



  • 1
    $\begingroup$ I don't understand the downvote, take a look at the problem at least. $\endgroup$
    – daniel
    Commented Nov 18, 2019 at 17:19
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ella Rose
    Commented Nov 18, 2019 at 17:41
  • 2
    $\begingroup$ @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. $\endgroup$
    – Maarten Bodewes
    Commented Nov 18, 2019 at 18:36
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Commented Nov 18, 2019 at 20:38
  • $\begingroup$ 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. $\endgroup$
    – daniel
    Commented Nov 19, 2019 at 10:18

1 Answer 1


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.

  • $\begingroup$ 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$. $\endgroup$
    – daniel
    Commented Nov 19, 2019 at 17:25
  • $\begingroup$ @daniel: actually, it was in there, but it was a bit subtle. I've revised my proof; take a look at it... $\endgroup$
    – poncho
    Commented Nov 20, 2019 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.