0
$\begingroup$

I believe I'm probably not the first person to think of using this as a trapdoor.

Let $R$ be a square matrix ring, and $S$ a commutative subgroup of its multiplicative monoid.

Let $P \in R$ be a publicly-known matrix such that for all $x \in S$, $x$ can be constructed by calculating $x = P \cdot D \cdot P^{-1}$, where $D$ is some diagonal matrix ($D$ isn't necessarily in $S$, and $x$ isn't necessarily a diagonal matrix).

The trapdoor problem being: given $a \in S$ and $u = a \cdot b + b \cdot a$, find $b \in R$

What I don't know about is:

  • How difficult is it to find $b$?

  • What are some of the cases where finding $b$ would be easier than average?

My Guess:

  • Because it's not possible to retrieve $b$ using ordinary matrix operations, some search is required.

  • If $u = 0$, then $b = 0$ would be a trivial answer. If $u \in S$, then $b = (u \cdot a^{-1})/2$ would be another.


A bit of explanation on $S$: its elements are guaranteed to be commutative in multiplication because:

1) diagonal matrices are commutative in multiplication,

2) multiplying an element constructed as $a=P \cdot A \cdot P^{-1}$ with $b = P \cdot B \cdot P^{-1}$ where $A$ and $B$ are diagonal matrices yields $a\cdot b = P \cdot A \cdot P^{-1} \cdot P \cdot B \cdot P^{-1} = P \cdot A \cdot B \cdot P^{-1} = P \cdot B \cdot A \cdot P^{-1} = ... = b \cdot a$

$\endgroup$
  • $\begingroup$ I guess it is restricted to finite ring, as common in crypto. $\endgroup$ – fgrieu Sep 18 '17 at 10:40
  • $\begingroup$ @fgrieu yes, now that you've made it explicit. $\endgroup$ – DannyNiu Sep 18 '17 at 11:47
  • $\begingroup$ First, $S$ is commutative and diagonal matrices are commutative, then $P D P^{-1} = D$, so you defined $S$ as the subgroup of diagonal matrices. Secondly: Why do you think it's hard? What is the trapdoor here? And why is the problem much easier when knowing the trapdoor? In the current state, the question might be better suited for math-SE, there isn't much cryptography so far. $\endgroup$ – tylo Sep 18 '17 at 11:56
  • $\begingroup$ It is not clear to me if $R$ is supposed to be a matrix ring, or just any commutative ring. Over what ring is the matrix $D$? I don't think you're using the term generator in the usual meaning (i.e. $S$ is actually cyclic), so please clarify. $\endgroup$ – Aleph Sep 18 '17 at 18:25
  • 1
    $\begingroup$ If the dimension of $R$ is $n \times n$, isn't the operation $a \cdot b + b \cdot a$ for public $a$ linear in terms of the $n^2$ elements that make up the matrix $b$? Can't you then express $u = a \cdot b + b \cdot a$ as $n^2$ linear equations, and solve it in $O(n^6)$ time? $\endgroup$ – poncho Sep 19 '17 at 10:24
2
$\begingroup$

How difficult is it to find $b$?

If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field the matrices are over; a simple minded Gaussian Elimination would recover $b$ in $O(n^6)$ steps.

If $u$ is specified explicitly in the public key or the ciphertext or the signature, that'll take $O(n^2)$ space; in other words, to get $n$-bit security, you'll need to take $O(2^{n/3})$ space (field elements).

Currently, the lowest level of security we consider is $n=80$ bit (and that's for constrained devices that really can't do any more); even at that level, you'll end up with using multimegabyte public keys/ciphertext/signatures (at the very least, assuming that there's no better attack).

Now, if your cryptosystem has nice properties, for example, is at least partially homomorphic, it might be of some interest. However, if it's just a simple public key encryption or signature system, well, something with a relatively low-exponent polytime solution doesn't look at all promising...

$\endgroup$

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.