Score:0

Quantum secure algorithms

ro flag

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).

Score:1
my flag

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.

Shima avatar
ro flag
even that p and g are secret sand unknown to the adversary?
poncho avatar
my flag
@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...)
Shima avatar
ro flag
how is can be modified to post-quantum secure algorithm, any clue!
poncho avatar
my flag
@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...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.