1
$\begingroup$

I am doing some research on the quaternions and their role in Non-commutative cryptography. I have found a number of articles, but it is still unclear to me if there is a known solution to the Conjugacy Search Problem (CSP) or Conjugacy Decision Problem (CDP) in integer quaternion rings:

CSP: Determine whether there exists a $z$ such that $zy=xz$ for a given $(x, y) \in R$

CDP: Find a $z \in R$ such that $zy=xz$ for a given $(x, y) \in R$

Here $R$ is either the ring of Lipschitz quaternions ($\{ai+bj+ck+d\mid a,b,c,d\in\mathbb{Z}\}$) or the Hurwitz quaternions (which is the union of the Lipschitz quaternions with a second copy of the lattice shifted by $(\frac12, \frac12, \frac12, \frac12)$; i.e., where all coordinates are either integers or integers $+\frac12$).

This paper is a PKC scheme based on the Conjugacy search problem and decision problem

Valluri and Narayan - Quaternion public-key cryptosystems

However, I am inclined to assume that the CSP has not been solved for the quaternions, based on the above. Does an algorithm for solving the CSP for quaternions exist?

Improve this question
$\endgroup$
17
  • 4
    $\begingroup$ I'm going to assume you are discussing the quaternions over $\mathbb{R}$. In this case what you are asking is essentially the conjugacy structure of $\mathrm{SO}(3)$, and it's easiest to see geometrically. Every rotation in three dimensions is a rotation by some angle around an axis, and two rotations by the same angle are conjugate via any rotation that takes one axis to the to other. The structure of the double cover doesn't change much about the conjugacy. $\endgroup$
    – Watson Ladd
    Commented May 10, 2020 at 19:01
  • 1
    $\begingroup$ When you say 'the group' do you mean 'the ring'? Neither the Hurwitz nor Lipschitz quaternions form a field, so you have to be very careful using expressions like $z^{-1}$ in such a case. The question of whether there's a $z$ such that $zy=xz$ is very different from the question of whether there's an invertible such $z$ (which is nearly trivial; very few Hurwitz or Lipschitz quaternions are invertible multiplicatively, after all...) $\endgroup$
    – Steven Stadnicki
    Commented May 11, 2020 at 20:24
  • 1
    $\begingroup$ Presuming that the question here is about conjugacy in these rings, then the problem is likely to be Complicated, by analogy with similar problems in $SL_2(\mathbb{Z})$ for instance. I think there's an interesting question here but you need to be more specific about it. $\endgroup$
    – Steven Stadnicki
    Commented May 11, 2020 at 20:26
  • 1
    $\begingroup$ If I am not mistaken, the question as written now follows by doing the linear algebra approach over $\mathbb{Q}$ and then scaling $z$ to get integer coefficients. $\endgroup$
    – Achim Krause
    Commented May 12, 2020 at 17:40
  • 1
    $\begingroup$ @user157838: Just a side note: you cite some authors, but their English is so bad, that I wouldn't even bother reading their papers. But then, they got published by Hindawi, so... this should tell a lot. $\endgroup$
    – Alex M.
    Commented May 13, 2020 at 9:10

1 Answer 1

Reset to default
4
$\begingroup$

If you are talking about quaternions, then you can rewrite the equation $y = z^{-1}xz$ as $zy - xz = 0$ which is $\mathbb{R}$-linear in $z$. Therefore both problems can be solved quite easily using linear algebra. (I.e. introduce real indeterminates $z_1, \ldots, z_4$ via $z = z_1 + i z_2 + j z_3 + k z_4$, insert into the latter formula and obtain linear system for $z_1, \ldots, z_4.$

If you are talking about quaternion group, then it's even easier as you can just test all eight elements.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What about the Libschitz or Hurwitz groups? $\endgroup$
    – user157838
    Commented May 10, 2020 at 22:16
  • $\begingroup$ I hope that you aren't missing the fact that the OP is working over $\mathbb Z$. $\endgroup$
    – Alex M.
    Commented May 13, 2020 at 9:07
  • 1
    $\begingroup$ @AlexM.: The OP changed the question. It was not originally about the integral case. $\endgroup$
    – Geoff Robinson
    Commented May 13, 2020 at 21:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .