Date : May 25, 2023, 1:30 p.m. - Room :Salle A104

Physical application to zero-knowledge proof protocol and NP-completeness

Léo ROBERT, post-doc - LIMOS

Suguru is a pen-and-paper puzzle which resembles to sudoku; you need to fill a grid with numbers following some rules. How can you convince that you have the solution without revealing any information about the solution? Firstly, we will see a protocol using day-to-day objects (such as playing cards) to prove that a party has the solution without revealing any piece of information about that solution.

Secondly, we will see a proof about the hardness of solving a suguru instance.