16
$\begingroup$

I have three bicycle locks, ones like this:

Picture taken from https://commons.wikimedia.org/wiki/File:Bike_cord_%26_lock_26d06.jpg

Because they look so much alike I etched a unique number into each lock and the same number into the keys that unlock it. Unfortunately I seem to have lost all my spare keys! (That also have the corresponding numbers etched into them.)

You tell me that you have one of my spare keys, but you don't want to tell me which one. Of course, I don't believe you.

How do you convince me that you have one of my spare keys, without letting me get any information whatsoever about which one you have?

I still have the keys to all the locks and I am willing to cooperate.

Disclaimer: This puzzle was inspired by a stackexchange answer.

https://crypto.stackexchange.com/questions/57674/how-do-i-explain-zero-knowledge-proof-to-your-7-year-old-cousin/57678#57678

Correct solutions to this problem have been given, however I was hoping someone would come up with a solution that

does not involve any props like tall trees or poles.

If someone comes up with a solution like this, which I would find more elegant, in a reasonable time span I will accept their answer, otherwise the green checkmark will go to Keelhaul.

(Picture taken from https://commons.wikimedia.org/wiki/File:Bike_cord_%26_lock_26d06.jpg)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I hope it's ok for me to move the goalposts like this. If it's not, then please let me know. $\endgroup$
    – Peter
    Mar 23, 2018 at 13:03
  • $\begingroup$ Am I holding your spare key up for ransom or something? I could just give you it. $\endgroup$
    – user253751
    Mar 24, 2018 at 7:47

6 Answers 6

Reset to default
24
$\begingroup$

Lock the three chains together in the form of the Borromean Rings, and hand me the linked set, then walk away so that you can't see which one I unlock. I unlock the one that I have the key for, separating all the rings. Then, leaving them all unlinked, I relock the chain that I unlocked, and return three unlinked chains to you.

It also works in "reverse", where you give me the unlinked chains, and I return them Borromean-linked.

Improve this answer
$\endgroup$
1
  • $\begingroup$ After seeing @LowKey 's solution - which is slick - I realized that this solution also works even if the locks and keys are visually identifiable by something other than specifically numeric engraving - say, letter engraving, or shape or color of the lock or cord, or et cetera. $\endgroup$
    – Jeff Zeitlin
    Mar 25, 2018 at 14:41
10
$\begingroup$

My answer:

Make a chain with all your locks as links around an object, so that you can't remove the locks chain without opening it (by opening one of its lock). For example, make the chain around a tall tree. Then go away while I open a lock, remove the chain from the tree and replace the lock, closing the chain again. This way, you won't know which lock I opened, but you'll know for sure I opened one in order to remove the locks chain from the tree.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ gosh, faster than me by 1 minute $\endgroup$
    – Kepotx
    Mar 23, 2018 at 12:53
7
$\begingroup$

The answers above all seem to rely on having access to the locks, and everyone seems to have forgotten about the numbers. The answer below works so long as none of the numbers are 0 (though you could probably alter it a bit to have it function even then).

Call the three numbers a, b, c. Ask your friend to give you the sum of the numbers, and also all three numbers multiplied together. You now have two equations symmetric in a, b, and c: $a+b+c=N_1$ and $abc=N_2$. This is a system of two equations with three unknowns. It cannot be solved unless you know one of the three numbers. Since you have the number, you can solve for all three, and relay all three numbers back to your friend. It doesn't matter whether you and your friend gave your key the same label or not, since the equations are symmetric anyways.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is slick! The only reason I like mine better is because it works even if the locks and keys are visually identifiable in some way other than the engraved numbers of the problem as stated. $\endgroup$
    – Jeff Zeitlin
    Mar 25, 2018 at 14:36
  • $\begingroup$ You seem to have switched “you” and “your friend”.   The OP is the owner of the locks and keys; the friend is the person who claims to have one of the keys. $\endgroup$
    – Peregrine Rook
    Nov 16, 2019 at 20:42
6
$\begingroup$

This seems to be related to

zero knowledge proof

Here what I can do to convince you:

I ask you to lock all three to make a chain
I unlock one of the lock, find a tree or a street lamp, and chain them around it
You don't know which lock I unlock, but know that I unlock at least one

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is essentially the "mirror image" of @Keelhaul 's answer. $\endgroup$
    – Jeff Zeitlin
    Mar 23, 2018 at 13:14
  • 2
    $\begingroup$ @JeffZeitlin he submitted while I write my answer, so I dont copy it, but yes, it's the same logic $\endgroup$
    – Kepotx
    Mar 23, 2018 at 13:16
  • 1
    $\begingroup$ @JeffZeitlin we both answered just a minute apart, no plagiarism here ;) $\endgroup$
    – Keelhaul
    Mar 23, 2018 at 13:20
1
$\begingroup$

While the answer using

Borromean Rings

is much more elegant, a simpler way without needing knowledge of how to do the aforementioned:

1. Pass all 3 locks to me locked
2. Turn your back to me
3. I unlock the one I have the key for
4. I hide the other 2 (conceal the other identifications)
5. I show you the unlocked one with my thumb covering the identification
6. You turn your back
7. I relock it and jumble the 3 locks and pass you them back
8. You give me the $20 finders fee (they're Halford's locks, they must be at least that a piece :P)

Improve this answer
$\endgroup$
2
  • $\begingroup$ How does the other party know you are showing them one of the three special locks if you have to hide the numbers that can show that? You could have come prepared with an identical lock you bought yourself. $\endgroup$
    – hkBst
    Mar 25, 2018 at 11:24
  • $\begingroup$ That's a lot of planning for what's more likely an on the spot thing, and perhaps is drilling too deep into specifics which the question doesn't (and perhaps shouldn't) cater for. ie Is the ID number engraved on all sides of the lock and various along the chain? Is it only on one side of the lock, if so without them turning their back, you could jumble them hiding the ID and unlock the one you have the key for. The basic premise is to show them you unlocking it while concealing the IDs, this can be achieved with simple requirements based on the question specifics. $\endgroup$
    – James
    Mar 25, 2018 at 12:05
0
$\begingroup$

Create multiple random numbers strings with length equal to the total amount of numbers in your three keys, and one which has a correct but random assortment of the keys' numbers.

Have me check which of your strings has all the numbers in my key in the correct amounts.

Do it multiple times until reasonable certainty is reached.

Alternatively, to reduce the issue of having to pick from a pool of 10 numbers that could overlap between the random numbers and the known numbers, you could split the keys' number strings in groupings of 2 and compare that way.

Improve this answer
$\endgroup$

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.