Home Tech Try with a puzzle that seems to have no solution

Try with a puzzle that seems to have no solution

2
0

It seems impossible to try to see if two people are doubting the same person without letting the other know that they are doubting someone.
According to Alex Bellos, author in charge of the journal Maths column The Guardian This puzzle is based on the concept Zero Knowledge Proof (ZKP) – A protocol that allows users to prove they know something but not reveal to others what that knowledge is like.

He added that the Abel Prize (considered the Nobel Prize for Mathematics) in 2021 was awarded to a pioneer in the field Zero Knowledge Proof – Scientist László Lovász (Mathematical Institute Alfréd Rényi and University of Eötvös Loránd in Budapest, Hungary), and Avi Wigderson (Institute for Advanced Study in Princeton, USA). The puzzle is as follows: Isla works in an office with 100 employees. One day, she discovered that her favorite paperclip was stolen by someone else. She identifies the suspicious object. Annabel, her colleague, said she was also suspicious of a person. Isla wants to know if she and Annabel are suspicious of the same person, but the two don’t want the other to know who they are doubting, in case they suspect different subjects. Isla thinks over and over how she and Annabel can check if they suspect the same person without revealing the information they find suspicious to the other party. The question is whether Isla and Annabel can find a way to reconcile their thoughts without letting the other know who they are doubting? This method should ensure that, after comparison, Isla knows whether she and Annabel are suspicious of the same person. Second, they need to make sure the other person doesn’t know they are distrusting. This verification is part of the protocol Zero-knowledge . At first glance, Alex Bellos judged that this was a puzzle without a solution. For example, Isla cannot say “The person I suspect was late for work on Monday” because it revealed some information about the other person. He also came up with a third party two-man solution, Dan, a good friend they trust a lot. Then, Isla and Annabel numbered the office staff from 1 to 100. Next, they write the number to replace the name of the suspect on a piece of paper and give it to Dan. If Dan confirms the two numbers are the same, they suspect the same person and vice versa. However, this solution is not perfect as no one can guarantee Dan from disclosing his number to the other person. Everything depends on the level of trustworthiness of the third party. Therefore, it cannot guarantee the non-disclosure of information as the quiz requires. Nearly 200 people participated in discussing Alex Bellos’s riddle and proposing measures to verify that Isla and Annabel were suspicious of the same person. Then, the author Alex Bellos together gave 3 relatively suitable methods. Can you take any measures to ensure the request of the assignment or not, ie Isla and Annabel know if they are suspicious of the same person and do not disclose information about the suspect to the other person? Readers who have difficult problems that need to be answered or want to share good calculations can send them to the newsroom at [email protected].