Cryptographic challenges: epilogue and solution of the last challenge

Every crypto fan knows the story of how British intelligence recruited ordinary citizens in the middle of World War II through riddles in the

newspaper .

For years these singular cryptanalysts fought the German ciphers in the cabins of the Government Code and Cipher School in Bletchley Park.

I couldn't help thinking about it when Bernardo Marín asked me to coordinate the launch of a series of cryptographic problems for EL PAÍS to challenge the ingenuity of readers.

With the rise of new communication technologies, the need for Cryptography experts is no less pressing today than it was in Bletchley's time.

However, far from seeking to recruit anyone, our goal was to pose a riddle and, at the same time, to spread the word: to explain in an accessible way some concepts related to modern Cryptography.

Several enthusiastic experts got to their wits and designed their challenges based on encrypted messages in different formats, imperfect summaries, cryptocurrencies, secrets in pieces, strategies to calculate odds and even a zero-knowledge proof with poker cards.

Without intending to, we have formed a small virtual squad of readers who, over the course of almost five months, have dared with the ten challenges.

Some have sent us their ideas, have shamelessly shared their frustration and, on occasion, have made us see our mistakes and inaccuracies.

The responses received in our email account revealed great differences in style, training and previous knowledge in Cryptography.

Surprisingly, that diversity was not so in terms of gender.

Four of the ten challenges were submitted by women, but the vast majority of responses and comments received have been from men.

It does not necessarily mean that they have not participated in the challenges, but it does mean that they have not been so expansive when it comes to sharing their solutions and interacting with the community of readers.

More information

The why of cryptographic challenges.

See the ten challenges

For those of us who were trained in the era before inclusive language, cryptanalysis is written in the feminine.

Traditionally, any cryptographic scheme or protocol was raised involving certain legitimate users (Alice, Bob, Charlie...) faced with the adversarial action of an intruder (typically named Eve or Tracy).

Although the choice of these fictitious names is usually related to terms in English (Eve from

, the one who spies, Tracy from

, the one that analyzes the communications traffic), other justifications are possible.

I choose to think that "Eva" represented a kind of romantic heroine, who wielded mathematical and computational tools in the worst conflicts (weapons much nobler and more effective than those reserved for male combatants).

Hence my uneasiness to see that in our Cryptographic Challenges, Eva has almost always been

We conclude this epilogue by thanking all the teachers who, with their dedication and ingenuity, have designed the challenges;

to our illustrator, Bel Martín, who has endowed the challenges with a stupendous graphic personality;

and, above all, to the followers of this section for their fidelity and effort;

especially, to those who have written to us during these months.

We have learned and enjoyed tremendously with your messages;

once again, everyone, thank you.

SOLUTION TO THE TENTH CHALLENGE

This week's challenge was surely one of the most complicated.

Despite this, we have obtained some interesting answers and even an alternative solution to the one we had identified.

This is the solution we propose: once the voting is complete, the three face down cards in the left half are placed in an envelope and the same is done for the other three cards.

The packs are then shuffled in such a way that neither voter can tell which is which (this can be achieved, for example, by having one voter shuffle while the other has their eyes closed and vice versa).

Then, the cards are removed from the envelopes and placed again, in the corresponding spaces, maintaining the relative order of each group of three cards.

Thus, the cards may have stayed as they were 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 all the cards over and mix them up so that the order of the two cards that have not been revealed is not known.

This protocol is a recreational example (implemented with physical elements) of what in Cryptography is known as multipart computing protocols, which, in the real world, are algorithms that run on electronic devices with computing power.

In this type of protocol, several entities have the objective of calculating a function that depends on an

or secret input from each one of the entities.

The objective of the protocol is that, without external intervention, the group of entities is able to calculate the

or output of the function in such a way that each of the entities does not obtain information about the inputs of the rest beyond what the output itself provides.

Our example is a protocol with two parts in which the output of the AND function or logical conjunction is calculated.

The key to how the protocol works is to observe that, for the four possible vote configurations, the two cards in the bottom row that are on the heart side of the top row mark the desired result for the protocol.

Regarding the privacy of the votes, it is clear that revealing the top row does not give information, since the two cards may have been exchanged or remained as they were.

If the two cards in the bottom row correspond to “Cut”, there is no problem, since it is clear that both voters have chosen “Cut”.

On the other hand, if they correspond to "Forgive", there is no way to know if these two cards are the ones that were placed at the beginning or are the vote of the row below.

We encourage the reader to find someone to test run the protocol with on real materials,

The article has been used as reference:

Kastner, J., Koch, A., Walzer, S., Miyahara, D., Hayashi, YI, Mizuki, T., & Sone, H.

.

International Conference on the Theory and Application of Cryptology and Information Security (pp. 126-155).

Springer, Cham.

December, 2017.

Our reader, Salva, has proposed a very ingenious solution in which the cards of each selected list are shuffled, in addition to the envelopes.

This is how he explains it to us:

We code the cards as R (ace of hearts) and N (ace of spades).

The 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 ones, that is, an R card. We shuffle those 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 mix the envelopes so that it is not possible to know which envelope contains each group of cards.

In the case of having chosen the option "Cut" for the queen and the king, that is, both in the RN order, when choosing the cards in the indicated manner we would have three red cards in one envelope and three black cards in another, so that when opening a pack and looking at three cards of the same type, we would know that the final option is to “Cut” (but surely this is not the case).

In any other case where the final result is “Forgive” (1st Queen: RN, King: NR; 2nd Queen: NR, King: RN; 3rd Queen: NR, King: NR), when picking cards In the indicated manner we would have two cards of one type and the other of the other type in an envelope, leaving 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 they have chosen the queen and the king (not even between them), because the only thing that could be known is that one/or (or both) has (n) chosen "Forgive".

You can follow EL PAÍS TECNOLOGÍA on