Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles

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

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

16 اقتباسات (Scopus)

ملخص

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier. In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize scratch-off cards, similar to those used in lotteries, or even just simple playing cards. The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by "lay-people" and implementable without the use of computers.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفFun with Algorithms - 4th International Conference, FUN 2007, Proceedings
الصفحات166-182
عدد الصفحات17
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2007
منشور خارجيًانعم
الحدث4th International Conference on Fun with Algorithms, FUN 2007 - Castiglioncello, إيطاليا
المدة: ٣ يونيو ٢٠٠٧٥ يونيو ٢٠٠٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4475 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference4th International Conference on Fun with Algorithms, FUN 2007
الدولة/الإقليمإيطاليا
المدينةCastiglioncello
المدة٣/٠٦/٠٧٥/٠٦/٠٧

بصمة

أدرس بدقة موضوعات البحث “Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا