12

Let's say I want to use a zero-knowledge proof to prove that I am older than 18 to vote, without revealing my age.

But then, let's say I give another one to prove that I can 'drink', and am older than 21. And then, another proof that I'm older than 35 to run for 'United States president'. And then one more that I'm younger than 65 to not get 'retirement benefits'.

If I give enough ZK proofs - do I eventually give knowledge about my exact age?

4
  • Giving any zero knowledge proof gives knowledge, because giving any proof gives knowledge. You know the thing you're proving! Nov 30, 2022 at 23:17
  • I guess I'm just curious as to what point it becomes a security concern, but that sounds like a case-by-case basis. Dec 1, 2022 at 0:08
  • @PatrickCollins In ZKP prover claims to know something and wants to convince verifiers. Thinh is, they may not trust one another. Both follow a protocol (designed for the claim at hand, say, by a neutral instance) which is complete and sound and does not reveal any extra information (see e.g. Wikipedia for definitions). Question: what exactly does prover (you) claim in your example? There are multiple claims. That may be fine but they need to be aggregated to one claim: older than 35 and younger than 65. Dec 4, 2022 at 1:36
  • But even if aggregated claim was : older than 39 and younger than 41 (i.e.: age 40) then it's fine (it is actually the purpose of prover) to reveal that true knowledge of his/her or to be caught as lier. However, nothing more than that knowledge should be revealed to verifier and even independent observer of the protocol. Dec 4, 2022 at 1:48

7 Answers 7

6

Generally, privacy preservation is about hiding in a large set of possibilities, so anything that narrows the set of possibilities too much is a hazard.

When multiple observations are possible, an adversary may be able to deduce more than is directly divulged.

Each proof is a clue, so with enough of them, someone might put together "Colonel Mustard in the Library with the Candle Stick" without needing it explicitly revealed.

2
  • But does it make sense to keep calling them "zero knowledge proofs" then? It feels misleading. Is there a way to calculate how much knowledge is being given away? Nov 30, 2022 at 12:48
  • Have a look at Ander's answer. Dec 1, 2022 at 3:29
8

A proper zero-knowledge proof gives no information whatsoever EXCEPT about the statement it's proving. So, for example, no number of ideal digital signatures will ever serve to leak even a single bit of information about the private key.

... HOWEVER, the laws of regular logic still apply. The statement you are proving obviously DOES get revealed with the proof. That's the whole point. Any guarantees that a zero-knowledge proof system can provide, obviously do not apply to information you are intentionally disclosing.

So yes, if you tell someone that you're over 21, and also that you're under 65, they know what range your age is in. No amount of mathematical cleverness can save you from the consequences of people knowing information you intentionally told them. Sorry. 😔

... but there are still clever things you can do, they're just dependent on your exact application, and harder to generalize.

For example, if you only need ONE of the people in a group to be over 65 for their reservation to be at the senior rate, you could prove just that statement, and not give away anything definitive about any individual's age. Relatedly, there's a construction called a "ring signature", where you can show that one of a set of keys made a signature, but not which member of the set.

Or -- and this is getting out of my depth, so I don't know what is actually possible here -- if you give someone a non-transferable proof that you are over 21, they can let you into a bar, but will not be able to convince a third party of your age with it, which means it can't readily be combined with the non-transferable proof you gave someone else that you're under 65.

1
  • Exactly this. You give away one bit of information with a "ZK" proof: that the statement is correct. If you now add more statements in, you have more information, and eventually, after (e.g.) proving age >= 21 and age < 22 you will end up with age = 21. Dec 1, 2022 at 17:57
6

Yes, if you give enough ZK proofs, you do eventually give knowledge about your exact age. An analogy would be if you were assembling pieces of a puzzle. If you assemble enough of the pieces, you will eventually produce a complete picture, that is, your exact age. Philosophically speaking, when things get to their extreme, they turn into their opposite.

1
  • Is this something we have literature on then? Can we calculate how much knowledge we give when we give zkproofs? It feels like calling them "zero knowledge" is a bit misleading... Nov 30, 2022 at 12:47
4

A "zero knowledge proof" is a proof that gives zero knowledge of anything other than what it's proving. If you're proving that you're over 18, then a ZKP will prove that you're over 18, but not provide any other information. In comments, you've said that the term "zero knowledge proof" is misleading, but of course a proof will provide knowledge about the thing it's proving, so the only possible meaning is that it provides zero knowledge about anything else.

The more things you prove about your age, the more information you give about your age. That's the nature of information. That's not a fact about ZKP, that's just a fact about logic. ZKP still means you don't give knowledge about anything other than your age.

ZKP are generally about meta knowledge. For instance, you wouldn't be proving that your age is over 18, you'd be proving that you know whether it's over 18, without proving that it is or not. In ZKP, you prove that you know a piece of information, without giving any knowledge about that piece of information itself. For instance, you might prove that you know a password, without revealing what that password is. If you perform multiple ZKP, you'd be proving the same each time: that you know that password. In you example, however, you're giving ZKP about different things: whether your age is over 35, whether it's over 65, etc. It is because you are proving different things that you are giving more and more information, not because you are giving multiple ZKP. If you perform multiple ZKP about the same thing, then you don't give any more information than if you had performed one.

1
3

I know this is not a math/signal processing forum, but your question kind of is.

The problem is that "Zero knowledge" is a name of the protocol, often called a proof, but not a proof in the mathematical sense. In essence, saying you are older than 18 is not "zero knowledge", its 1 knowledge, it is information. So, mathematically speaking, you are indeed providing knowledge.

Basically, don't mistake protocol names with description of what they do.

3
  • Yeah... feels like maybe the name is misleading... Nov 30, 2022 at 12:49
  • 4
    @PatrickCollins it's not really, because there is zero public knowledge that lead to the proof. But the proof is information, the outcome of what you wanted to proof is information about you. I could reasonably so use a Zero Knowledge proof to proof that my name is Ander Biguri. While the knowledge used to proof that may be not visible to you, the outcome is information, my name. Nov 30, 2022 at 13:58
  • about math: I once heard (but I do not have a paper only claim) that for any mathematical theorem with a proof there is also a zero knowledge proof protocol. So I could have claimed (before pythagoras) theorem of pythagoras and a protocol would exist to convince others or to catch me as liar (i.e. pythagoras wrong, which is not the case). I imagine such protocol to check examples until counter example found by probability evidence if not by flaw. But even for unsolved conjectures (say collatz) a proof cliam would have a (I guess very complex) zero kowledge proof protocol. Dec 4, 2022 at 2:04
0

Its depend on creativity of protocol that want to use zkp, and also what we want to proof??

for example i want to proof that i am older than 18 but without showing any personal documentation(your example): in this case i can poit to clue like:

ok imagine now is 2023 So at least I must have been born in 2005

i can mentioned some thing about a cartoon or tv an show which shows in tv during 2007-2008 (for my generation) , it shows that at least in those years i was a child that i watched and i can remember somethings about it.

but that's not enough to proof i am older than 18, i need more clues to proof, so lets keep to give you more clues:

i can answer some another generally questions or some questions about topic, for exmaple i want to vote about what?

if i tell you something about George Bush during his presidency?

if i tell you something about a footbal match in world cup 2006 or 2010 or have conversation with you about it?

if i had a transaction hash on my wallet at 2015?? (or i sent transaction with a wallet that has transaction in 2015, this way i proved thats my wallet)

i think all of these can proof i am older than 18, if not i think i am not good in examples :)

Also, this example can be extended to other ages

As i said it depends on creativity, you must find best clues that can prove something without get personal infromation or documentation of that shows who i am.

i think best way is any person has different choices that choose one of them

0

Disclaimer: I am not an expert on this topic and only a fellow student of ZK protocols. Most of this answer is based on the article "Sorting out zero-knowledge", mentioned below, and corrections to this answer is very welcome.


I think what are you seeking is systems with the stronger notion of zero-knowledge with auxiliary input¹, which states that

"no matter which additional input is given to the verifier before the interaction with the prover, the interaction does not help the verifier learn anything at all that he could not have learnt by himself given the same additional input".²

(The additional input considering your scenario would be the information in you got in previous proofs)

1: Y. Oren, "On the cunning power of cheating verifiers: Some observations about zero knowledge proofs," 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA, 1987, pp. 462-471.

2: Brassard, Gilles, and Claude Crepeau. "Sorting out zero-knowledge." Advances in Cryptology—EUROCRYPT’89: Workshop on the Theory and Application of Cryptographic Techniques Houthalen, Belgium, April 10–13, 1989 Proceedings 8. Springer Berlin Heidelberg, 1990.


Regarding your comment "But does it make sense to keep calling them "zero knowledge proofs" then? It feels misleading."

This question was also raised by Feige, Fiat and Shamir in their paper "Zero-knowledge proofs of identity". There, they call what you refer as ZK proof as a ZK proof of assertion, and they propose a definition of ZK where the prover prove that he knows the status of an information I with respect to a language L instead of proving that I belongs to L. In their own words:

As a motivating (but technically inaccurate) example, consider a prover A who wants to prove to a skeptical B that he has settled Fermat's last theorem. With the type of proof introduced in this paper, A can convince B that he is a mathematical superstar without telling B anything new about the problem--not even whether he has found a proof or a counterexampte!

On the same vein, Galil, Haber and Yung also suggested that ZK proofs should be termed instead as proofs of minimum knowledge, meaning that they only reveal what is necessary for them to fulfill their intended purpose.

1
  • @Patrick Collins cheers from a fan of your videos!
    – shamisen
    Jan 22, 2023 at 12:19

Your Answer

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

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