(18.210.12.229) 您好!臺灣時間:2021/03/05 11:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:柯東爵
研究生(外文):Tung-Chueh Ko
論文名稱:數字推盤遊戲之零知識證明
論文名稱(外文):Zero-Knowledge Proofs for (N^2−1)-puzzle
指導教授:趙坤茂
指導教授(外文):Kun-Mao Chao
口試委員:王弘倫吳彥緯
口試日期:2019-07-26
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:21
中文關鍵詞:零知識證明數字推盤遊戲數字華容道對稱群認證加密協議
DOI:10.6342/NTU201902079
相關次數:
  • 被引用被引用:0
  • 點閱點閱:33
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在十九世紀發明以來,數字推盤遊戲已經是個廣為流傳的謎題遊戲。雖然遊戲規則十分簡單,但是卻有相當的挑戰性。因此有很多關於數字推盤遊戲的發表和研究。我們在此篇論文中,提出一套專為數字推盤遊戲設計的零知識協議。這個協議能推廣到所有正方形版面都能夠使用。利用這個協議,協議其中一方證明者可以向另一方驗證者證明「證明者知道謎題答案」,而且在這個過程中不會洩漏任何關於謎題答案的資訊。
Since invented in the 1870''s, 15-puzzle has now become a world famous puzzle game. This puzzle has various analyses in the field of mathematics. We design an interactive zero-knowledge protocol based on the problem. One case is 8-puzzle given a fixed number of move, the other is extending the scheme from 8 to all (N^2-1)-puzzles, N represents the length and width of the puzzle.
Abstract i
List of Figures iv
1 Introduction 1
1.1 Zero-Knowledge Proof 1
1.2 ZKP for Puzzles 2
2 Problem Definition 3
2.1 Permutation 3
2.2 Legal Moves of (N2 − 1)-puzzle 4
2.3 Cryptographic notations 6
3 Taking 8-puzzle as an Example 8
3.1 Hiding Information 8
4 Protocol 13
5 Proof of ZK Protocol 16
5.1 Completeness 16
5.2 Soundness 16
5.3 Zero Knowledge 17
5.4 Number of Rounds 18
6 Conclusion 19
Reference 20
[1] D. Ranter and M. Warmuth, “Finding a Shortest Solution for the N×N Extension of the 15-PUZZLE Is Intractable.” Association for the Advancement of Artificial Intelligence (AAAI), pp. 168–172, 1986.
[2] ——, “The (n2−1)-puzzle and related relocation problems.” Journal of Symbolic Computation, no. 10, pp. 111–137, 1990.
[3] H. Ripsom-Gardiner, “Zero-Knowledge Proofs for Puzzles,” Honors Program Capstone Projects, no. 5, 2016.
[4] E. Volte, J. Patarin, and V. Nachef, “Zero Knowledge with Rubik’s Cubes.” IACR Cryptology ePrint Archive, p. 174, 2012.
[5] ——, “Zero Knowledge with Rubik’s Cubes and Non-abelian Groups,” International Conference on Cryptology and Network Security (CANS), pp. 74–91, 2013.
[6] A. Chapple, A. Croeze, M. Lazo, and H. Merrill, “AN ANALYSIS OF THE 15-PUZZLE.” [Online]. Available: https://www.math.lsu.edu/system/files/RP1%20paper.pdf
[7] K. Conrad, “THE 15-PUZZLE (AND RUBIK’S CUBE).” [Online]. Available: https://kconrad.math.uconn.edu/blurbs/grouptheory/15puzzle.pdf
[8] S. Halevi and S. Micali, “Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing,” Annual International Cryptology Conference, pp. 201–215, 1996.
[9] J. McCranie, “Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).” 2003. [Online]. Available: https://oeis.org/A087725
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔