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}$.


Alice selects $a_{L}\in A_{L},a_{R}\in A_{R}$ and sends
$r=a_{L}ca_{R}$ to Bob.
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}.$


Alice computes $K_{A}=a_{L}sa_{R}$.
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}$.


Alice selects $a'_{L}\in A'_{L},a'_{R}\in A'_{R}$ and sends
$r'=a'_{L}a'_{R}$ to Bob.
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}.$


Alice computes $K'_{A}=a'_{L}s'a'_{R}$.
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).