Sunday, September 26

Can you solve it? The crazy math of cryptography | Math

Today’s puzzle is based on a revolutionary mathematical concept that last week earned one of its pioneers the Abel Prize, considered the Nobel Prize in mathematics.

The concept is the zero knowledge test, and it has many applications in digital cryptography.. Let me explain briefly.

Usually in math, and in life, when you want to prove a statement to be true, you must present evidence to support your claim. However, with a zero knowledge proof, it is possible to prove that a statement is true without revealing any supporting information.

For example, let’s say I have solved an extremely difficult Sudoku puzzle and I want to show you that I have solved it. A zero knowledge test will convince you that I have solved it without revealing anything at all about my solution.

Embarrassed? You are in good company. When the zero knowledge test first appeared in the 1980s, the math community at large was eager. The whole idea seemed strange and counterintuitive. Ultimately, however, it represented a conceptual revolution in the way mathematicians think about proof, and has found fantastic applications in cryptocurrencies and crypto systems, where users want to establish trust but keep crucial information confidential. .

Let’s go to the puzzle and continue the discussion later.

The stolen paper clip

You work in an office of 100 people. One day your favorite clip is stolen. You have a pretty good idea who did it. Her colleague Annabel tells her that she has a pretty good idea too.

He wants to check with Annabel that they are both suspicious of the same person, but neither of them is willing to identify his suspect in case he is thinking of different people. (Due to office policy, no one wants to point fingers.)

Think of a method that allows you and Annabel to verify that your suspect and the suspect are the same person, without either revealing information about your suspects.

What the puzzle asks is this: Can you and Annabel agree on a way to compare your information without revealing anything? At the end of your ‘comparison’, you will have established that your suspects are the same person or you will have established that they are not. In the latter case, you will not have leaked any information to Annabel, nor will she have leaked anything to you. The verification procedure is therefore “zero knowledge”, as no knowledge is disclosed except the truth or falsity of the verification itself.

I agree, it sounds impossible!

Here’s one thing you can’t do: You can’t share anything with Annabel that identifies your suspect. You cannot say, for example, ‘My suspect is late on Mondays’ as that reveals certain information about that person.

Usually in the column I say NO SPOILERS (capitalized!). But today is different, as I ask you to contort your brain in a way that you have probably never contorted it before. And there are many solutions, each with its strengths and weaknesses.

Here’s one: imagine that you and Annabel have a good friend Dan, whom you both trust. Here is a method involving Dan that works:

  • STEP 1 You and Annabel agree on a way to assign a number from 1 to 100 to everyone in the office.

  • STEP 2 Write the number of the person you suspect on a piece of paper. Annabel does the same.

  • STEP 3 You give Dan the two sheets of paper and ask him to tell you if both pieces have the same number.

If Dan says the numbers are the same, you know the suspects are the same. If the numbers are different, the suspects are different, and neither you nor Annabel know who the other person suspects. Work done!

However, the Dan option is not perfect. First, it relies on there being a Dan, that is, an independent and truthful verifier, which may not always be the case. More importantly, both of them are revealing information to Dan. The goal of this exercise is to never reveal anything to anyone. Is there a way that doesn’t involve anyone else?

Feel free to make suggestions below the line on how you would like to approach the problem. Please don’t give a complete solution if you know one.But help each other and work in groups!

I’ll be back at 5pm UK with a solution and more discussion.

I mentioned at the top that the Abel Award 2021 honored one of the pioneers of the zero knowledge test. His name is Avi Wigderson, 64, and he was awarded together with László Lovász, 73, for his “leading role in the formation [theoretical computer science and discrete mathematics] in central fields of modern mathematics “.

In the 1980s, Wigderson, along with Oded Goldreich and Silvio Micali, showed that any true mathematical statement has a proof of zero knowledge. At the time, this result was a purely theoretical advance, but in recent years zero-knowledge tests have found important applications in digital security, especially in cryptocurrencies and authentication systems. The zero knowledge test allows two people to establish trust without revealing anything.

If you are interested in learning more about the work awarded with the Abel 2021 award, you can enjoy this short video that I made for the Abel Award that was broadcast during the announcement ceremony. It offers a layman’s summary of Lovász and Wigderson’s work and (4 minutes) gives an example of a zero knowledge test (which may be helpful in trying to solve today’s puzzle).

The explanation of the zero knowledge test is 4 minutes

I put a puzzle here every other week on Mondays. I am always looking for great puzzles. If you’d like to suggest one, please email me.

I am the author of several puzzle books, the most recent the puzzle book for language lovers.

Leave a Reply

Your email address will not be published. Required fields are marked *