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

1 Answer 1

Reset to default
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$
1
  • $\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, 2020 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.