Hacker News Reader

Comment by mkagenius | Hacker News Reader

Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.

I solved it a little differently than the suggested method.

The suggested solution requires a box that is capable of being locked in both the lid and box by two padlocks. It also requires (Spoiler!) the ring to make two pointless transits, which could be expensive if it was large.

What if, instead, the box was capable of admitting only one padlock? Then Jan would padlock it closed. On receiving the locked box, Maria locks her padlock to Jan's, and returns the box (still locked with Jan's padlock, and not necessarily containing anything.) Then, on receiving the box back from Maria, Jan can form a chain that can be broken by either his padlocks (which he can remove) or by Maria's padlock (which she can remove). Then he can attach the chain to any box. Perhaps he should clip one more of his padlocks only to hers, so she can also select a new box.

Of course, this relies on some properties of padlocks that are not necessarily transferrable to cryptography.

> Jan can form a chain that can be broken by either his padlocks or by Maria's padlock

The box cannot be opened by Maria, breaking the rear end of chain wouldn't help at all.

The chain would start:

    Box - J - Lid

Maria adds hers:

    Box - J - Lid
          |   
          M

Jan can open his padlock, releasing hers, and transform this to:

   Box - J - M - J - Lid

Which Maria can open. An optimization could be:

    Box - M - J - Lid

This is available if Maria could fit her padlock through the port in the box simultaneously with Jan's there, and send that back so Jan could remove his initial box padlock.

And the arrangement

    Box - M - J - Lid
          |   |
          J   M

Would let either start a new box, using the J - M - J or M - J - M chaining as needed.

Nicely done. Understood the chaining solution now. One small assumption in that would be that the chain remains taut enough to not leave any gaps to slide the hands into the box (since the lid's hook is no longer in touch with the box).

That puzzle needed more clarification. The solution talks about having two padlocks affixed to the same box, but I can't imagine any kind of box that can have 2 padlocks affixed to it unless the box is specifically designed to allow 2 locks.

A quick search for padlocked box will show many, many such boxes. It seems more common for there to be space for two or more locks, than for just one.

My point is that the puzzle should be updated to inform the reader that designing the right kind of box is a part of the puzzle:

"Jan and Maria each have plenty of padlocks, but none to which the other has a key. Using only the padlocks, keys, and a custom-designed box, how can Jan get the ring safely into Maria’s hands?"

You could always take a one-lock box and build an adapter that accepts two locks, and keeps the box locked if either lock is present.

This just isn't true. I mean, yes they exist, but the norm is overwhelmingly a single latch with room for a single lock.

Without a third party showing sales of padlock boxes with and without space for two or more locks, there's no actual way of being SURE which is more common.

Even if there are ten times as many boxes available that only have space for a single lock, what matters in the case of the puzzle is, a box with space for two or more locks is readily available. Suggesting in the puzzle "by the way the box has space for two locks" really kind of destroys the "puzzle" aspect.

I'm mad at myself for not managing to figure this out myself.

I guess i made more assumptions about the limitations than there were in the description of the problem.

I think you'd enjoy The Code Book by Simon Singh.

Same. It was not clear that multiple padlocks can be added to the box.

It took me way too long for this reason. I got it instantly once I realized I had made that limitation up.

I feel like there is some sort of lesson, here.

> I guess I made more assumptions about the limitations than there were in the description of the problem.

This accounts for some high percentage of the failures in figuring out brain teasers :)

Assuming cryptography exists in Kleptopia, couldn't he use a padlock with a combination and transmit this electronically?

Two points -- one, that's outside of the problem statement, so no, you can't use cryptography. Two, public-key cryptography uses an exact analogy of the physical-world method, so if you have access to a cryptographic solution you've already solved the problem.

Interesting to me that there is an analogy with a 1000 year old puzzle.

https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_pu...

There isn't really an analogy here, it just seems like it.

The apparent similarity between these two is due to there being multiple trips in both -- across the river in one, and through the mail in the other. But the reason for the multiple trips are entirely dissimilar, and so the similarity is purely superficial.

My sister's solution: Send the ring in a box with a combination lock ;)

Edit: Ah, charlesdenaul already proposed that. You wouldn't need cryptography, as the problem doesn't state that the postal service also monitors the Internet.

It's a really good metaphor for explaining public key cryptography.

Alternative solution: send her a model of the key to 3d-print

How are you sending the model safely?

After she gets the package. If the post staff just break into your house to take your stuff based on internet communication, they'd find out about your ring the next time one of you mentioned it, among other problems.

I presume email, and that GP misspoke when they said "model" and meant a file that the key could be modeled and printed from. That being said, that solution definitely skirts the intention of the puzzle, but would certainly work given the restrictions the puzzle did list.

model as in 3D model

:). OTOH, as someone interested in high latency communication protocols I wish cryptographers would hesitate to suggest a three round trip protocol at postal latency.

My solution is that Jan should send the ring in a padlocked wooden box with an inner protective but unlocked box and Maria should apply a saw to the outer box.

(To be fair, I can certainly imagine that in Kleptopia they know how to make excellent boxes).

Even simpler: send it in a padlocked cardboard box which Maria can rip open with her hands. Nothing in the problem statement says that the box itself has to be resistant to attack.

Simplest, drive her the key

Or send a bunch of hobbits with the key.

I noticed that one proposed solution is pretty pointless: attach a key to the hasp of the first locked box. The key can then be copied ("stolen" in today's copyrights-holder's parlance) by anyone along the mailing route, and the first person to use the key gets the ring.

This, aside from the fact that the key on the hasp is not "inside a padlocked box" ...

You are right. Sending key is bad idea.

Another alternate solution was a bummer..

> Win at Wimbleton > 9999-9997 : Roger was wearing himself out

I mean, seriously?

Should work fine if the locked box is sent first...

Not bad. Sadly this one has no (secure) digital parallel.

> How can Jan get the ring safely into Maria’s hands?

Jan will get the bus.

Or pay for three mailings, whichever is less expensive.

I knew "the" solution was something DH-like, but my solution was:

Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock.

...I think others are overcomplicating this.

> Maria mails Jan one of her padlocks

I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.

I don't know, why would someone steal a padlock unless it was attached to a box? Maybe so, though.

If not steal, can definitely make a copy of the key :)

The wording of the problem is "anything sent through the mail will be stolen unless it is enclosed in a padlocked box".

Jan constructs an enormous box around the entire country of Kleptopia, and places his own padlock on it from the inside. Then he mails the ring with no additional security measures.

The problem is fatally flawed by not explicitly stating that boxes locked with padlocks are also not stolen, despite not being enclosed in a padlocked box.

Jan takes a normal box and locks it. He declares the space enclosed by the box to be the "outside," and the world to be "inside."

Unfortunately, the mail thieves declare "outside" to be the volume in conformal space on the side of the boundary definition that contains the point at infinity, and "inside" to be the volume that does not, and thus steal the ring.

Those jerks, they're always one step ahead.

Of course the point at infinity had been stolen some time ago, and its whereabouts are currently unknown.

> anything sent through the mail will be stolen unless it is enclosed in a padlocked box

If someone stole the padlocked box then they would necessarily also steal whatever's inside. Therefore (non-empty) padlocked boxes are safe to mail.

Aha!

Then you put a tiny corundum crystal inside a tiny padlocked box, and permanently affix it to the ring. (Or perhaps the ring has a lockable box portion.) Now the ring cannot be stolen without also stealing an object that is inside a padlocked box. Safe to mail.

Or even better: a thief replaces the padlock with one of his own, then later steals the ring.

What you really need is a trusted "padlock authority" that can verify the authenticity of your padlocks...

Reply on news.ycombinator.com