Join Log in
Score:1
avatar Crypto

Schnorr based ZK scheme

cn flag
Gaston Maffei

TL;DR: This ABSOLUTELY does not work and presents a huge security risk. Posting it anyways in case there are other threats I missed or to dissuade any other person who comes up with this idea.

Hi! I’m sort of new to cryptography. I’m starting to venture into ZK schemes. For a small project of mine with which I intend to put in practice what I learnt so far, I came up with a protocol and I’d love to know if it’s good (i.e. safe, truly non-interactive and ZK, etc). It’s pretty much reusing the Schnorr signature construction and verification protocol.

Setup

  • Players are Alice, Bob and the Crowd.
  • All players agree on using a cryptographically secure cyclic subgroup of a certain elliptic curve, with generator $G$.
  • Bob has a public/private key pair ($b$,$B=bG$).

Objective

Alice has a secret $s$, to which she commits publicly by announcing $S$ (constructed as $S=sG$).

Bob wants to prove to any member of the Crowd that he knows $s$, but without revealing anything about $s$ (ZK). Plus, he wants his proof to be non-interactive and reusable by any skeptic member of the Crowd.

Protocol

  1. Alice publicly announces $S$.
  2. Bob claims to know $s$ and submits a proof $p=s-b$.
  3. The Crowd takes it as a valid proof iff $pG+B=S$.

Rationale

  1. For Bob to be able to construct a valid $p=s-b$ at will, he is required to know $s$. He knows the verification involves removing the $-b$ part, so not knowing $s$ means not being able to end up with $S$ in the end.
  2. Bob does not give away any information on $s$ because it is masked by the addition with $-b$. Since no one else knows $b$, it essentially uniformally randomizes the values.
  3. The Crowd knows that Bob actually knows because generating the proof involves knowing $b$ as well as $s$ for a similar principle to the first point. If someone knew $s$ but not $b$, they could not subtract the correct amount $-b$ which is restored during the verification process and the end result of it would not be $S$.

Questions

  • Is this a valid non-intearctive ZK scheme?
  • Is it a good one if so?
  • Are there any advantages of using zkSNARKs over such a scheme, with the function being proven is, for instance, that the user knows the hash of the word and the hash of the word concatenated with their own public key?

Warning

This absolutely does not work. It’s hugely risky as any prover (Bob in this case) could have their private key leaked: any other player knowing $s$ (Alice in this case, and any other who got a hold of $s$ by whatever means) could just do $b = s - p$. In the Schnorr signature scheme, there’s a factor accompanying $b$. But this factor is publicly known, as it’s used in the verification protocol, and thus fails to protect $b$ in this case. The key takeaway, which I’m glad I can take as a lesson, is that in the Schnorr protocol it’s paramount to keep $k$ safe.

50
0 + 0
knaccc avatar
es flag
knaccc
I assume in the zkSNARKs part of your question, "word" is the secret $s$? If it's a word, then it may not qualify as being high entropy. I'm not sure how it helps to prove not just knowledge of a hash of $s$, but also the hash of $s$ concatenated with Bob's public key $B$. zkSNARKs are much more complicated, and so this part of your question would probably deserve another crypto.stackexchange question if you want to explore it in more detail.
0
Reply
cn flag
Gaston Maffei
Yeah, it’s not a word, it’s a high entropy secret (might be a word but mixed with a sufficiently high entropy nonce). The reason for involving B in the proof is that I want the proof to be unique to Bob, so that no third party Charlie can also claim to know the answer with the same proof. But sure, I’ll give it a bit more thought and give it the proper standalone question it deserves :)
0
Reply
knaccc avatar
es flag
knaccc
If I understand your use case correctly, then just in case it's not obvious: Bob could simply provide any kind of regular signature for the public key $S$ on a message that includes Bob's identity or public key. This would prevent re-use of the signature by another party that wanted to also claim knowledge of $s$.
0
Reply
cn flag
Gaston Maffei
I don’t know that I fully understood the way you say you can avoid proof reuse. However, I’m also trying to minimize the size of the full proof. The idea is to have this on a blockchain so verifying a correct zkSNARK proof is cheaper than zkSNARK proof + signature. I don’t really mind adding complexity to the zkSNARK function being proven.
0
Reply
knaccc avatar
es flag
knaccc
The type of proof you've specified in your original question will bind the proof to Bob's public key. However, for the method mentioned in the comment I just made, the regular signature would not bind the proof to Bob as the author unless you also include Bob's identity as part of the message being signed. Therefore I'm saying you can avoid having to create any kind of custom signature mechanism, and instead just use regular signatures for the public key S and include Bob's identity in the message to prevent the signature from being copy-pasted by someone else as proof they also know $s$.
0
Reply
cn flag
Gaston Maffei
I don’t understand how you propose Bob prove knowledge of $s$ in a binding way to his public key just by signing something involving $S$. I understand that schemes such as Schnorr signatures bind the signature to Bob in this case because the proof and verification protocol use H(m|B). However in this case what exactly is Bob signing to show he knows the secret? Sorry if this is basic and I’m missing it
0
Reply
knaccc avatar
es flag
knaccc
Let's say Bob signs an empty message using knowledge of $s$. Eve can just copy-paste that signature and claim she was the one demonstrating knowledge of $s$. But if Bob signs the message "This is Bob, my public key is 01234...." using the private key $s$, then Eve can't claim it as originating from her. The whole point of a signature is that the message is not malleable.
0
Reply
cn flag
Gaston Maffei
Oh I see. I understand, I just can’t think of a message content to sign that shows knowledge of $s$ without leaking info on it.
0
Reply
knaccc avatar
es flag
knaccc
That's right, you can't put $s$ in the message. Instead, you create a regular signature and sign as if you were a person whose public key was $S$, and that proves knowledge of $s$. But then inside the message, you include your actual identity $B$.
0
Reply
cn flag
Gaston Maffei
Super, now I get it! Use Schnorr signature with S as signer (Bob knows $s$) and B as message (no re-use, binds proof to Bob). That's clean! Thanks
0
Reply
Score:0
knaccc avatar Crypto
es flag
knaccc

Consider an equivalent variant of a regular Schnorr signature that signs a message $m$. I'm assuming $s$ is a sufficiently high-entropy secret, and so that therefore $S$ cannot be brute forced.

The signature would be the pair $(B=bG,\ p=c\cdot s-b)$. It would be verified by checking that $B\overset{?}{=}cS-pG$, where $c = H(B \mathbin\| m)$.

You're removing the challenge $c$, so the first disadvantage is that you are no longer able to sign a message. You can only prove you know $s$.

You therefore have the pair $(B=bG,\ p=s-b)$, and the verification is $pG\overset{?}{=}S-B$.

The challenge was also part of a Fiat-Shamir heuristic that prevented $B$ from being calculated after the challenge $c$ was chosen. Therefore, there is a problem if Bob is able to declare his public key $B$ after $S$ has been announced. Bob could simply pick a random $p$ value, determine $B=S-pG$, and claim his public key is $B$. This could be solved in two ways: 1. Bob is required to declare $B$ prior to $S$ being declared. 2. Bob is required to provide a signature proving knowledge of $b$ such that $B\overset{?}{=}bG$.

Assuming Bob's public key was declared prior to $S$ being declared, you therefore do have a valid way of proving knowledge of $s$. As you've pointed out, Alice could trivially learn Bob's private key $b$. Therefore this does not meet the definition of zero knowledge, which requires "without revealing the information itself or any additional information".

Your construction is therefore similar in definition to an "adaptor signature", because "an adaptor signature scheme can authenticate messages, but simultaneously leaks a secret to certain parties". Your scheme doesn't sign messages, but it does prove knowledge of $s$ while verifiably leaking $b$ to Alice.

Note there may also be issues with your scheme where there is a second secret $s'$, and for some reason $s'-s$ becomes known.

0 + 0
cn flag
Gaston Maffei
That was very thorough, thanks! 1) In paragraph 2, should the signature be (B, p=c.s-b) instead? Anyways, in my scheme I did not include the factor because I’m only interested in proving knowledge and not in signing. 2) Loved the second attack vector with the declaration of B after S. In my case, that would not be a problem because players interact in a way that necessitates them knowing their private keys. But I found it really clever! 3) Thanks for the adaptor signature info, I’ll definitely take a look!
0
Reply
knaccc avatar
es flag
knaccc
@GastonMaffei oops, yes thanks I forgot the $c$. I've amended the answer.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.