Presentation Information
[A-7-09]マカロに対する効率的な天秤ベースゼロ知識証明プロトコル
〇Miyuki Fujii1, Yang Li1, Kazuo Sakiyama1, Daiki Miyahara1 (1. Electro Communications Univ.)
Keywords:
ZKP
物理ゼロ知識証明とは，カード組や天秤など身近な道具を用いるゼロ知識証明プロトコルである．主にNP完全に属するペンシルパズルを対象にプロトコルの設計が進められてきた．今回対象とするペンシルパズル「マカロ」の物理ゼロ知識証明は，カードベースプロトコルや天秤プロトコルですでに設計されているが，リソースや手順数の限界について十分に議論はされていない．マカロを足掛かりとして天秤を用いた物理ゼロ知識証明プロトコルの効率性の限界を示す．