月か太陽に対する物理的ゼロ知識証明
電気通信大学 助教 宮原大輝

※ 「数独」「カックロ」「スリザーリンク」は株式会社ニコリの商標です
公開用のために、いくつかのパズルを消去しています
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

目次
0. 前回からの更新
1. 研究背景、目的、貢献
2. 準備
3. 提案方式
4. 議論
5. 結論

2

去年の研究集会からの更新• 4つの未解決問題を提示➢数独などに対するZKPプロトコルの進展を2つ紹介

プロトコルの定式化における未解決課題

3

未解決問題（1/4）：数独• Sasakiら[TCS20]、Ruangwises[NGCO22]、田中ら[SCIS23]
によって必要な枚数・シャッフル数が改良された
著者

シャッフル数
2745322

必要なデッキ

Gradwohlら
Sasakiら
Ruangwises

枚数24390120

田中ら

11716

UNO2組

トランプ27組
トランプ9組
トランプ2組• 現実的な時間で実行可能になるためには？
• 他のパズルに対するZKPは効率化できるか？
4

未解決問題（1/4）：数独における進展• SCISなどの国内研究会において4つの研究が発表
著者
Gradwohlら

枚数
243

Sasakiら
Ruangwises
Tanakaら

90
120
117

シャッフル数 必要なデッキ
27
トランプ27組
45
トランプ9組322
トランプ2組
16
UNO2組

佐々木ら
田中ら
小野ら*

243
243
162

32
1

トランプ9組
トランプ9組
トランプ3組*入力の準備に工夫あり• 未解決：入力工夫無しのシャッフル数1回プロトコル5

未解決問題（2/4）：他のペンシルパズル•ZKPプロトコルが構成されていない（ニコリ社の）下線はZKPに関する発表が数字パズルは約25個されていないパズル（宮原調べ）

因子の部屋、ウソワン、お家へ帰ろう、カックロ、キンコンカン、クロット、
黒どこ(黒マスはどこだ)、碁石ひろい、さしがね、さとがえり、サムライン、
四角に切れ、シャカシャカ、縦横さん、推理パズル、数コロ、数独、ストストーン、スラローム、スリザーリンク、ダブルチョコ、チェンブロ、チョコバナナ、月か太陽[HKL+23]、ドッスンフワリ、ドッチループ、流れるループ、ナンスケ、ナンバーリンク、ぬりかべ、ぬりみさき、ぬりめいず、のりのり、波及効果、橋をかけろ、バッグ、美術館、ひとりにしてくれ、フィルオ
ミノ、ふくめん算、へびいちご、へやわけ、ヘルゴルフ、ペンシルズ、マカロ、ましゅ、マックロ、ミッドループ、虫くい算、やじさんかずさん、ヤジリン、よせなべ、LITS•

近年注目を浴びたパズルへのZKPが構成された

数字のパズル一覧：https://www.nikoli.co.jp/ja/puzzles/[HLL+23] S. Hand et al., Check Alternating Patterns: A Physical Zero-Knowledge Proof for Moon-or-Sun, IWSEC 2023

6

目次
1. 研究背景、目的、貢献
2. 準備
3. 提案方式
4. 議論
5. 結論

10

物理暗号・カードベース暗号とは• 日本が発信する特色ある分野➢最大級の暗号シンポジウムで5つセッションが設けられる➢AIセキュリティ・耐量子暗号に次ぐ3番目の多さ• 海外からは、3つの機関から継続的に論文が輩出
最終日に1つ（合同）

終日占拠

8年後

SCIS webサイトより

18

本研究：パズルの物理ゼロ知識証明• Pはパズルの答えを知っているとVに納得させたい

P

V
数独パズル

19

数独を機に研究が広まっている• カード組を用いてゼロ知識証明（ZKP）を実現[SMMS20]• 日本発信の研究で日本のプレゼンス向上に繋げる

初学者
向け教育

導入のきっかけ日本発信[SMMS20] Tatsuya Sasaki, Daiki Miyahara, Takaaki Mizuki, and Hideaki Sone, “Efficient Card-Based Zero-Knowledge Proof for Sudoku,” Theoretical Computer
Science, Elsevier, vol.839, pp.135–142, 202020

研究目的：数字から図形へ• 数字に関するパズルは多く取り組まれている➢数独[GNPR09,SMMS20]、カックロ[BDDL16,MSMS19]、マカロ[BDD+18]など➢カードベース暗号に関する研究をそのまま応用できる• 図形の性質の証明は比較的複雑➢スリザーリンク：1つの輪であること➢ぬりかべ：ひとつながりになっていること（分断禁）ニコリWebサイトより

スリザーリンク[LMM+21]

ぬりかべ[RML+22]

21

貢献：「月か太陽」に対するZKP• 「月か太陽」を扱う（NP完全[II22]）• 比較的複雑なルールを検証➢1つの輪であること（今日の内容）➢部屋ごとに異なる図形を通ること[HLL+23]

ニコリWebサイトより[II22] Chuzo Iwamoto and Tatsuya Ide, Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete, IEICE Trans. Fundamentals, 2022
[HLL+23] S. Hand et al., Check Alternating Patterns: A Physical Zero-Knowledge Proof for Moon-or-Sun, IWSEC 202322

貢献：1つの輪検証の効率化• 「月か太陽」に対するZKPを構成、効率化➢既存方式[LMM+21]の非効率な手順を指摘➢一つながりの検証[RML+22]を応用• 手順（シャッフル回数）を半分にまで削減

スリザーリンク[LMM+21]

ぬりかべ[RML+22][LMM+21] Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Léo Robert, Tatsuya Sasaki, and Hideaki Sone, How to Construct PhysicalZero-Knowledge Proofs for Puzzles with a “Single Loop” Condition, TCS 202123

目次
1. 研究背景、目的、貢献
2. 準備
3. 提案方式
4. 議論
5. 結論

24

カードと値の符号化• 黒と赤の2色カード組を使用

FrontBack25

カードと値の符号化• 黒と赤の2色カード組を使用• 2つのセルの間の線の存在を、2枚のカードで符号化

Front
Back==26

カードと値の符号化• 黒と赤の2色カード組を使用• 2つのセルの間の線の存在を、2枚のカードで符号化

Front
Back==27

スリザーリンクに対する既存ZKP• 基本アイデア：𝑃に解を安全に「作らせる」• セットアップ：盤面サイズのループを表すカードを置く28

スリザーリンクに対する既存ZKP• 基本アイデア：𝑃に解を安全に「作らせる」• セットアップ：盤面サイズのループを表すカードを置く• 作成フェーズ：𝑃にループを安全に「凹ませる」
安全に取り出す
既存技術[KW21]を用いる

29

スリザーリンクに対する既存ZKP• 基本アイデア：𝑃に解を安全に「作らせる」• セットアップ：盤面サイズのループを表すカードを置く• 作成フェーズ：𝑃にループを安全に「凹ませる」➢解を知っている𝑃は一連の手順を繰り返せば良い30

既存ZKPの欠点• 凹み前後に追加検証が必要➢𝑃が選んだ4点の間に線が存在すること（シャッフル2回）

31

既存ZKPの欠点• 新たなループ• 凹み前後に追加検証が必要➢𝑃が選んだ4点の間に線が存在すること（シャッフル2回）• 線の交錯32

既存ZKPの欠点• 凹み前後に追加検証が必要➢𝑃が選んだ4点の間に線が存在すること（シャッフル2回）➢凹ませた後に線が交差していないこと（シャッフル8回）

33

既存ZKPの欠点• 凹み前後に追加検証が必要➢𝑃が選んだ4点の間に線が存在すること（シャッフル2回）➢凹ませた後に線が交差していないこと（シャッフル8回）

34

既存ZKPの欠点

凹ませた先で交錯する可能性• 凹み前後に追加検証が必要➢𝑃が選んだ4点の間に線が存在すること（シャッフル2回）➢凹ませた後に線が交差していないこと（シャッフル8回）

35

目次
1. 研究背景、目的、貢献2. 準備
3. 提案方式
4. 議論
5. 結論

36

[再掲] 貢献：1つの輪検証の効率化• 1つの輪を描くパズルに対するZKPを効率化➢既存方式[LMM+21]の非効率な手順を指摘➢ひとつながりの検証[RML+21]を応用• 手順（シャッフル回数）を半分にまで削減

スリザーリンク[LMM+21]

ぬりかべ[RML+22][LMM+21] Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Léo Robert, Tatsuya Sasaki, and Hideaki Sone, How to Construct PhysicalZero-Knowledge Proofs for Puzzles with a “Single Loop” Condition, TCS 2021

37

アイデア：線を1つずつ描く• 𝑃に線を安全に「描かせる」➢既に描いた線に繋ぐように描く➢追加検証が比較的楽（シャッフル4回）

38

アイデア：線を1つずつ描く• 描く位置によって検証すべき位置が異なる• 描く位置は秘密なので工夫が必要• 𝑃に線を安全に「描かせる」➢既に描いた線に繋ぐように描く➢追加検証が比較的楽（シャッフル4回）

39

提案プロトコル
1. 各ドットの間にを置き、裏返す
2. 𝑃に線を描かせることを繰り返す

40

提案プロトコル
1. 各ドットの間にを置き、裏返す
2. 𝑃に線を描かせることを繰り返す
a.

各四角の上・左辺上に置かれたカードをまとめる

41

提案プロトコル
1. 各ドットの間にを置き、裏返す
2. 𝑃に線を描かせることを繰り返す
a.

各四角の上・左辺上に置かれたカードをまとめる
数が合わないところはダミーを追加

42

提案プロトコル
1. 各ドットの間にを置き、裏返す
2. 𝑃に線を描かせることを繰り返す
a.

各四角の上・左辺上に置かれたカードをまとめる
b. 𝑃は描きたいところに 、それ以外に を裏にして置く43

提案プロトコル
1. 各ドットの間にを置き、裏返す
2. 𝑃に線を描かせることを繰り返す
a.

各四角の上・左辺上に置かれたカードをまとめる
b. 𝑃は描きたいところに 、それ以外に を裏にして置く
c. 5枚から成るカード束を巡回的にシャッフルする44

提案プロトコル
1. 各ドットの間にを置き、裏返す
2. 𝑃に線を描かせることを繰り返す
a.

各四角の上・左辺上に置かれたカードをまとめる
b. 𝑃は描きたいところに 、それ以外に を裏にして置く
c. 5枚から成るカード束を巡回的にシャッフルする45

提案プロトコル
2. 𝑃に線を描かせることを繰り返す
d. 𝑃が置いたカードをめくり、赤が含まれる束を見る46

提案プロトコル
2. 𝑃に線を描かせることを繰り返す
d. 𝑃が置いたカードをめくり、赤が含まれる束を見る47

提案プロトコル
2. 𝑃に線を描かせることを繰り返す
d. 𝑃が置いたカードをめくり、赤が含まれる束を見る
e. 再度𝑃に、どの2つに線を描くのかを選ばせる48

提案プロトコル
2. 𝑃に線を描かせることを繰り返す
d. 𝑃が置いたカードをめくり、赤が含まれる束を見る
e. 再度𝑃に、どの2つに線を描くのかを選ばせる• 検証に必要なカードは上記の通り

49

提案プロトコル 𝑒𝑓𝑑𝛽𝑐

2. 𝑃に線を描かせることを繰り返す
𝛼𝑏ℎd. 𝑃が置いたカードをめくり、赤が含まれる束を見る
𝑔𝑎e. 再度𝑃に、どの2つに線を描くのかを選ばせる

𝛼𝑎𝑏𝑐𝛽𝑑𝑒𝑓or• どちらを描いて検証するかを選ぶ

50

提案プロトコル 𝑒𝑓𝑑𝛽𝑐

2. 𝑃に線を描かせることを繰り返す
𝛼𝑏ℎd. 𝑃が置いたカードをめくり、赤が含まれる束を見る
𝑔𝑎e. 再度𝑃に、どの2つに線を描くのかを選ばせる

or• 左のカード束が安全に選ばれた

51

提案プロトコル 𝑒𝑓𝑑𝛽𝑐

2. 𝑃に線を描かせることを繰り返す
𝛼𝑏ℎd. 𝑃が置いたカードをめくり、赤が含まれる束を見る
𝑔𝑎e. 再度𝑃に、どの2つに線を描くのかを選ばせる

or1. 選ばれたコミットメントをスワップ

52

提案プロトコル 𝑒𝑓𝑑𝛽𝑐

2. 𝑃に線を描かせることを繰り返す
𝛼𝑏ℎd. 𝑃が置いたカードをめくり、赤が含まれる束を見る
𝑔𝑎e. 再度𝑃に、どの2つに線を描くのかを選ばせる

赤黒が1つしかないことを確認（シャッフル2回）
or

1. 選ばれたコミットメントをスワップ
2. 描いた線が先端になることを確認➢

最後は結合されることを確認

53

提案プロトコル• 以上をループが描かれるまで繰り返す➢解を知らない𝑃であっても、必ず1つのループが描かれる➢1つのループが数字ルールも満たす→解を知っている• シャッフル回数は（各繰り返しの中で）6回➢既存方式は12回[LMM+21]

𝑃

V[LMM+21] Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Léo Robert, Tatsuya Sasaki, and Hideaki Sone, How to Construct PhysicalZero-Knowledge Proofs for Puzzles with a “Single Loop” Condition, TCS 2021

54

目次
1. 研究背景、目的、貢献
2. 準備
3. 提案方式
4. 議論
5. 結論

55

議論
• 提案プロトコル中の最大繰り返し数は盤面サイズ➢既存方式と全く一緒の繰り返し数[LMM+21]➢つまりシャッフル回数は半分に効率化• 周長も秘匿する必要あり[LMM+21]➢あり得る解の最大周長分を繰り返す➢先端の線を消す（全く同じ操作）ことも行う

最大周長は点の数と等しい[LMM+21] Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Léo Robert, Tatsuya Sasaki, and Hideaki Sone, How to Construct PhysicalZero-Knowledge Proofs for Puzzles with a “Single Loop” Condition, TCS 2021

56

結論
• 1つの輪を描くパズルに対するZKPを効率化➢既存方式[LMM+21]の非効率な手順を指摘➢ひとつながりの検証[RML+22]を応用• 未解決：重力を安全に証明する➢ストストーンに対するZKPの構築[LMM+21] Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, Léo Robert, Tatsuya Sasaki, and Hideaki Sone, How to Construct PhysicalZero-Knowledge Proofs for Puzzles with a “Single Loop” Condition, TCS 2021

57