ICS Theory Group

October 23, Fall Quarter 2009: Thoery Seminar

1:00pm in 1423 Bren Hall

Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles.

By Ronen Gradwohl, Moni Naor, Benny Pinkas, Guy Rothblum.

Appeared in TOCS 2009

Presented by Rishab Nityanand, UC Irvine

Talk Overview: I decided to select a topic for my presentation which continues from my two presentations last year (Sudoku as a SAT problem, Overview of ZK Proofs). I will put both of them together and talk about this paper which presents cryptographic and physical ZK protocols to prove that Alice has a solution to a Sudoku puzzle. I will explain 2 of the cryptographic protocols and 2 of the physical protocols from the paper.