Sumpleteに対する物理的ゼロ知識証明
初貝 恭祐（電気通信大学）

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

1

パズルに対するゼロ知識証明➢ Prover➢ 解答を知っている➢ Verifier

ProverVerifier➢ 解答を知らない➢ 解答を計算できない➢ 目的➢ パズルには解答が存在することをVerifier に納得させる➢ Verifier に解答を教えない解答があると納得

2024/5/22

物理的ゼロ知識証明⇒ 計算機ではなくカードなどを使って行う産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

2Sumplete とは？
➢問題

35

目標値

0 −6−3 1 −2 3 −15 −7 6
942

83 −8 5−6 3 −4 −1 −10➢解答

350 −6−3 1 −2 3 −15 −7 6
942

83 −8 5−6 3 −4 −1 −10
2024/5/22➢ ChatGPTが生成（2023年3月）[1]➢ 問題例：4 × 4 サイズの盤面◼ マス内に整数◼ 各行・列にも整数（目標値）が割り当て➢ 解答：整数を削除するマスの位置＜条件＞
各行・各列について,残ったマスの和 = 目標値[1] P. Penguin: “Chatgpt invented its own puzzle game.”,https:// puzzledpenguin.substack.com/p/chatgptinvented-its-ownpuzzle-game (2023).

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

3

本研究の成果350 −6−3 1 −2 3 −15 −7 694283 −8 5−6 3 −4 −1 −1035① Sumplete の NP 完全性の証明
マスの数字に制限のないSumplete
マスの数字に制限のあるSumplete② Sumplete に対する物理的ゼロ知識証明の提案
実用性に即した手法
定義に即した手法

0 −6−3 1 −2 3 −15 −7 694283 −8 5−6 3 −4 −1 −102024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

4Sumplete の NP 完全性 – 証明方針

➢Sumplete はNP問題

NP完全問題➢ NP 完全問題から Sumplete へ変換

多項式時間で変換可能⇒ Sumplete は変換前の問題と同程度の難しさ
3

50 −6

⇒ Sumplete は NP 完全−3 1 −2 3 −15 −7 6942

83 −8 5−6 3 −4 −1 −102024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

5

部分和問題 ⇒ Sumplete の帰着➢部分和問題➢Sumplete−1 −1 −1 −1−3 1◼問題：𝐴 = −3,1, −2, 3 , 𝑁 = −1
◼解答：Yes (𝐴′ = {1, −2})

1

2024/5/22−2 3−2 3
3−2 3−3 −1−3 1−3 1

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地−1−1−2 −1

6

制限付き Sumplete の NP完全性➢オリジナルの Sumplete：マスの数字は−20 以上 20 以下⇒ マスの数字に制限があってもSumplete はNP完全➢部分和問題から証明できない
制限付き部分和問題はNP完全ではない⇒ 特殊な充足可能性問題から証明

引用：https://sumplete.com

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

7

XSAT for 3-CNF+3 ⇒ 制限付きSumplete の帰着➢XSAT for 3-CNF+3

各 𝑐 に TRUE が 1 個だけ現れる
変数割り当ては存在するか？
各 𝑐 は3変数の論理和
各変数は３回ずつ現れる

𝑐1 = 𝑥1 ∨ 𝑥2 ∨ 𝑥3
𝑐2 = 𝑥2 ∨ 𝑥3 ∨ 𝑥6
𝑐3 = 𝑥1 ∨ 𝑥4 ∨ 𝑥6
𝑐4 = 𝑥2 ∨ 𝑥5 ∨ 𝑥6
𝑐5 = 𝑥1 ∨ 𝑥4 ∨ 𝑥5
𝑐6 = 𝑥3 ∨ 𝑥4 ∨ 𝑥5
2024/5/22➢制限付きSumplete1 ≤ 𝑖 ≤ 6行目：𝑗 列目＝ቊ
7行目：全て 3

1 (𝑥𝑗 in 𝑐𝑖 )
3 𝑜/𝑤

3

3

3333

1

1

133

3

13

1

1331113313

1

13

133

1

11133113

1331113133333312

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

8

XSAT for 3-CNF+3 と (1,3)-Sumplete の解答の対応➢XSAT for 3-CNF+3➢制限付きSumplete各 𝑐 に TRUE が 1 個だけ現れる
変数割り当ては存在するか？
各 𝑐 は3変数の論理和
各変数は３回ずつ現れる

𝑐1 = 𝑥1 ∨ 𝑥2 ∨ 𝑥3
𝑐2 = 𝑥2 ∨ 𝑥3 ∨ 𝑥6
𝑐3 = 𝑥1 ∨ 𝑥4 ∨ 𝑥6
𝑐4 = 𝑥2 ∨ 𝑥5 ∨ 𝑥6
𝑐5 = 𝑥1 ∨ 𝑥4 ∨ 𝑥5
𝑐6 = 𝑥3 ∨ 𝑥4 ∨ 𝑥5

2024/5/22

 1 ≤ 𝑖 ≤ 6行目：𝑗 列目＝൝残す (𝑥𝑗 = TRUE)

削除
𝑜/𝑤
残す (𝑥𝑗 = FALSE) 7行目：𝑗 列目＝൝削除𝑜/𝑤

3333331113331𝑥2 = TRUE

3113311𝑥3 = FALSE

1331311𝑥4 = TRUE

3133111𝑥5 = FALSE

1331131𝑥6 = FALSE

331113133333312𝑥1 = FALSE

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

9パズルに対するゼロ知識証明➢ Prover➢ 解答を知っている➢ Verifier

ProverVerifier➢ 解答を知らない➢ 解答を計算できない➢ 目的➢ パズルには解答が存在することをVerifier に納得させる➢ Verifier に解答を教えない解答があると納得

2024/5/22

物理的ゼロ知識証明⇒ 計算機ではなくカードなどを使って行う産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

10パズルに対するゼロ知識証明 – 完全性：解答あり

ProverVerifier

解答を知っている受理

2024/5/22

完全性 ( 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝑛𝑒𝑠𝑠 )Prover は解答を知っている⇒ Verifier は必ず受理

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

11パズルに対するゼロ知識証明 – 健全性
健全性 ( 𝑠𝑜𝑢𝑛𝑑𝑛𝑒𝑠𝑠 )：解答なし

ProverVerifier

Prover は解答を知らない⇒ Verifier は無視できない確率で拒否➢ Prover が解答を知らないにもかかわらずVerifier が受理する確率(健全性誤り確率)を 𝑝 として，0≤𝑝<1であれば，繰り返し実行することで全体の健全性誤り確率は 0 に近づく．
解答を知らない2024/5/22

拒否➢ 物理的ゼロ知識証明：人の手で行う→ 人の手で繰り返し行うのは非効率的であるから
𝑝 = 0 が望ましい

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

12パズルに対するゼロ知識証明 – ゼロ知識性：解答あり

ProverVerifier

ゼロ知識性 ( 𝑧𝑒𝑟𝑜-𝑘𝑛𝑜𝑤𝑙𝑒𝑑𝑔𝑒 )Verifier は, 解答があること以上の知識を得られない.

解答を知っている

2024/5/22

解答があると納得
しかし解答は分からない
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

13Sumplete のゼロ知識証明➢問題 35➢解答

0 −63

50 −6−3 1 −2 3 −1−3 1 −2 3 −15 −7 65 −7 6942

83 −8 5

9−6 3 −4 −1 −1042

83 −8 5−6 3 −4 −1 −10

目的ProverVerifier
対話・Prover は Verifier に，次を納得させる「各行・各列について，残ったマスの和＝目標値を満たすようなマスの消し方がある」
・Verifier に，削除するマスの位置は教えない

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

14Sumplete のゼロ知識証明➢問題 35➢解答0 −6350 −6−3 1 −2 3 −1−3 1 −2 3 −15 −7 65 −7 6942

83 −8 5

9−6 3 −4 −1 −1042

83 −8 5−6 3 −4 −1 −10

目的ProverVerifier
対話・Prover は Verifier に，次を納得させる「各行・各列について，残ったマスの和＝目標値を満たすようなマスの消し方がある」
・Verifier に，削除するマスの位置は教えない

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

15

ゼロ知識性を考えない証明
350 −6−3 1 −2 3 −15 −7 694283 −8 5−6 3 −4 −1 −10➢任意の行・列で，次を検証◼ 残すマスの和を計算◼ 目標値と比較➢残すか削除するかを教えずに，−1102024/5/22

残すマスだけを加算したい

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

16

解答を秘匿するアイディア
350 −6➢解答（削除するマス）を隠すために−3 1 −2 3 −1
5 −7 6942① カウンターの切り替え：削除マスはダミーに加算◼ どちらのカウンターに加算するかは秘密にする

8② 値を隠して加算：最後に本物だけ公開

3 −8 5−6 3 −4 −1 −10

本物+1−22024/5/22➢このギミックを2種類のカードで実現する

ダミー−10? +3−30?

表面：♥ or ♠

裏面：?

（同じ柄）

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

17

ゼロ知識証明プロトコルの流れ➢すべての行/列で検証
35a.

0 −6削除マス ⇒ ダミーカウンターに加算−3 1 −2 3 −15 −7 694283 −8 5−6 3 −4 −1 −10残すマス ⇒ 本物カウンターに加算b.

?

本物カウンター = 目標値

課題①カウンターの作り方◼ 値を隠したまま加算②カウンターの切り替え方◼ どのマスを削除するかは隠す

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

18カウンターの作り方➢注目する行：マスの和の最小値が −5 ，最大値が 435➢カウンター： | − 5| + 1 + 4 = 10 枚 のカード列

0 −6−3 1 −2 3 −15 −7 6942

83 −8 5−6 3 −4 −1 −10➢ハートが左から 𝑖 番目：カウンターの値は 𝑖 − 5 − 1−5−4 −3−2−101234♠ ♠ ♠ ♠ ♠ ♥ ♠ ♠ ♠ ♠➢ 既存のアイディアを拡張 [MHMS20][MHMS20] D. Miyahara, Y. Hayashi, T. Mizuki and H. Sone, “Practical Card-based
Implementations of Yao’s Millonaire Protocol” Theor. Comput. Sci., (2020).

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

19カウンターへの加算➢加算＝カード列のシフト操作→ カードが裏向き（値が秘密）でも実行可能➢負数 / 正数の加算：左 / 右にシフト例）3 を加算−5−4 −3−2−1𝟎1234♠ ♠ ♠ ♠ ♠ ♥ ♠ ♠ ♠ ♠右に3枚シフト−5−4 −3−2−1012𝟑4♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♥ ♠2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

20カウンターの切り替え方 – 下準備➢目的：残す/削除する マスは，本物/ダミー カウンターに加算◼ 今注目しているマスが残すかどうかは識別できないようにする

3

50 −6??

??

??

?? −1??

??

??

??

8??

??

??

??

5??

??

??

?? −10

下準備：（削除するマスを知っている）Prover は，各マスの上にカード組を裏向きに配置

残すマス： ♥ ♠削除マス： ♠ ♥2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

21カウンターの切り替え方 – カウンターの配置
注目マスに配置されたカード組：?

?

♥? ＋

本物カウンター＋?

① マスからカード組を取り出し，封入◼ 注目マスが残すマス⇒ ♥ の右は本物カウンター◼ 注目マスが削除するマス♠? ＋2024/5/22

ダミーカウンター＋⇒ ♥ の右はダミーカウンター?

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

22カウンターの切り替え方 – カウンターへ加算② 封筒をシャッフルし，開封◼ 左端のカードを表向きにし，♥ の隣のカウンターに裏向きのまま加算操作♠＋カウンター＋?

◼注目マスが残すマス⇒ ♥ の右は本物カウンター♥ ＋ カウンター
加算＋◼注目マスが削除するマス?

⇒ ♥ の右はダミーカウンター◼ シャッフルによって，残すマスか削除するマスかは識別できない
2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

23カウンターの切り替え方 – カード組の復元♥? ＋

本物カウンター＋?
♠? ＋

ダミーカウンター＋?

③ カードをすべて裏向きにし，封筒へ戻す④ 封筒をシャッフルし，開封◼ 右端のカードをもとにマスへカード組を戻す

注目マスに配置されたカード組：

2024/5/22?

?

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

24提案プロトコルの流れ
1. すべてのマスにカード組を配置
2. すべての行/列で検証
350 −6−3 1 −2 3 −15 −7 6942a.

カウンター作成b.

残すマス ⇒ 本物カウンターに加算
削除マス ⇒ ダミーカウンターに加算

83 −8 5c.

?

本物カウンター = 目標値−6 3 −4 −1 −10

ギミックによって，解答（削除するマスの位置）は秘匿

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

25

提案プロトコルの健全性
健全性 ( 𝑠𝑜𝑢𝑛𝑑𝑛𝑒𝑠𝑠 )健全性誤り確率は 0（Prover は解答を知らない ⇒ Verifier は必ず拒否）

対偶「Verifier が証明を受理 ⇒ Prover は解答を知っている」を示す
Verifier が証明を受理⇒ 任意の行/列について，Prover が ♥ ♠ を配置したマスの和＝目標値⇒♠ ♥ を配置したマスを削除すれば解答が得られる⇒ Prover は解答を知っている
2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

26

提案プロトコルのカード枚数➢1マスにつき2枚⇒ 2𝑚𝑛 枚➢カウンターの切り替え⇒2枚➢カウンター作成⇒ 2𝑘 枚

2𝑚𝑛 + 2𝑘 + 2= 2𝑚𝑛 + 2 ⋅ 2log2𝑘 + 2 枚目標値 𝑘 を表現
2個作成➢カード枚数が目標値 𝑘 のビット長の指数関数になってしまう！

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

27

カウンターの様式変更➢カウンターに2の補数表現を用いる
2(10) = 0010(2) = ♠ ♥♠♥ ♥♠ ♠♥

−5(10) = 1010(2) = ♥ ♠♠♥ ♥♠ ♠♥

➢カウンターの値を秘匿したまま加算：ANDプロトコルとXORプロトコルで実行可能 [NHMS15][NHMS15] T. Nishida, Y. Hayashi, T. Mizuki and H. Sone, “Card-Based Protocols for Any
Boolean Function” Theory and Applications of Models of Computation, (2015).
2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

28

２の補数を用いるプロトコルの流れ? ?

残す or 削除? ⋯ ?

補数表現

350 −6−3 1 −2 3 −15 −7 6

942

83 −8 5

1. すべてのマスにカード組を配置
2. マスの値を2の補数で表現
3. すべての行/列で検証
a.

カウンター作成b.

残すマス ⇒ 本物カウンターに加算
削除マス ⇒ ダミーカウンターに加算?

c. 本物カウンター = 目標値−6 3 −4 −1 −10

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

29

２の補数を用いた場合のカード枚数⇒ 𝑚𝑛(2log 2 𝑘 + 2) 枚

➢1マスに配置するカード

残す / 削除の指示ペア：２枚
マスの数字を2の補数で表現：2 log 2 𝑘 枚➢カウンターの切り替え⇒2枚➢カウンター作成⇒ 2 × 2log 2 𝑘 枚目標値 𝑘 を表現
2個作成

2024/5/22

𝑚𝑛 2log 2 𝑘 + 2+4log 2 𝑘 + 2 枚

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

30プロトコルの比較
カード枚数

シャッフル回数

シフト回数

整数コミットメントを用いる手法

2𝑚𝑛 + 2 ⋅ 2log2 𝑘 + 24𝑚𝑛𝑚𝑛2の補数表現を用いる
手法

𝑚𝑛 2log 2 𝑘 + 2 + 4 ⋅ log 2 𝑘 + 22𝑚𝑛 + 7𝑚𝑛 ⋅ log 2 𝑘0

➢人の手で行う場合：整数コミットメントの手法が適切
シフト操作による加算が分かりやすく，実行が簡単大きな数字を取り扱うことは少ない➢定義を遵守する場合：補数表現を用いる手法が適切（理論上）実現可能なカード枚数

2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

31

まとめ
46 -30 36 10 -29 -8① Sumplete のNP完全性の証明◼ 部分和問題からの変換◼ XSAT for 3-CNF+3 からの変換② Sumplete に対する物理的ゼロ知識証明の提案◼ ダミーカウンターを利用して解答を秘匿

38-3

53

37 18 -35

7-815 -30 31 25 -32 27 83

32-15 -18 15 39 11 -15

29 11 16 -24 -38 -7 -33 -618-23 34 29

1337815 76

830-4-1 -15 21-7 -37

00-14 -16

31 -38 -20

622 -22 39 30 -31 -7-26 -611 39-25 -20 38 33 -27 -18-28

94-5-11 17 21-34 17 40-10 17 -12 -1 -24 32 -13 -5 -26 -43
2024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

32

付録➢解答46 -30 36 10 -29 -838-353

37 18 -35

7-815 -30 31 25 -32 27 83

32-15 -18 15 39 11 -15

29 11 16 -24 -38 -7 -33 -6

18-23 34 29

1337815 76

830-4-1 -15 21-7 -3700-14 -16

31 -38 -20

622 -22 39 30 -31 -7-26 -6

11 39-25 -20 38 33 -27 -18-28

94-5-11 17 21-34 17 40-10 17 -12 -1 -24 32 -13 -5 -26 -432024/5/22

産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

33