Five Cells is a pencil puzzle consisting of a rectangular grid, with some cells containg a number. The player has to partition the grid into blocks, each consisting of five cells, such that the number in each cell must be equal to the number of edges of that cell that are borders of blocks. In this paper, we propose a physical zero-knowledge proof protocol for Shikaku using a deck of playing cards, which allows a prover to physically show that he/she knows a solution of the puzzle without revealing it. More importantly, in the optimization we develop a technique to verify a graph coloring that no two adjacent vertices have the same color without revealing any information about the coloring. This technique reduces the number of required cards in our protocol from quadratic to linear in the number of cells and can be used in other protocols related to graph coloring.


翻译:五个单元格是一个由矩形网格组成的铅笔拼图, 有些单元格包含数。 玩家必须将网格分割成块块, 每个由五个单元格组成, 这样每个单元格的数必须等于该单元格的边缘数, 也就是区块的边框数。 在本文中, 我们建议使用一张扑克牌为志家提出一个物理上的零知识证明协议, 使证明人能够实际显示他/ 她知道谜题的解答, 而不透露它。 更重要的是, 在优化过程中, 我们开发了一个技术, 来验证一个图形颜色, 显示两个相邻的顶部没有相同的颜色, 而没有透露任何关于颜色的信息。 这个技术可以减少我们协议中要求的卡片数, 从细胞数的二次角到直线, 并且可以用于与图形颜色有关的其他协议 。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
11+阅读 · 2022年9月1日
Arxiv
10+阅读 · 2021年11月3日
A Survey of Deep Learning for Scientific Discovery
Arxiv
29+阅读 · 2020年3月26日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员