I can't be the first one to think of this and there must be a reason nobody design cryptosystem off this problem.

Let's define MECC as matrix of elliptic curve points, and MI as matrix of non-negative integers.

Given a MECC $G$, MI $v$, and MECC $P=v\cdot G$. How would a quantum computer calculate $v$ from $P$ and $G$?

  • $\begingroup$ How is $\cdot$ defined in the question? As element-wise multiplication or as a matrix-matrix product? $\endgroup$
    – SEJPM
    Commented Sep 28, 2020 at 14:49
  • $\begingroup$ matrix-matrix product obviously. $\endgroup$
    – DannyNiu
    Commented Sep 28, 2020 at 14:50

1 Answer 1


Reasoned it through just now. Given the ultimate generator of the elliptic curve group $G'$

  1. Shor $G$ element-wise to obtain an MI $H$ such that $G=H * (G')$, where $*$ is element-wise multiplication.

  2. Shor $P$ element-wise against $(G')$ to obtain an MI $J$

  3. Calculate $J\over H$ using Gaussian elimination to obtain $v$

Yeah! I defeated myself in a cryptanalysis challenge.

  • $\begingroup$ Was about to say that in a comment. You could consider accepting your own answer then, can be useful if anyone wonders something similar in the future :) $\endgroup$ Commented Sep 28, 2020 at 16:15

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.