1
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – knaccc
    May 21, 2022 at 18:28
  • $\begingroup$ 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 :) $\endgroup$
    – popeye
    May 21, 2022 at 18:39
  • $\begingroup$ 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$. $\endgroup$
    – knaccc
    May 21, 2022 at 18:50
  • $\begingroup$ 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. $\endgroup$
    – popeye
    May 21, 2022 at 18:59
  • $\begingroup$ 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$. $\endgroup$
    – knaccc
    May 21, 2022 at 19:42

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – popeye
    May 21, 2022 at 18:35
  • $\begingroup$ @GastonMaffei oops, yes thanks I forgot the $c$. I've amended the answer. $\endgroup$
    – knaccc
    May 21, 2022 at 18:38

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.