2
$\begingroup$

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$?

Improve this question
$\endgroup$
  • $\begingroup$ How is $\cdot$ defined in the question? As element-wise multiplication or as a matrix-matrix product? $\endgroup$ – SEJPM♦ Sep 28 '20 at 14:49
  • $\begingroup$ matrix-matrix product obviously. $\endgroup$ – DannyNiu Sep 28 '20 at 14:50
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\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$ – Geoffroy Couteau Sep 28 '20 at 16:15

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.