0
$\begingroup$

$$g^a = c \bmod{N} \text{ }\rightarrow \text{ }G_{i_1}G_{i_2}G_{i_3}...G_{i_n} = C \bmod N $$

At the Discrete Log problem we try to find the exponent ($a$) of a generator ($g$) over a finite filed. e.g. $$g^a = c \bmod{N}$$ We assume everything except the exponent is known. This also includes the factorization of $N, N-1, \phi(N) \phi(N-1)...$ and period length of $g$. We also know at least one solution for an exponent $a$ with given $c$ exists.

Now we extend this problem to a 2 factor problem: $$g_1^a \cdot g_2^b = c \bmod{N}$$ We choose $g_1,g_2,N$ carefully with being cycle with about the same length. $$\not\exists\text{ } a \text{ with: } g_1^a = g_2 \bmod N$$ This can be solved even easier (under the condition everything but $a,b$ is known). About $\sqrt{\text{security}}$ of the one generator case.

For integer multiplication the order of $g_1,g_2$ is irrelevant but
$\rightarrow$ Q: What happens if we change it to something where the order is relevant? Can we make the dlog problem significant harder?

e.g. a series of matrix multiplication: given 2 well chosen cyclic (with similar length) matrices $G_1$ and $G_2$ with (at least): $$\not\exists\text{ } a \text{ with: } G^a_1 = G_2 \bmod N$$ and a resulting matrix $C$ with $$G_{i_1}G_{i_2}G_{i_3}...G_{i_n} = C \bmod N$$ $$i_j \in [1,2]$$

As far as I know for 128-bit security for the one exponent DL-problem we use $N$ with a bit size of 3072 and $a$ with a bit size of 256.

To convert it to matrix multiplication the 256-bit key could mean $0 \rightarrow$ multiply with $G_1$ and $1 \rightarrow$ multiply with $G_2$. We will end up with a product of 256 matrices.

How difficult would it be to break this? We assume everything but the order in known. If it is less secure than the integer DL-problem are there alternative ways to make it more secure (e.g. increasing the amount of used matrices)?


Of course it hardly depends on the chosen matrices. We assume we picked matrices with most secure structure for a given matrix size. We can make it computable harder by just increasing their size. For size 1x1 we only get the two generator integer security of ~$64$-bit (if I'm not mistaken). What would be the minimal matrix size to reach $128$-bit security again?


As alternativ we could also use non-commutative hypercomplex numbers like Quaternions. I guess they gain less security than matrices. If both won't work out are there other non-commutative alternatives wich can be used to increase security?

$\endgroup$
3
  • $\begingroup$ This is so open ended to be a significant research problem, probably not answerable here. Also "it hardly depends on the chosen matrices"? Surely the opposite, according to your later sentence. $\endgroup$
    – kodlu
    Oct 28, 2023 at 15:45
  • 1
    $\begingroup$ Not sure about quaternions but there is a polynomial reduction in the matrix case (general linear group). Therefore they don't provide any advantage. uwaterloo.ca/scholar/sites/ca.scholar/files/ajmeneze/files/… $\endgroup$
    – honzaik
    Nov 2, 2023 at 11:18
  • $\begingroup$ @honzaik Thanks for the reply. As far as I understood this only covers the case with the power of one matrix like $B = A^l$. $\endgroup$
    – J. Doe
    Nov 2, 2023 at 17:53

1 Answer 1

1
$\begingroup$

I would say that the answer is no without any significant introduction of new techniques. As stated in the comment, the question is too broad.

There was quite a bit of effort expended by community members here on your other questions including mixing up (commutative) operations over some graph structure. Did that help? Do you have any progress in implementation/testing or otherwise you'd like to share in that domain?

Your proposal is in the broad area of using products over some algebra, albeit non-commutative. Given all the intricacies with commutative products, starting with the difficulties with finding a secure knapsack based public key system for example, I think:

  1. Analyzing any such schemes would require new techniques.
  2. Trusting such schemes without extensive analysis, given the inclination towards being conservative in proposing new schemes, is not going to happen.

This answer does not cover existing non-commutative proposals based on multivariate arithmetic, see for example https://en.wikipedia.org/wiki/Multivariate_cryptography. I don't believe any of these are trusted to increase security for symmetric schemes, which I understand is your question.

I am not a deep expert in this area, however I wonder why NTRU did not make it into the final PQC list. Another aspect of this whole standardization effort I find a bit strange is that certain people appear on so many proposals. From a pure outsider point of view, it seems very incestuous.

$\endgroup$
3
  • 1
    $\begingroup$ "I wonder why NTRU did not make it into the final PQC list" - the reason NIST gave was that the key generation process was somewhat more expensive compared to Kyber. $\endgroup$
    – poncho
    Oct 28, 2023 at 18:08
  • $\begingroup$ thanks for the answer! If I find some nice matrices I will do some more specific question. This is related to a possible solution for another problem of the same application. For the structural embedding I will go for $m' = AES(m,k)$, a key modification $k' = f(k,m,m')$ and $m_{next} = AES(m',k')$ with finding a valid $k'$ for the inverse being hard except for one case. Fine tuning need to be done. To avoid meet in the middle only a small number of consecutively steps can be done. So it is easy to progress multiple ways in forward direction but for inverse only one direction is easy to use. $\endgroup$
    – J. Doe
    Oct 28, 2023 at 23:54
  • 1
    $\begingroup$ note that NTRU has some known structural weaknesses with the "subfield attacks" of ~2016-2018. It killed essentially all NTRU-based FHE at the time (there are some proposals now that sort of get around the problematic parameter sets, but some authors are perhaps flirting with disaster more than I would). These subfield attacks are not known to be relevant to purely PKE, but one can say that NTRU has structural flaws that RLWE-based schemes are currently not known to have, e.g. it seems reasonable to me to have a (mild) preference towards RLWE over NTRU as a result $\endgroup$
    – Mark Schultz-Wu
    Oct 29, 2023 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.