The aptly-named Journal of Craptology (est. 1998) has just published a special Valentine Day issue. It contains a silly piece on Romantic Cryptography that we originally discussed in 1999 in our Friday meetings.
The aptly-named Journal of Craptology (est. 1998) has just published a special Valentine Day issue. It contains a silly piece on Romantic Cryptography that we originally discussed in 1999 in our Friday meetings.
Interesting!
I have for a long time been after a crypto protocol to work out (in some approximate way) the degree of correlation between two people’s, er, shall we say “interests”, without revealing what those specifically are, and without relying on a trusted third party. It would ideally follow a protocol similar to this:
1) There is a universe U of interests (possibly predetermined?).
2) Alice and Bob each choose a subset of U which represents their interests, A and B respectively.
3) They perform some crypto operations which result in them both learning the size of the intersection between A and B, but not the members of the other person’s set.
Obviously this does leak some information: if the size of the intersection is the same as the size of A, then Alice learns that Bob has all of the interests in A. That’s probably not important if they are both approaching the system in good faith, but unlike your romantic cryptography protocol, an attacker might be willing to claim any subset in order to ‘steal’ information, and might be able to masquerade as more than one pseudonym in order to run the protocol multiple times – this trivially allows the attacker to deduce the contents of A.
I doubt that there is a way to fix this when the measure of correlation is the size of the intersection, but I do wonder if there is some other way to approach it 🙂
Having run the protocol with my (now ex-)partner I have discovered a serious vulnerability which the brains at Cambridge have clearly overlooked! I shall now explain this vulnerability and request that the Journal of Craptology editors insist on an immediate revision of the article prior to Sunday 14th.
The protocol fails to anticipate the emotion exhibited by A when she discovers that B does not reciprocate her love. It should of course therefore be apparent that B can launch an “emotional side-channel attack” when the participants execute the protocol in physical proximity of each other. Moreover, the close proximity of participants is a highly likely precondition for protocol executions for a multitude of reasons. For example, it is probably that A and B already share an apartment given: 1) A’s romantic attachment for B; 2) B’s inability to perform basic household duties; and 3) the current financial climate.
In conclusion the protocol is vulnerable to a practical emotional side-channel attack and therefore unfit for purpose. One can only assume that these technical details were overlooked due to the ‘poker face’ training undertaken by the authors, under the supervision of The Real Hustle’s Paul Wilson.
@Torne
about the same time (circa 1999) Kan Zhang (also, at the time, a member of the Cambridge security group) was thinking of something along the lines of what you’re after. A bit of googling yielded this (manuscript?)
A private matchmaking protocol
Kan Zhang, Roger Needham
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.835
@ Just dumped
I like your comment about A’s emotions potentially showing through. I’d call it “side-channel leakage” rather than an attack, though, because I cannot see a motivation for B (the non-loving one in your scenario) to mount an “attack” to find out about A’s feelings; since B doesn’t love A, B doesn’t actually give a damn whether A loves B or not. Unless B is a sadist and runs the protocol (*) just to make A feel bad. In which case it’s probably just as well for A that it all
ends in tears now, rather than in more tears later. (Unless A is a masochist and WANTS to be mistreated by B…)
(*) To me the main weakness is instead the fact that the one who initiates the protocol usually leaks information just by the fact of initiating the protocol (if s/he didn’t care, she wouldn’t even think about starting it). So the core one-on-one protocol is not very effective unless wrapped in some higher level social protocol that “forces” both partners to run the inner protocol no matter what, eg “it’s Valentine’s day so let’s run this protocol because it’s a long standing tradition”. On other days, A should invent some other imaginary bullshit tradition that would provide plausible deniability for wanting to run the protocol: “even if you never heard about it, at least it’s a tradition IN MY COUNTRY, now we HAVE to do it otherwise it’s incredibly bad luck”.
@Just dumped.
JCrap welcomes technical correspondence. To be accepted any submission must make the editors laugh (or at least smile broadly).
@Frank Stajano
That’s interesting, but I don’t think it can be applied. The protocol described finds exact matches (because the key is a hash of the wish), and thus can’t approximate..
@ Torne
You might do something with Bloom filters, perhaps?
@Frank Stajano
Ooh. That looks promising actually; selecting the parameters such that the false positive rate is sufficient to plausibly deny any particular thing, but not so high that AND’ing two together and counting the bits produces a meaningless result. I think I have been looking at too much crypto and not enough probability to try and solve this one. Thanks a lot!
I am unable to have a romantic relationship because I have a personality disorder.
@Torne
You’re most welcome!
@BLEK
Sorry to hear that. A psychiatrist might probably be more helpful than a craptologist, then.
@ my coauthor Will
Glad you got in touch!