0
$\begingroup$

I want to know if the below algorithm , secure against quantum computing attack, and how I can compute the running time for the original algorithm and the proposed attack

further fixed image

Source: Yan Zhu, HuaiXi Wang, ZeXing Hu, Gail-Joon Ahn & HongXin Hu, Zero-knowledge proofs of retrievability, in Sci. China Inf. Sci. 54, 1608 (2011).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I want to know if the below algorithm , secure against quantum computing attack

No, it's not secure against Quantum Computers. To quote the text: the secret key is $sk = x \in_R \mathbb{Z}_p$ and the public key is $pk = (g, v = g^x)$.

Shor's algorithm will directly recover the secret key from the public key; that runs in polynomial time.

Improve this answer
$\endgroup$
4
  • $\begingroup$ even that p and g are secret sand unknown to the adversary? $\endgroup$
    – Shi Li
    Oct 5, 2021 at 13:56
  • $\begingroup$ @Shima: $g$ is not unknown to the adversary - it's right there in the public key. As for $p$, well, that can be recovered (or at least, a multiple of it) by doing point counting on the curve (and Shor's can also directly recover it, but that'd be more effort...) $\endgroup$
    – poncho
    Oct 5, 2021 at 14:03
  • $\begingroup$ how is can be modified to post-quantum secure algorithm, any clue! $\endgroup$
    – Shi Li
    Oct 5, 2021 at 14:42
  • 2
    $\begingroup$ @Shima: doesn't look likely - it uses a pairing operation - I can't think of a post-quantum pairing operation off the top (don't the idea of a 'pairing operation' imply a group; discrete logs in a group are not postquantum), and revising it not to use a pairing operation isn't a "modification", but closer to a complete redesign... $\endgroup$
    – poncho
    Oct 5, 2021 at 15:15

Your Answer

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

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