Any Cryptography fan knows the story of how British intelligence recruited ordinary citizens through puzzles in the Daily Telegraph newspaper in the middle of World War II. For years these unique cryptanalysts battled German ciphers in the shacks of the Government Code and Cipher School in Bletchley Park.
I couldn’t help but think about it when Bernardo Marín asked me to coordinate the launch of a series of cryptographic problems for EL PAÍS to challenge readers’ ingenuity. With the advent of new communications technologies, the need for cryptography experts is no less pressing today than it was in Bletchley’s day. Far from recruiting anyone, our goal was to pose a conundrum while spreading the word: to explain some concepts related to modern cryptography in an accessible way. Several enthusiastic experts came to their senses and designed their challenges based on encrypted messages in various formats, imperfect summaries, cryptocurrencies, secrets in pieces, strategies for calculating odds and even a zero-knowledge proof with poker cards.
Without meaning to, we formed a small virtual crew of readers who took on the ten challenges over the course of almost five months. Some have sent us their ideas, shamelessly shared their frustrations, and occasionally pointed out our mistakes and inaccuracies. The replies received in our email account showed wide variation in style, education and prior knowledge of cryptography. Surprisingly, this diversity was not so when it came to gender. Four of the ten challenges were submitted by women, but the vast majority of responses and comments received were from men. That doesn’t necessarily mean they didn’t participate in the challenges, but it does mean they didn’t share their solutions as widely and interacted with the community of readers.
More information
For those of us educated in the pre-inclusive language era, cryptanalysis is written in the feminine form. Traditionally, any cryptographic scheme or protocol was created involving specific legitimate users (Alice, Bob, Charlie…) faced with the adversary action of an intruder (usually named Eve or Tracy). Although the choice of these fictitious names mostly refers to English terms (Eve from eavesdropper, the one who spiones, Tracy from traffic analyst, the one who analyzes communication traffic), other justifications are also possible. I choose to think that “Eva” represents some sort of romantic heroine, using mathematical and computational tools (weapons far more noble and effective than those reserved for male combatants) in the worst of conflicts. Hence my uneasiness to see that Eva was almost always him in our cryptographic challenges.
We end this epilogue by thanking all the teachers who, with their dedication and ingenuity, designed the challenges; to our illustrator Bel Martín, who endowed the challenges with an amazing graphic personality; and especially to the followers of this section for their loyalty and dedication; especially to those who have written to us over the past few months. We have learned and enjoyed tremendously from your messages; Thanks again everyone.
SOLUTION OF THE TENTH CHALLENGE
This week’s challenge was certainly one of the most complicated. Despite this, we received some interesting answers and even an alternative solution to the one we identified.
We propose the following solution: once the voting is complete, the three face-down cards are placed in an envelope in the left half, and the same with the other three cards.
The packs are then shuffled in such a way that none of the voters can tell which is which (this can be achieved, for example, by one voter shuffling while the other has their eyes closed and vice versa).
Then the cards are removed from the envelopes and placed back in their appropriate boxes, maintaining the relative order of each group of three cards. The cards can have stayed the same or been swapped, the three on the left with the three on the right.
The two cards in the top row are then revealed.
The two bottom row cards that are on the heart side of the top row are then revealed. The order of these last two letters provides the result of the protocol.
Finally, it is important to turn over and shuffle all the cards so that the order of the two unturned cards is not known.
This protocol is a recreational example (implemented with physical elements) of what are known in cryptography as multipart computer protocols, which in the real world are algorithms executed on electronic devices with computing power. In this type of protocol, multiple entities aim to compute a function that depends on input or secret input from each of the entities. The goal of the protocol is that, without external intervention, the set of entities is able to compute the output of the function in such a way that each of the entities does not get any information about the inputs of the other beyond the output itself provides. Our example is a two-part protocol in which the output of the AND function or logic operation is calculated.
The key to how the protocol works is to note that for the four possible voting configurations, the two cards in the bottom row that are on the heart side of the top row mark the desired outcome for the protocol. Regarding the confidentiality of the votes, it is clear that revealing the top row does not provide any information, as the two cards may have been swapped or remained as they were. If the two cards in the bottom row match Cut, there is no problem as it is clear that both voters have chosen Cut. On the other hand, if they equal “Forgiveness,” there’s no way of knowing whether those two cards are the ones placed at the beginning or are the voice of the row below. We encourage the reader to find someone to try doing the protocol with real materials, it’s great fun and can even help in shared decision making!
The article was used as a reference:
Kastner, J., Koch, A., Walzer, S., Miyahara, D., Hayashi, YI, Mizuki, T., & Sone, H. The minimum number of cards in practical card-based protocols. International Conference on Theory and Application of Cryptology and Information Security (pp. 126-155). Springer, Cham. December 2017.
Our reader Salva has suggested a very ingenious solution that involves shuffling the cards of each selected list in addition to the envelopes. This is how he explains it to us:
We encode the cards as R (Ace of Hearts) and N (Ace of Spades). Queen and King choose the order of their cards (RN: “Cut” or NR: “Forgive”) and place them face down. We choose the first card of the queen, the first of the king and the second of the added cards, that is, a card R. We shuffle these three cards and put them in an envelope, and we also take the other three cards ( the second of the queen, the second of the king and a letter N), we shuffle them and put them in another envelope. Later we shuffle the envelopes so you don’t know which envelope contains which group of cards.
If we had chosen the “Cut” option for the Queen and King, i.e. both in RN order, when selecting the cards in the manner indicated, we would have three red cards in one envelope and three black cards in another , so we when opening a pack and looking at three cards of the same type, you would know that the last option is “cut” (but that’s certainly not the case).
In any other case where the end result is forgiveness (1st Queen: RN, King: NR; 2nd Queen: NR, King: RN; 3rd Queen: NR, King: NR) when we play cards on the draw two cards of one type and the other of the other type in one envelope and leave the other on the complementary option, and since we do not know the group of cards chosen for each envelope, it is not possible to know the option that they chose the queen and the king (not even between them), because the only thing that could be known is that one/or (or both) chose “forgive”.
Follow EL PAÍS TECNOLOGÍA on Facebook and Twitter or sign up here to receive our weekly newsletter.