# What is it known about the hardness of the factorization search problem in non-commutative crypto?

The factorization search is an interesting problem in non-commutative crypto that can be defined as:

Given an element $$c$$ of a group $$G$$, two subgroups $$A,B \leqslant G$$. Find two elements $$a\in A$$ and $$b \in B$$ such that $$c=ab$$.

In the case of $$A=B$$ we can see that any element $$a'\in A$$ will give us $$b' \in B$$, since $$b'= a'^{-1}c$$, because the resulting element is in the same subgroup.

If $$A$$ and $$B$$ commute element-wise then pick $$b'\in B$$ and compute the commutator $$[c,b'] = [ab, b'] = b^{-1}a^{-1}b'^{-1}abb'$$. Since $$[a^{-1}, b'^{-1}] = 1$$ then $$[ab,b'] = (b'^{-1})^b b'$$. Finally multiply by the inverse of $$b'$$ to obtain $$(b'^{-1})^b$$. This is a reduction to the conjugacy search problem (CSP).

Q: What is the situation about the factorization search problem?

Q: What reductions exist to known problems on Group Theory, if any?

Q: Is there any protocol based on this problem?

Q: What reductions exist to known problems on Group Theory, if any?

I would consider the factorization search problem to be a known problem in group theory. After all, the LU-decomposition and QR-decompositions of matrices are special cases of the factorization search problem. In group based cryptography, the decomposition problem is usually stated in the following equivalent but seemingly more general form:

Suppose that $$G$$ is a group and $$A,B$$ are subgroups of $$G$$. Suppose that $$x,y\in G$$. Then find $$a\in A,b\in B$$ where $$axb=y$$.

Q: Is there any protocol based on this problem?

The Ko-Lee et al key exchange, one of the first two non-commutative group based public key cryptosystems, is the cryptosystem which is most closely related to the factorization search problem.

$$\textbf{Ko-Lee key exchange classical formulation:}$$ Suppose that $$G$$ is a group $$c\in G$$, and $$A_{L},B_{L},A_{R},B_{R}$$ are subgroups of $$G$$ such that $$ab=ba$$ whenever $$a\in A_{L},b\in B_{L}$$ or $$a\in A_{R},b\in B_{R}$$.

1. Alice selects $$a_{L}\in A_{L},a_{R}\in A_{R}$$ and sends $$r=a_{L}ca_{R}$$ to Bob.

2. Bob selects $$b_{L}\in B_{L},b_{R}\in B_{R}$$ and sends $$s=b_{L}cb_{R}$$ to Alice.

The common key is $$K=a_{L}b_{L}ca_{R}b_{R}.$$

1. Alice computes $$K_{A}=a_{L}sa_{R}$$.

2. Bob computes $$K_{B}=b_{L}rb_{R}$$.

Note: Sometimes, in the Ko-Lee key exchange, one sets $$A_{L}=A_{R},B_{L}=B_{R}$$ and $$a_{L}=a_{R}^{-1},b_{L}=b_{R}^{-1}$$ so that the Ko-Lee key exchange is based upon the conjugator search problem.

$$\textbf{Ko-Lee key exchange alternate formulation:}$$ Suppose $$G$$ is a group and $$A'_{L},B'_{L},A'_{R},B'_{R}$$ are subgroups of $$G$$ such that $$ab=ba$$ whenever $$a\in A'_{L},b\in B'_{L}$$.

1. Alice selects $$a'_{L}\in A'_{L},a'_{R}\in A'_{R}$$ and sends $$r'=a'_{L}a'_{R}$$ to Bob.

2. Bob selects $$b_{L}'\in B'_{L},b'_{R}\in B'_{R}$$ and sends $$s'=b'_{L}b'_{R}$$ to Alice.

The common key is $$K'=a'_{L}b'_{L}a'_{R}b'_{R}.$$

1. Alice computes $$K'_{A}=a'_{L}s'a'_{R}$$.

2. Bob computes $$K_{B}'=b_{L}'r'b'_{R}$$.

The alternate formulation of the Ko-Lee key exchange is a special case of the classical formulation of the Ko-Lee key exchange. To formulate the classical formulation of the Ko-Lee key exchange in terms of the alternate formulation of the Ko-Lee key exchange, one sets $$A_{L}'=A_{L},B_{L}'=B_{L}$$, $$A_{R}'=cA_{R}c^{-1},B_{R}'=cB_{R}c^{-1}$$ and $$a_{L}'=a_{L},b_{L}'=b_{L}$$ and $$a_{R}'=ca_{R}c^{-1},b_{R}'=cb_{R}c^{-1}$$ and $$K'=Kc^{-1}$$.

Q: What is the situation about the factorization search problem?

The decomposition problem on the braid groups has been attacked for example using length based attacks. Such an attack can be found in this paper. In general, one could more or less use length based attacks to attack any cryptosystem based upon the factorization problem in non-commutative cryptography. For example, length based attacks have successfully broken the Ko-Lee key exchange with Thompson's group as the platform (see this paper).

• Seems like Koo-Lee is similar to the Centralizer problem, so $g,a,b \in G$ and $A=C_G(a)$ and $B=C_G(b)$. Decomposition problem can be reduced to a subgroup-restricted conjugacy search problem where I can set an attack. Thanks for your insight. Oct 26 '18 at 8:05
• @kub0x I am unsure of what you mean by the centralizer problem. But I do know that this paper eprint.iacr.org/2005/447.pdf refines the Ko-Lee key exchange so that $A=C_{G}(a),B=C_{G}(b)$ as you have mentioned. I do not know how well these refinements actually improve the security of the Ko-Lee key exchange for braid groups though (and even in this refined key exchange, one would need to use a platform group where it is easy to find elements in centralizers). Oct 26 '18 at 22:37
• That's it, the protocol defined by Vladimir Shpilrain and Alexander Ushakov, is sometimes called the twisted protocol or centralizer key exchange in some literature. You are right, one must find easy to select elements in centralizers, since now you use two subgroups instead of 4 and these don't commute elementwise. Oct 27 '18 at 8:54