Is this problem with anti-circulant matrices hard?

If there is an obvious way to solve this problem, please give it a chance before downvoting, I beg you. Also, some insight into the resultant asymmetric cryptosystem will be welcomed (described in the link at the end of this question).

We will work with 4x4 anti-circulant matrices of the form:

$$\left (\begin{matrix} a_0 & a_1 & a_2 & a_3 \\ a_1 & a_2 & a_3 & a_0 \\ a_2 & a_3 & a_0 & a_1 \\ a_3 & a_0 & a_1 & a_2 \end{matrix}\right )$$

With $$a_i \in \mathbb{Z}_p$$ and with $$p$$ a large enough prime, say 32-bit. Let's call the invertible subset of such matrices $$S$$.

Since the product of two anti-circulant matrices is a circulant matrix, we define a matrix that turns a circulant matrix into its anti-circulant equivalent.

$$M=\left (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ \end{matrix}\right )$$

Next, we define a function $$f$$, which is the product of two matrices turning the result in its anti-circulant equivalent:

$$f(A,B)=M A B$$

As an anticirculant matrix is defined by its first column, we can alternatively write $$f$$ just as a function of vectors:

$$f\left( \left(\begin{matrix} a_0\\a_1\\a_2\\a_3\end{matrix}\right), \left(\begin{matrix} b_0\\b_1\\b_2\\b_3\end{matrix}\right) \right)= \left(\begin{matrix} a_0 b_0+a_1 b_1+a_2 b_2+a_3 b_3\\ a_0 b_1+a_1 b_2+a_2 b_3+a_3 b_0\\ a_0 b_2+a_1 b_3+a_2 b_0+a_3 b_1\\ a_0 b_3+a_1 b_0+a_2 b_1+a_3 b_2\\ \end{matrix}\right)$$

This function is not associative and not commutative.

Next let's define a series using the function just defined:

$$k_1,k_2 \in S, s_0=k_1, s_1=k_2, s_i=f(s_{i-2},s_{i-1})$$

next we define two result elements for a given $$i$$:

$$r_1=f(s_{i-1},k_1)$$, $$r_2=f(s_i,k_2)$$

Then, for a large enough $$i$$, the hard problem is:

find the value of $$k_1$$ and $$k_2$$ knowing $$r_1$$ and $$r_2$$.

If the problem is really hard, it can lead to the cryptosystem described here.

It is also described more simply here.

• I didn't get that the product of two 4x4 anti-circulant matrices is circulant [update: PLBCAK; also, the suggestion I made is now incorporated in the question] – fgrieu Feb 9 at 15:33
• @fgrieu it is. Perhaps it needs a proof. Actually the procedure is, for the first position of the result vector, $r_0$, just do the sum of the products of each $a_i b_i$. For the second position rotate vector b to the left and do the same, and so on, rotating at each step, until you fill all the values or $r$. I don't know how to write this formally. I appreciate your interest, btw. You break some early attempts on this if I recall correctly. I don't want to abuse the site though. – daniel Feb 9 at 16:45
• I strongly suggest you do not use the notation $tr(AB)$ for your function, as $tr(A)$ often denotes the trace of a matrix. – Mark Feb 9 at 18:04
• With respect to linear/differential cryptanalysis, basing all in one function makes these kind of attacks feasible. But as speed is not critical in an asymmetric primitive, you can add as many rounds as you want, 256 or more. So probabilities fade away below the security threshold of, say $2^{-256}$. Thank you for your attention. – daniel Feb 10 at 10:50
• As a minor tangent, your vector version of $f$ is closely related to discrete convolution. In particular, $g(\bar u, \bar v) = f(\bar u, M \bar v)$ is both commutative and associative, being essentially the circular discrete convolution of $\bar u$ and $\bar v$. – Ilmari Karonen Feb 13 at 14:33

$$f$$ is defined using matrix multiplication, which is associative, as $$f(A,B)=MAB$$. Matrix $$M$$ is anti-circulant, with $$MM$$ the identity.

For all anti-circulant 4×4 matrices $$A$$, $$B$$, $$C$$, it holds $$ABC=CBA$$, and that's an anti-circulant matrix. This explains $$f(f(A,B),f(C,D))=MMABMCD=MMACMBD=f(f(A,C),f(B,D))$$.

Now, the question's $$s_i$$ becomes $$\begin{array}{lll} s_0&&&=k_1\\ s_1&&&=k_2\\ s_2&=f(s_0,s_1)&&=M k_1k_2\\ s_3&=f(s_1,s_2)&=M k_2M k_1k_2&=M k_1{k_2}^2M\\ s_4&=f(s_2,s_3)&=M M k_1k_2M k_1{k_2}^2M&=M {k_1}^2{k_2}^3M\\ s_5&=f(s_3,s_4)&=M M k_1{k_2}^2M M {k_1}^2{k_2}^3M&={k_1}^3{k_2}^5M\\ s_6&=f(s_4,s_5)&=M M {k_1}^2{k_2}^3M {k_1}^3{k_2}^5M&={k_1}^5{k_2}^8\\ s_7&=f(s_5,s_6)&=M {k_1}^3{k_2}^5M {k_1}^5{k_2}^8&={k_1}^8{k_2}^{13}\\ \ldots&&&\ldots \end{array}$$ and if we define the Fibonacci series $$u_{-1}=1$$, $$u_0=0$$, $$u_{i+1}=u_{i-1}+u_i$$ it comes $$s_i=\begin{cases} \quad{k_1}^{u_{i-1}}{k_2}^{u_i}\quad&\text{if }i\bmod6=0\text{ or }i\bmod6=1\\ M{k_1}^{u_{i-1}}{k_2}^{u_i}\quad&\text{if }i\bmod6=2\\ M{k_1}^{u_{i-1}}{k_2}^{u_i}M&\text{if }i\bmod6=3\text{ or }i\bmod6=4\\ \quad{k_1}^{u_{i-1}}{k_2}^{u_i}M&\text{if }i\bmod6=5\\ \end{cases}$$

For $$i\bmod 6=1$$, it comes $${k_1}^{u_{i-2}+1}{k_2}^{u_{i-1}}=Mr_1$$ and $${k_1}^{u_{i-1}}{k_2}^{u_i+1}=Mr_2$$, with all the exponents known and even. We have reduced the problem to finding circulant matrices $$x={k_1}^2$$ and $${y=k_2}^2$$ given circulant matrices $$Mr_1=x^ay^b$$ and $$Mr_2=x^by^c$$ for known integers $$a=\frac{u_{i-2}+1}2$$, $$b=\frac{u_{i-1}}2$$, $$c=\frac{u_i+1}2$$.

This is a system of two equations in the finite commutative group of circulant 4×4 matrices with components in $$\mathbb Z_p$$ and non-zero discriminant. It's easily solved.

For some values of $$i\bmod 6$$ things are somewhat more complicated, but I think the conclusion remains unchanged.

No, this problem is not hard. Here is algebraic reformulation which leads to efficient key recovery.

Ring representation

Let $$R = \mathbb{F}_p[X]/(X^4-1)$$. We identify any $$a \in S$$ with an element of $$R$$ as follows: $$R(a) = a_0 + a_1X+a_2X^2+a_3X^3.$$ From now on assume that we work with elements of $$R$$. Let $$rev$$ denote the polynomial reciprocal function: $$rev(R(a)) = a_3 + a_2X+a_1X^2+a_0X^3.$$ Then, it is easy to verify that for any $$a,b \in R$$ $$rev(a\cdot b) = X\cdot rev(a) \cdot rev(b)$$ and that $$f(a,b) = rev(a\cdot rev(b)) = X \cdot rev(a) \cdot b.$$ Using the simple fact that $$rev(X^i a)=X^{-i}rev(a)$$, we can reduce the result of any sequence of operations of $$f$$ to the form $$s_i(k_1,k_2) = X^j \cdot k_1^x\cdot rev(k_1)^y\cdot k_2^z\cdot rev(k_2)^w,$$ where $$i,j,x,y,z,w$$ are known integers (depending on the number of iterations $$i$$).

Note that we are given two such values $$s_i, s_{i+1}$$.

This settles simple (up to $$rev$$) algebraic formulation of the problem. Clearly, without $$rev$$ we would be given a pair $$(k_1^xk_2^y, k_1^zk_2^w)$$ and it would be easy to recover $$k_1,k_2$$, excluding corner cases when the matrix $$\pmatrix{x & y \\ z & w}$$ is not invertible modulo $$p-1$$, in which case we'll have to deal with factorization of $$p-1$$.

Recovering linear components

Observe that $$X^4-1 = (X-1)(X+1)(X^2+1)$$. We will consider $$s_i \in R$$ modulo each of the linear factors and two cases for the last factor depending on whether it splits or not.

Case of $$X-1$$

Reduction modulo $$(X-1)$$ is equivalent to computing the trace of the vector: $$tr(a) = a_0+a_1+a_2+a_3$$. It is easy to see (e.g. by plugging $$X=1$$ in the polynomial form of $$a,b$$) that $$tr(f(a,b)) = tr(a)\cdot tr(b).$$ As a result, $$tr(s_i) = tr(k_1)^{F_{i-1}}tr(k_2)^{F_i},$$ where $$F_{-1},F_0,F_1,F_2,\ldots = 1,0,1,1,2,\ldots$$ are the Fibonacci numbers.

Given $$s_i, s_{i+1}$$, we can "undo" the iterations via divisions like $$tr(s_{i-1})=tr(s_{i+1})/tr(s_i)$$ and recover $$tr(k_1), tr(k_2).$$ This amounts to inverting the matrix described above $$\pmatrix{x' & y' \\ z' & w'} = \pmatrix{x & y \\ z & w}^{-1}$$ and computing $$tr(k_1) = tr(s_i)^{x'}tr(s_{i+1})^{y'}, tr(k_2) = tr(s_i)^{z'}tr(s_{i+1})^{w'}.$$

Case of $$X+1$$

Similarly, let $$tr'(a) = a_0 - a_1 + a_2 - a_3$$. Then we also have $$tr'(f(a,b)) = tr'(a)\cdot tr'(b).$$

The recovery of $$tr'(k_1), tr'(k_2)$$ is analogous to the case of $$tr$$, except that we have to track the sign, since $$tr'(X) =-1$$.

Case when $$X^2+1$$ splits ($$p=4k+1$$)

If $$p=4k+1$$, then $$X^2+1$$ splits into $$(X-i)(X+i)$$ (thanks @Mark). However, reduction modulo $$(X-i)$$ or $$(X+i)$$ does not behave very well with respect to $$rev$$. Let $$a = a_0 + a_1X + a_2X^2 + a_3X^3$$. Then, $$a \mod (X-i) = (a_0 - a_2) + i(a_1 - a_3),$$ $$rev(a)\cdot i \mod (X-i) = (a_0 - a_2) - i(a_1 - a_3).$$ We see that $$a$$ and $$rev(a)\cdot i$$ are "complex conjugates" of each other (note that $$i$$ is actually not imaginary but lies in $$\mathbb{F}_p$$). The problem with previous approach is that $$a$$ and $$rev(a)$$ are not related by a constant multiplication and so each $$s_i$$ has 4 variables (whereas previously $$k_1$$ and $$rev(k_1)$$ collapsed into one variable). Now, $$a \mod (X+i) = (a_0 - a_2) - i(a_1 - a_3),$$ $$rev(a)\cdot (-i) \mod (X+i) = (a_0 - a_2) + i(a_1 - a_3).$$ Observe that the four expressions $$a \mod (X+i), rev(a) \mod (X+i), a \mod (X-i), rev(a) \mod (X-i)$$ contain only 2 unique variables. Therefore, $$s_i \mod (X-i), s_i \mod (X+i), s_{i+1} \mod (X-i), s_{i+1} \mod (X+i)$$ give four equations on the exponents of four variables (a pair of "conjugates" for each of $$k_1,k_2$$). Therefore, we can invert the respective 4x4 matrix and recover $$k_1,k_2$$ modulo $$(X-i)$$ and $$(X+i)$$.

Now that we have the solution modulo each linear factor, we can reconstruct the keys using the Chinese Remainder Theorem (CRT). This is a complete break for the case $$p=4k+1$$.

See SageMath implementation of the attack.

Case when $$X^2+1$$ does not split ($$p=4k+3$$)

In this case apply the same technique to recover the complex norm of $$k_1,k_2$$ modulo $$X^2+1$$, which is multiplicative.

Further, we reuse the previously noted fact that $$X\cdot rev(a) \mod{X^2+1}$$ is the complex conjugate of $$a \mod {X^2+1}$$. In particular, $$X\cdot rev(a) \cdot a \mod{X^2+1} = norm_{X^2+1}(a)$$ Recall that we have values of the form $$s_i(k_1,k_2) = X^j \cdot k_1^x\cdot rev(k_1)^y\cdot k_2^z\cdot rev(k_2)^w.$$

Working modulo $$X^2+1$$, we can replace $$rev(k_1)$$ by $$norm_{X^2+1}(k_1)/X/k_1$$. Similarly with $$k_2$$. Since the norm is recovered, we end up with equations of the form $$u_1 = k_1^{x'}\cdot k_2^{y'}$$ $$u_2 = k_1^{z'}\cdot k_2^{w'},$$ where $$u_1,u_2,x',z',y',w'$$ are known. This is completely similar to previous attacks, and so we recover $$k_1$$ and $$k_2$$ modulo $$X^2+1$$.

After combining the components using CRT, we recover $$k_1,k_2$$ completely.

The scheme is broken.

UPD: I just realized that I was recovering $$k_1,k_2$$ from $$s_i, s_{i+1}$$ which is trivial to do in any representation by inverting each step. However, for $$r_1=f(s_i,k_1), r_2=f(s_{i+1},k_2)$$ the attack still works by inversion of the relevant exponent matrix $$[[x,y],[z,w]]$$ modulo element order of the multiplicative group of the ring (which is $$p-1$$ for $$p=4k+1$$ and $$p^2-1$$ for $$p=4k+3$$). The only caveat is that in the latter case the matrix is not always invertible modulo each factor of the order. I suppose that the solution is not unique in such cases.

• Similarly, we should have that $\det(f(a, b)) = \det(a)\det(b)$. – Mark Feb 10 at 17:23
• @Mark nice observation. I think $det(M)=-1$. For reference, $det(a)=-a_0^4 + a_1^4 - 4a_0a_1^2a_2 + 2a_0^2a_2^2 - a_2^4 + 4a_0^2a_1a_3 + 4a_1a_2^2a_3 - 2a_1^2a_3^2 - 4a_0a_2a_3^2 + a_3^4$. – Fractalice Feb 10 at 18:21
• If $p\equiv 1\bmod 4$, then there exists an element $i\in\mathbb{F}_p$ such that $i^2+1 \equiv 0\bmod p$. One can then factor $(x^2+1) = (x - i)(x+i)$, and similarly "reduce mod" each component of this to obtain two more linear factors. This is all essentially using the CRT decomposition $\mathbb{F}_p[x]/(x^4-1) \cong \mathbb{F}_p[x]/(x-1)\times\mathbb{F}_p[x]/(x+1)\times\mathbb{F}_p[x]/(x-i)\times\mathbb{F}_p[x]/(x+i)\cong \mathbb{F}_p^4$, and solving in each CRT factor. One can then lift these solutions back up to $\mathbb{F}_p[x]/(x^4-1)$ to get a full break. – Mark Feb 10 at 20:18
• @Mark The problem is $rev$ does not behave well with respect to those reductions. – Fractalice Feb 10 at 20:22
• Answered, there's a typo $rev(a b)=X⋅rev(a)⋅rev(b)$ at the beginning, there's and extra comma. But reducing to a product of polynomials with a reciprocal is enough convincing. Thank you. And I'll come back if nobody minds. – daniel Feb 11 at 11:40