2
$\begingroup$

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:

https://drive.google.com/open?id=1OGnFfooWASVCD1Iw_hVwvHYgqMGGE5nH

https://drive.google.com/open?id=1OeKh_ZJF-i7_KzWFRv8jodk3YkXe2qyv

$\endgroup$
  • 1
    $\begingroup$ I don't understand the downvote, take a look at the problem at least. $\endgroup$ – daniel Nov 18 '19 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 Nov 18 '19 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 Nov 18 '19 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 Nov 18 '19 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 Nov 19 '19 at 10:18
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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 Nov 19 '19 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 Nov 20 '19 at 4:30
  • $\begingroup$ Question answered. Thank you. $\endgroup$ – daniel Nov 20 '19 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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