1
$\begingroup$

I have two identical pieces of paper. On each piece of paper I write down a number, either 1 or 2. I do not show or tell the numbers to anyone. My writing is always the same - if I write the same number twice then it will look identical both times. I tell you that the sum of the numbers is even. How can I prove it to you beyond reasonable doubt that my statement is true without showing or telling you the actual numbers?

Bonus: Could I still prove it to you if the numbers I wrote down were 1, 2 or 3?

Hint for bonus question:

I can get more pieces of paper and I can write numbers on them that are identical to the original. I can also show you what I wrote down this time.

$\endgroup$
15
  • 2
    $\begingroup$ I have simplified the puzzle. Now the numbers are either 1 or 2. $\endgroup$ Apr 8 at 13:58
  • 2
    $\begingroup$ I think the problem works better with identical coins under identical opaque bottle caps, and the statement that exactly one has heads on top. This avoid the convoluted "writing is always the same", and similar statements about the paper pieces being indistinguishable. I just did that and convinced my wife. $\endgroup$
    – fgrieu
    Apr 8 at 14:35
  • 6
    $\begingroup$ Is this question isomorphic? How can I convince my colour blind friend that his two balls have different colours? You probably disagree because you recently saw it. $\endgroup$
    – noedne
    Apr 8 at 15:18
  • 1
    $\begingroup$ @noedne this question is certainly similar, but not identical. In particular the bonus question makes is quite different. $\endgroup$ Apr 8 at 15:29
  • 1
    $\begingroup$ @noedne : perhaps puzzle wants to steer us in the direction of a general solution. $\endgroup$ Apr 8 at 19:06

10 Answers 10

5
$\begingroup$

Here is a clean solution assuming the following. (I'm not claiming originality; elements of this are already in other answers.)

Dmitry can be trusted in

  • that he wrote 1 or 2 on the two sheets
  • that he is incapable of writing two copies of either 1 or 2 that he himself would be able to distinguish

Apart from that he is a competent liar and cannot be trusted on anything.

Further assumption: There is a way Dmitry can shuffle a given set of sheets without any chance of tampering with them.

Then he can prove without disclosing any information whatsoever that the two original numbers are identical by:

1. Writing openly a 1 and a 2 on two more sheets. Call this the new pair, and the original one original pair.

2. Flipping the two new sheets over and shuffling them before passing then to us so we know they are 1 and 2 but not which is which. (Without this step Dmitry would disclose additional information because if we knew which was which we would be able to infer whether the original pair was two 1s or two 2s later.)

3. Allowing us to repeatedly select one of the four sheets at random (without looking at what is written on it but keeping track of which pair it was from) and let him see the number.

4. Accepting his claim if he manages to guess significantly above chance (50%) level which pair the number comes from.

Note that this does not require us to trust Dmitry. It only requires that Dmitry wants to convince us.

Why this works

If the sum is not even, the original pair will contain 1 and 2, so we have two 1's and two 2's in the four sheets. So if Dmitry lied, he couldn't have got above chance level (50%) to guess which pair the sheet we picked come from. Only when the sum is even will Dmitry be able to guess above chance level, by guessing "original" if the number is the same as the two original number, and guessing "new" if the number is different. This way Dmitry will make a correct guess 75% of the time.

Variation:

Instead of step 3 and 4 above, we could also do:

3' Randomly select a pair (either original or new) and let Dmitry see both numbers, and guess whether it's the original pair or the new pair. Repeat.

4' Accept his claim if he guesses correctly 100% of the time.

Generalisation:

Dmitry claims something, which basically means he is choosing a subset of all possible outcomes. We let him openly produce all other outcomes, which we verify. Then shuffle them and pass them to us in an opaque (think face down) state.

If he now is able to tell with 100% accuracy whether a randomly selected outcome is the original submission or not he must be telling the truth.

$\endgroup$
17
  • $\begingroup$ Vagrerfgvat cebgbpby... Whfg phevbhf: Fhccbfr byq cnve jnf (1,1) naq arj furrg 1 vf nyjnlf cerfragrq. Vs Qzvgel jnagf gb pbaivapr hf, ubj? (nafjre ebg13 cyrnfr). <- rot13 $\endgroup$ Apr 10 at 10:38
  • $\begingroup$ V unir gur fnzr dhrfgvba nf nobir. Vg frrzf gung unys bs gur gvzr V jvyy thrff pbeerpgyl (vs V unir (1,1) naq V nz fubja n 2) naq unys bs gur gvzr V jvyy thrff vapbeerpgyl (vs V unir (1,1) naq V nz fubja n 1). Guvf tvirf zr 50% thrff engr, juvpu vf ABG nobir punapr yriry. $\endgroup$ Apr 10 at 12:29
  • 1
    $\begingroup$ @DmitryKamenetsky I've added a full generalisation. $\endgroup$
    – loopy walt
    Apr 10 at 14:26
  • 1
    $\begingroup$ @FirstNameLastName Seeing Dmitry perform at 100% tells us only one thing: the new outcomes are different to the original one. If we do not know what the new outcomes look like this is pretty much useless. $\endgroup$
    – loopy walt
    Apr 10 at 14:49
  • 1
    $\begingroup$ @FirstNameLastName If we do not check on him he could write 2 and 3 on the new sheets and would be able to tell them apart from the original ones no matter whether they were (0,0) (0,1) or (1,1). The point of the protocol is that if he lied about the original pair and submitted a new pair (0,1) then both pairs are identical and he will have no way of telling them apart, so will be unable to perform at 100%. Conversely, if he does perform at 100% he cannot have lied. Whereas if he just says the sum is even we have no way of telling whether he lied or not. $\endgroup$
    – loopy walt
    Apr 10 at 16:21
3
$\begingroup$

I would like to ask for clasrification but I can't ask in a comment due to reputation. I assume that you can show the actual numbers as long as I can't know what you originally wrote. Otherwise this seems fairly impossible as anything you show me is created independently of the original numbers and so doesn't need to relate to them.

Assuming that here is my solution to the first puzzle.

Clearly you have either written $(1,1)$ or $(2,2)$. Now write on $2$ new pieces of paper the other number. Put these pairs of numbers into $2$ seperate envelopes. Shuffle the envelopes and then give them to me. Now I can open each envelope and see that they contain $(1,1)$ and $(2,2)$. This could only be true if the original numbers sum is even, but additionally I know nothing about the original numbers other than that.

Edit: There is also a simple extension for any property of any collection of numbers.

Simply repeat the same idea but instead write all the possible options that satisfy the property and place these into envelopes. Exactly the same argument shows that this proves you were telling the truth and tells me nothing more. (Although it is propably suboptimal as a solution)

As a note, the reason that this isn't like a zero knowledge proof is that you technically do give me information about what you have written, but only in the sense that you tell me what the options are for things which sum to even values. i.e. it is information which doesn't help me identify what you wrote.

$\endgroup$
8
  • $\begingroup$ player is not allowed to reveal anything to you ... still: you must mathametically prove player knows sum is even $\endgroup$ Apr 9 at 15:58
  • $\begingroup$ Yes thinking about it your method does work without showing anything, however I think my answer is still somewhat worthwhile. Additionally the hint for the bonus question seems to imply that at least there my method is allowed. $\endgroup$
    – Fishbane
    Apr 9 at 16:01
  • 1
    $\begingroup$ nothing must be revealed in bonus version either $\endgroup$ Apr 9 at 16:09
  • $\begingroup$ From the hint. I can also show you what I wrote down this time. Also surely only the question poster can tell us what is allowed. $\endgroup$
    – Fishbane
    Apr 9 at 16:10
  • 2
    $\begingroup$ @Fishbane "I can also show you what I wrote down this time" is for the additional papers, not for the original ones. $\endgroup$
    – justhalf
    Apr 10 at 12:01
3
$\begingroup$

My answer is wrong and here is why.

First, let me refer to ZKP wikipedia https://en.wikipedia.org/wiki/Zero-knowledge_proof (Two balls and the colour-blind friend), and to Computer Science exchange https://cs.stackexchange.com/questions/150548 (How can you convince your colour-blind friend that two balls have the same colour?), and let me thank @MichaelS (and others) who opened my eyes. Dmitry Kamenetsky's nice question boils down to: we know a ZKP for different colors (or odd sum) exists. Does one also exist for same colors (or even sum)? Note that P can look at the numbers and V not. In case of the colors, V can look as well, but it does not help ... V is color-blind. In such ZKP example you (P) claim to know statement S is true and a protocol must be designed which proves me (V), not trusting you, that S indeed is true. There are two aspects I missed: 'claim' and 'trust'. Also, it is neither the case that V must design the protocol to unveil potential lies from P, nor it is the case that P must design the protocol because P wants to convince V about S. Rather: this sort of scenarios often have cryptography as motivation and it's only a matter of designing protocols where parties that should not trust one another can exchange information without giving anything away to everyone. My answer depends on V trusting P but that's exactly what must not be so: P may not be trustworthy and still V needs to be proven S is true. My proof only proves to V that P claims S is true, but, if P can be trusted, V might as well ask about S directly or believe the claim in the first place! The flaw lies in the case when P lied to V about S. That is: S is false. Then my protocol does not work. Because P might as well toss a coin and answer 'swap' for head and 'no swap' for tail. He might do so for S is true as well, that's OK, but for S is false (same colors, or, odd sum) then P leaves V with no proof (S could be true or false). Otherwise stated: my (wrong) protocol is complete but not sound.

Please do not let my comments depending on the flaw confuse you...

(wrong) answer to 'case $1$ $2$' version:

could be $0$ and $1$ too

Let's follow a classical ZKP protocol: you close your eyes and, each time, I either swap the (identical sized, with number hidden) papers or not. Each time, I then allow you to look at one and you must guess and tell me (as perfect thinker who is wanting to prove me something), to your best effort, if I swapped or not. You are not able to conclude correctly if sum is even (both numbers same) so you will eventually give some wrong answers. But if sum is odd you can always conclude correctly and you will give 100% correct answers. So if you do not keep on answering correctly such proves sum is even without extra information being leaked. In fact, any other (passive) spectator does not get anything extra revealed either.

$\endgroup$
21
  • 2
    $\begingroup$ But he could be lying about the difference of their squares. $\endgroup$ Apr 8 at 13:40
  • 7
    $\begingroup$ This is silly. The question asks the guy to “prove” to me that his statement is true. This answer wholly depends on him being 100% honest when answering my questions. If you guys can agree to him doing that then there’s no need to swap any paper just straight up ask him if he lied and he’ll have to tell you the truth. Otherwise if he can still lie then he can lie about the swaps and he hasn’t proven anything at all. $\endgroup$
    – Amorydai
    Apr 8 at 18:08
  • 2
    $\begingroup$ I just realized that there could be a problem with this solution and the whole question in general. The sum could be odd and I just lie during the protocol to get a 50% guess rate. Now if I was asked to prove that the sum is odd (numbers are different) then the classical protocol would work (even if I lied) and I would approach 100% guess rate. So I think the original question is actually flawed and I should have asked for an odd sum. I am considering closing this puzzle, unless you show me otherwise... $\endgroup$ Apr 10 at 12:18
  • 2
    $\begingroup$ Hold on. On more thought, the question asker may not trust the number writer's statement. So while the writer has no incentive to lie, the asker doesn't have to believe that the writer is not lying (unless objectively shown otherwise). As you said yourself, the asker may conclude that the writer guesses wrong in purpose, so it proves nothing to the asker. All these just show that indeed a sandbox would have made this question much much better.. $\endgroup$
    – justhalf
    Apr 11 at 13:14
  • 2
    $\begingroup$ Wait a minute, isn't @justhalf right? If the op stated 'sum is odd' that can absolutely be proven using this technique, but how can they prove 'sum is even'? When you swap, their guess rate is 50%, which doesn't "prove" anything, since if the sum was odd, they could just be randomly giving answers at that same 50% rate to make you think the sum is even... $\endgroup$
    – Amoz
    Apr 11 at 23:40
1
$\begingroup$

By showing me their respective last digits.

$\endgroup$
15
  • 2
    $\begingroup$ This would fail if both numbers are single digits though, as then we see both of the actual numbers $\endgroup$ Apr 8 at 13:32
  • 3
    $\begingroup$ @Randal'Thor yeah, this OP has a habit of changing his questions after receiving valid answers he didn't intend. It really grates. $\endgroup$
    – msh210
    Apr 8 at 14:16
  • 1
    $\begingroup$ Sorry msh210. I realized that the original puzzle was too hard, so I had to update it. $\endgroup$ Apr 8 at 14:20
  • 1
    $\begingroup$ @msh210 fwiw: nothing needs to be shown and still we 'know' if truth was told or not about evenness of sum. Basically: no information is revealed to anyone apart from the fact that something only performer knows is true. $\endgroup$ Apr 8 at 15:03
  • 1
    $\begingroup$ @FirstNameLastName I made a few mistakes in the design of this puzzle. First I didn't realise that proving an even sum would be harder than an odd sum. Then there was the issue of the prover writing the numbers. I think it would be better to have a stack of cards with 1 and 2, and prover selecting a pair of these cards. When I added the bonus question I didn't know the answer, but was hoping someone could find it. I then had the idea that you could possibly solve it with two ZKP protocols. The first proves if numbers are equal or not. If they are not equal then the second protocol $\endgroup$ Apr 11 at 12:37
1
$\begingroup$

You tell me that you wrote the same number on both pieces.

$\endgroup$
8
  • 3
    $\begingroup$ But I could be lying. So that wouldn't prove it. $\endgroup$ Apr 8 at 13:36
  • $\begingroup$ @DmitryKamenetsky You may have also not written anything on the papers. You may also not have any papers at all. You could be lying. Because this is such a trivial proposal ("I wrote two numbers that sum to an even number"), I would be willing to just trust the statement at face value. Without showing the numbers, it is impossible to prove that what you say is true because, as you said, you could be lying about literally everything. $\endgroup$ Apr 8 at 13:38
  • 1
    $\begingroup$ I am not lying about the existence of the numbers. But I could be lying about their sum being even. $\endgroup$ Apr 8 at 13:53
  • $\begingroup$ @DmitryKamenetsky Prove that you're not lying about the existence of the numbers. $\endgroup$ Apr 8 at 14:47
  • 1
    $\begingroup$ The "I could be lying" part is the suspicion of the others, not the writer of the numbers. The others don't trust the writer (so may think that the writer is lying), but the writer wants to prove that they have an even sum, but don't want to show the numbers. In FirstName LastName's answer, we see that the questioner will have to believe that the numbers are indeed even, if the writer can guess correctly 100% of the time. You can lie to not know a secret info, but you can't lie to know the secret info. The puzzle is on how to eliminate the first possibility. $\endgroup$
    – justhalf
    Apr 10 at 7:32
1
$\begingroup$

This problem reduces to "How can I prove to you that I wrote the same number on both pieces?"
If I also assume that you write consistently in form, size, and location, then you can

measure various physical properties of the paper, like weight, moments, and so forth. Since the pieces are stated to be identical, the only way the measurements could differ is if you added different markings to the paper, and multiple identical measurements would be very suggestive (but not definitive proof) of identical numbers.

$\endgroup$
1
$\begingroup$

For the sum to be even, both numbers have to be 1 or both numbers have to be 2. So

Write the numbers in seven segment display, and overlay the paper. By shining a light through the paper, you will observe either:

1 + 1 = 1
1 + 2 or 2 + 1 = backwards 6
2 + 2 = 2

So if the shadow is 1 or 2, the sum is even as the numbers are the same

Bonus:

This also works for 1, 2 and 3, we now also have 1+3 = 3 and 3+3 = 3, and for odds, 2 + 3 = backwards 6

So as long as the shadow is not a backwards 6, the sum is even

$\endgroup$
3
  • $\begingroup$ Very creative answer! Nice. $\endgroup$ Apr 8 at 14:55
  • 1
    $\begingroup$ I’m not sure I understand, if you show the shadow to me I’ll be able to tell what the numbers are, might as well just show me the numbers then. $\endgroup$
    – Amorydai
    Apr 8 at 18:13
  • $\begingroup$ @Amorydai only for the first case, wouldn't necassirly be possible for the bonus. I was also aware of this issue and clarified with Dmitry in the comments under the question whether this was ok, and he said it was. However, yes it may be possible to deduce the numbers, even if you havent been shown them $\endgroup$ Apr 8 at 18:16
1
$\begingroup$

Solution:

Leverage the fact that the op stated:

I do not show or tell the numbers to anyone

instead of

I do not show or tell the numbers to anything

To start, I have op write a 1 on one extra sheet of paper, and a 2 on another, showing me both.
I scan these into a computer using a scanner and write a program that leverages numerical OCR and math to convert the images into two numbers and output "E" if their sum is even, else "O" if their sum is odd. I tweak as needed to account for any idiosyncrasies with respect to the op's handwriting.
I test the program and verify it works.

I now have the op get two identical pieces of paper. On each piece of paper the op writes down a number, either 1 or 2, without showing me. When done, I take the papers and, without looking at them, scan them and run the program I created. When it outputs E or O, I am convinced beyond reasonable doubt as to whether the op's statement regarding the sum of the numbers is true or false. This leverages the assumption that for the op, "My writing is always the same - if I write the same number twice then it will look identical both times".

Bonus question: Same solution, but test the software with OCR on "3"'s.

Note: for the 1/2 basic case, this is also solvable with

very heavy ink and an extremely precise balance scale.

$\endgroup$
2
  • $\begingroup$ The 'instead' backdoor is interesting. I am not ZKP (that abbreviation already slipped into comments) expert, and, I don't know if in practical real life applications (which, I suppose, but I am not sure, no longer require human brains) that door is closed. I think I will want to follow a decent course about all this. Suggestions welcome. $\endgroup$ Apr 10 at 22:45
  • 1
    $\begingroup$ @FirstNameLastName this is equivalent to giving information to a third party trusted by both sides. In all "I want to prove something but I don't want to give this information to anyone" problems, usually it's assuming no commonly trusted third party (or specifically, the writer of the numbers really don't want to show the numbers to anyone, including a computer), otherwise it's trivial, as this answer shows. $\endgroup$
    – justhalf
    Apr 11 at 13:33
1
$\begingroup$

My answer is wrong please refer to explanation in answer 'case 1 2'

As for the bonus:

It needs a slightly more complex protocol. But the same idea remains: somehow I (verifier, spectator) must, following your protocol instructions, repeatedly interact with you to convince myself mathematically that you know something about the two initial numbers (the fact they are even). The protocol involves that each step I do something you do not 'see' (hence you do not know) but you can guess. The probabilities that you (prover, performer), acting logically and cooperative (since you want to prove me something), can guess what I did each step must, no matter what your initial numbers are, be such that, if sum were odd, you can always guess right, and if sum were even, you can't. Then, if you do not always answer correctly, sum must be even, without leaking information.

So now for the 'case $1$ $2$ $3$'. I do not have a general protocol for the 'case $1$ $...$ $N$' let alone for any integer. Perhaps such protocol exists and Dmitry Kamenetsky could let us know about it (in case one exists and if he knows it).

Here we go

You could (if allowed) add another extra identical paper and write a number on it. You choose the number not random but as follows: if original sum is even, you choose left number from pair, and, if original sum is odd, you choose number not in pair. So this time we take advantage of a property of all odd sums of pairs. Then you place the extra paper in between the original pair. You would explain me your strategy (but you do not show any number). Now, each step in the protocol, just like in 'case $1$ $2$', I am allowed, while you close your eyes, to swap, this time: either left or right one, with middle one. You must then inspect middle one and mathematically guess if there was a swap or not.

As it turns out for this particular choice (see overview below): In case original sum was odd, you can guess correctly with probability PO $1$ (i.e.: always) and, in case original sum was even, you can guess correctly with probability PE $\frac{1}{2}$ (in $\frac{3}{5}$th of the cases) and PE $\frac{2}{3}$ (in $\frac{2}{5}$th of the cases). The required ingredient (you can always answer correct if sum is odd) is present, and, so I can know what you know (that the sum is even). The $\frac{2}{3}$ is high but still less than $1$. It accounts for the pairs $(1,3)$ and $(3,1)$ that make simple protocol fail.

epilogue

I see two potential objections: (1) "is it allowed to bring in a third object into the guessing?", and (2) "does this protocol reveal any information?". I will not address (1). About (2): will it, in case you had $(1,3)$ or $(3,1)$, not suggest such to be the case (and reveal the numbers, not the order) because probability to guess correctly can be two times higher in that case (and expected number of guesses before first wrong one as well) than in all other even sum choices? Well, since only a single wrong answer is sufficient, even if it took a bit long, there is no 100% certain conclusion I can draw from what happened. Not sure if statistical information is counted and when it is relevant. The relevant sigma can be calculated but I don't do this here.

Here is overview of situations showing PO PE


==== 11 e m 1 111 e 0.5 111 <- no swap e 0.5 111 <- swap l e 0.5 111 <- swap r PE 1/2 ==== 12 o m 3 132 o 1.0 132 <- no swap o 1.0 312 <- swap l o 1.0 123 <- swap r PO 1 ==== 13 e m 1 113 e 0.5 113 <- no swap e 0.5 113 <- swap l e 1.0 131 <- swap r PE 2/3 ==== 21 o m 3 231 o 1.0 231 <- no swap o 1.0 321 <- swap l o 1.0 213 <- swap r PO 1 ==== 22 e m 2 222 e 0.5 222 <- no swap e 0.5 222 <- swap l e 0.5 222 <- swap r PE 1/2 ==== 23 o m 1 213 o 1.0 213 <- no swap o 1.0 123 <- swap l o 1.0 231 <- swap r PO 1 ==== 31 e m 3 331 e 0.5 331 <- no swap e 0.5 331 <- swap l e 1.0 313 <- swap r PE 2/3 ==== 32 o m 1 312 o 1.0 312 <- no swap o 1.0 132 <- swap l o 1.0 321 <- swap r PO 1 ==== 33 e m 3 333 e 0.5 333 <- no swap e 0.5 333 <- swap l e 0.5 333 <- swap r PE 1/2

$\endgroup$
4
  • 1
    $\begingroup$ Oh nice. I will need to think about this. $\endgroup$ Apr 10 at 15:02
  • 2
    $\begingroup$ Does your previous comment imply that this answer to the bonus is also incorrect? $\endgroup$ Apr 12 at 0:15
  • 1
    $\begingroup$ Yes, there is a fundamental flaw, perhaps not only in my reasoning (regardless of 1,2 or 1,2,3), but rather also in the way ZKP is sometimes presented, I am not entirely sure how to explain but @MichaelS certainly managed to cool me down. I am working on explanation. I may need help. $\endgroup$ Apr 12 at 2:08
  • 1
    $\begingroup$ In terms of P and V : it is not that V (not trusting P) imposes P a recipe to prove P to be honest, neither is it that P imposes V a recipe to follow, wanting show to V to know something. In both cases without extra information leaking. It is about (I think now) a contract of cooperation to reach best of both worlds. Neither P nor V is imposing anything. This sort of (crypto) solutions often gets lost in perfectly well meant recreational questions. But @DmitryKamenetsky your simple question : does 'same' has a ZKP such as 'different' has, is a very inspiring and valid one. Respect! $\endgroup$ Apr 12 at 2:26
1
$\begingroup$

In keeping with my answer to your Computer Science question, here's an answer that only involves 3 sheets of paper and doesn't involve showing me any numbers for the two-possibility case. I can't come up with a good answer for the three-possibility case, but I've given an answer that's not completely bad.

We have to assume you can't write anything on a paper except the allowed numbers (1, 2, and possibly 3), and any paper with a given number is indistinguishable from other papers with the same number.

Two Possibilities (1, 2)

The numbers 1 and 2 can be substituted for any other integers provided one is even and one is odd.

For the sum to be even, the two papers must contain the same number. So the proof is simply that the papers match: either both are 1, or both are 2.

So you write a number on a third sheet of paper that isn't the first number. If the existing sheets are both 1, the third sheet is 2. Otherwise the third sheet is 1.

Now, you prove the third sheet doesn't match the first sheet. You hand me both sheets. I ensure I never lose track of which is which, but I hide them from you so you can't tell while shuffling.

I show you (and only you) both sheets. You now know which is on the left and right. I hide them from you, and either leave them in place, or switch them left to right, randomly. I again show you each sheet, so you can tell left from right. You tell me whether I switched them or left them the same.

If you can consistently tell when I switched them or didn't, I know they're different. Otherwise, the test fails.

Since I kept track of when I switched them, I know which one is the third sheet. I place the first sheet to the side, then take the second sheet. I repeat the test to prove you know which is the second sheet and which is the third.

If you can consistently tell me which is the second and which is the third sheet, I know they're different. Since you were only allowed to write one of two numbers, and neither of the first two sheets matches the third, the first two sheets must match each other.

Three Possibilities (1, 2, 3)

We can substitute 1, 2, and 3 with any other integers provided two are odd and one is even.

Unfortunately, my answer to the Computer Science question won't completely work here.

That answer only shows the two numbers match. Here, it's also acceptable if the numbers are 1 and 3. So we have to prove neither of the papers has the number 2, or both have the same number.

First, we can simply test using the above method.

You give me four papers, $P_1, P_2, P_3, P_4$. The papers $P_2, P_3, P_4$ must have the numbers 1, 2, and 3, but I don't know which is which. $P_1$ + $P_2$ is claimed to be even.

Using the standard method, I prove that each pair of papers in [$P_2, P_3, P_4$] is different. I test you with $P_2\neq P_3$, $P_2\neq P_4$, and $P_3\neq P_4$. This ensures you have one of each number.

Now, I prove that $P_1$ is neither $P_3$ nor $P_4$ using the standard method, which tells me $P_1$ must be $P_2$.

If this proof succeeds, we're done. The result is guaranteed to be even. However, failure here isn't a total failure since there were multiple ways the result could be even.

Sadly, there's no way to find the answer without giving away some extra information.

If the two numbers don't match, any test proving the sum is even automatically tells us the numbers are 1 and 3.

You can write the number 2 on a paper, $P_5$, then use the standard method to prove that neither $P_1$ nor $P_2$ matches $P_5$. This proves that both are 1, both are 3, they're 1 and 3, or they're 3 and 1.

This never tells us the exact value of either paper, but I don't really like it, given the spirit of "zero information" protocols. I'd prefer a method that never distinguishes between

matching papers and papers aren't 2

but I can't think of such a method.

Real World (Lack of) Applicability

I'm unable to come up with any scenario where these "proofs" really work. As a puzzle, we can magic away some of the rules and that's fine. But it doesn't work in a practical setting.

The original test, that two objects are definitely different, is clear-cut. I can't tell two things apart, but you can. That's potentially useful, and is immediately convincing.

In this test, I require proof that you can't cheat. It would be trivial to make a small mark on one paper, or write the number in way you can see the difference but I can't, or just write completely different numbers than agreed upon. Since I'm not allowed to examine the papers, I have no way of showing that it's even likely you can't cheat.

So I'm required to either take your word for it, in which case I can just skip the entire test. Or take the word of a trustworthy third-party, in which case I can just have them verify on my behalf.

It might work as a magic trick of some kind. Use cards from brand-new card decks, and have an audience member verify the cards aren't tampered with. But magicians can easily acquire trick decks that are sealed, so that's not really convincing. And your average audience member isn't going to have to logical aptitude to be any more convinced by this proof than you just claiming you're right.

$\endgroup$
3
  • 2
    $\begingroup$ Getting there with just one extra sheet of paper is so far the leanest ZKP solution I read for 1 and 2. $\endgroup$ Apr 12 at 22:56
  • $\begingroup$ Perhaps, for all clarity, somewhere in answer you could mention : you=P and me=V $\endgroup$ Apr 13 at 12:45
  • $\begingroup$ Also, you could perhaps mention (and explain) that, when P's claim is false, no matter what "(perhaps not trust worthy) P writes on third paper", P cannot prove its claim to V (so protocol is sound). $\endgroup$ Apr 13 at 12:55

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