June 28, 2006

Matrimonial cryptography

This real-life puzzle was sent in by Daniel:

Sarah and I are getting married in September, and want to engrave an encrypted message in our rings. The catches:

(1) Each ring should make sense on its own. I.e., neither ring may look like "XJFIWLGOSIBNQ".
(2) Only about 20 characters can fit on each ring.
(3) The message must require both rings to be decoded; further, every *character* of the message must require both rings to be decoded.

[Update: further explanation can be found here.]

Daniel worked out that an ideal method would be for each ring to serve as a "one time pad" for the other. If the message on his ring is D and the message on her ring is S, then the desired result can be defined as M = D+S, where D and S are combined element-wise (via modular arithmetic, XOR or some other invertible function) to make the joint matrimonial message M.

However, he also recognizes that finding D, S and M such that all are readable (and appropriate) strings is a daunting task.

My best approximation is to suggest that he choose D, S and M as mathematically arbitrary (but personally meaningful) strings; then define X so that D+S+X = M, i.e. X = M - (D+S). Then engrave his ring with D and half of X, and Sarah's ring with D and the other half of X.

This partially violates condition (1), since 1/3 of the characters on each ring appear to be gibberish. However, it does have the property that M is a simple function of both inscriptions, and hard to decrypt otherwise. (And yes, I know that to achieve Shannon security, you'd have to introduce a genuinely random keystream into the process; but as far as I can see, that would require half the characters on each ring to be unreadable gibberish, whereas the 1/3 gibberish in my solution is already too much. Dan is looking for a metaphor to defeat the odds of life and love, not a code that will baffle the NSA. What? Life and love are tougher opponents? Well, perfect encryption of wedding rings probably still isn't either a necessary or a sufficent condition for victory, even metaphorically...)

If you can suggest a better (but still practical) approach to finding inscriptions for Dan and Sarah's rings, let me know. You should be able to get a wedding invitation out of it.

Posted by Mark Liberman at June 28, 2006 07:14 AM