昨年の研究集会からのアップデート
水木 敬明
東北大学サイバーサイエンスセンター
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地｜2024a035
九州大学 伊都キャンパス ウエスト1号館 D棟 4階 IMIオーディトリアム（W1-D-413）
5月22日（水）【公開】10:00-17:45

1

昨年度
主催：九州大学マス・フォア・インダストリ研究所
種別・種目：一般研究-短期共同研究
研究計画題目：産学連携によるカードベース暗号の数理的未解決問題と新課題の整理
研究代表者：水木 敬明（東北大学）

組織委員

須賀 祐治（株式会社インターネット
イニシアティブ）縫田 光司（九州大学）
品川 和雅（茨城大学）

2

カードベース暗号は、物理的なカード組を用いて秘密計算
やゼロ知識証明等の暗号機能を実現する技術である。その特徴は、カードを並べることによりプロトコルを視覚的・体験的に実行できることであり、暗号技術に関する教育的効果が期待されていることに加えて、非専門家が日常生
活において利用できる実用的な暗号技術であるといえる。

3

昨年度
カードベース暗号は1990年代に萌芽的研究が提案されたが、2010年代に本研究代表者らのグループが計算モデル
を抽象機械によって数理的に定式化したことを皮切りに、複数の研究グループが活発に論文成果を発表するようになり、特にここ数年論文数が急増している。また同分野の近年の研究には、有限群論、アソシエーションスキーム、
形式検証系などの数理科学的な題材との関連についての新しい研究テーマも現れてきており、研究分野として急成長を遂げる転換点にあると考えられる。このようにカード
ベース暗号分野が急速に拡大する状況において、この分
野の未解決問題を把握すること自体のコストが高くなっており、新規参入のハードルは年々上がっている。

4

昨年度
カードベース暗号分野のScopus掲載論文数の推移

5

昨年度
本共同研究では、さらなる分野の発展のため、新規に参入する研究者の増加を目標とし、この分野を先導する産業界と学術界の研究者が集中的に議論し、潜在的な研究者の参入のガイドになるような、未解決問題や新課題の整理を行う。そして、得られた整理の結果を未解決問題リストのような形で公表することにより、新規参入研究者の増大に資
する。

6

昨年度

組織委員（講演者）
水木 敬明（東北大学 サイバーサイエンスセンター）
須賀 祐治（株式会社インターネットイニシアティブ）
縫田 光司（九州大学マス・フォア・インダストリ研究所）
品川 和雅（茨城大学 理工学研究科）
講演者
真鍋 義文（工学院大学 情報学部情報科学科）
宮原 大輝（電気通信大学 情報理工学研究科）
中井 雄士（豊橋技術科学大学）

7

昨年度
10:00-11:30 オープニング、セッション１ （座長：縫田 光司）
水木 敬明（東北大学 サイバーサイエンスセンター）
ANDプロトコルにまつわる未解決問題
標準モデル等

宮原 大輝（電気通信大学 情報理工学研究科）
カードベースZKPプロトコル

13:00-14:30 セッション２ （座長：品川 和雅）
中井 雄士（豊橋技術科学大学）
秘匿置換を用いたカードベース暗号
真鍋 義文（工学院大学 情報学部情報科学科）
無開示性を持つカードベース暗号プロトコルについて

秘匿置換
モデル

8

昨年度

15:00-17:15 セッション３、クロージング （座長：水木 敬明）

品川 和雅（茨城大学 理工学研究科）
カードベース暗号に登場するさまざまなカード組と符号化
須賀 祐治（株式会社インターネットイニシアティブ）
デッキ分割法とアソシエーションスキーム

カード組
と符号化

数学との
かかわり

縫田 光司（九州大学マス・フォア・インダストリ研究所）
カードベース暗号に現れる数学

9水木 敬明（東北大学 サイバーサイエンスセンター）
ANDプロトコルにまつわる未解決問題 ←このあとアップデートを
宮原 大輝（電気通信大学 情報理工学研究科）
カードベースZKPプロトコル ←セッション２で
中井 雄士（豊橋技術科学大学）
秘匿置換を用いたカードベース暗号★
真鍋 義文（工学院大学 情報学部情報科学科）
無開示性を持つカードベース暗号プロトコルについて★

★未解決問題はフレッシュ

品川 和雅（茨城大学 理工学研究科）
カードベース暗号に登場するさまざまなカード組と符号化★
須賀 祐治（株式会社インターネットイニシアティブ）
デッキ分割法とアソシエーションスキーム ←セッション３で

縫田 光司（九州大学マス・フォア・インダストリ研究所）
カードベース暗号に現れる数学★
10中井 雄士（豊橋技術科学大学）
秘匿置換を用いたカードベース暗号★
真鍋 義文（工学院大学 情報学部情報科学科）
無開示性を持つカードベース暗号プロトコルについて★
品川 和雅（茨城大学 理工学研究科）
カードベース暗号に登場するさまざまなカード組と符号化★

縫田 光司（九州大学マス・フォア・インダストリ研究所）
カードベース暗号に現れる数学★

スライドと動画は昨年度のページでご覧ください：https://joint.imi.kyushu-u.ac.jp/post-9009/

11

水木 敬明（東北大学 サイバーサイエンスセンター）
ANDプロトコルにまつわる未解決問題 ←このあとアップデートを
宮原 大輝（電気通信大学 情報理工学研究科）
カードベースZKPプロトコル ←セッション２で須賀 祐治（株式会社インターネットイニシアティブ）
デッキ分割法とアソシエーションスキーム ←セッション３で12

以降も、昨年度のスライドです
未解決問題はフレッシュなままです

ANDプロトコルにまつわる未解決問題• 2色カード組、1ビット2枚符号化• 標準モデル（パブリックモデル、シャッフルモデル） [MS14]• 2入力や多入力のANDを秘密計算するプロトコル• コミット型、非コミット型※ ANDを扱う理由：(i) ANDができるとORもできる、(ii) XORは容易[MS14] Takaaki Mizuki and Hiroki Shizuya. A formalization of card-based cryptographic protocols via abstract machine. Int. J.
Inf. Secur., 13(1):15–23, 2014.

13

目次
1.

導入

2.

非コミット型2入力ANDプロトコル

3.

コミット型2入力ANDプロトコル

4.

多入力ANDプロトコル

5.

汎用的なプロトコル

142色カード組

表

ひっくり返す？ ？ ？ ？ ？

裏

符号化

=0

=1
15

=0

=1

符号化に従う裏に置かれたカードをコミットメントと呼ぶ：？ ？

x = 0 のとき
？ ？

xx = 1 のとき
？ ？
16

コミット型（2入力）ANDプロトコル
？？ ？？
a

…

…

b

=0

=1

？？
a∧b

例：Mizuki-Sone ANDプロトコル [MS09]

出力がコミットメント

非コミット型（2入力） ANDプロトコル
？？ ？？
a

…

…

a∧b

そうでは
ない

b
例：Five-Card Trick [DB90][DB90] Bert Den Boer. More efficient match-making and satisfiability the five card trick. Advances in Cryptology—
EUROCRYPT ’89, volume 434 of LNCS, pages 208–217, Berlin, Heidelberg, 1990. Springer.
[MS09] Takaaki Mizuki and Hideaki Sone. Six-card secure AND and four-card secure XOR. Frontiers in Algorithmics, volume5598 of LNCS, pages 358–369, Berlin, Heidelberg, 2009. Springer.

17非コミット型ANDプロトコルの例：Five-Card Trick [DB90]
1. 5枚のカードを次のように置く:

=0

？？ ？？

=1

a
b
2. 真ん中のカードを裏にして，ランダムカットを適用する:
？？？？？

？？？？？

？？？？？

3. 5枚すべてのカードを表にする:

a∧b = 1a∧b = 018

コミット型ANDプロトコルの例： Mizuki-Sone AND [MS09]
1. 初期配置:

？？

？？

a

b

？？ ？？ ？？
a2. 並べ替え:？？？？？？
？？？？？？

0

=0

=1

b
4. 並べ替え:？？？？？？
？？？？？？

3. ランダム二等分割カット:

5. 左端の二枚をめくる:[ ？？？ ？？？ ]？？？？ or
a∧b

？？？？
a∧b
19

標準モデルにおけるプロトコル• プロトコルは抽象機械によって定式化されている[MS14]• 簡単に言うと、次の3つの動作の組み合わせ– turn, 𝑇 : 𝑇 に含まれる番目のカードをめくる– perm, 𝜋 : 置換𝜋 の並べ替え– shuf, Π, ℱ : 分布ℱ に従って, 置換 𝜋 ∈ Π を適用（一様のとき分布の記述は省略）

20

Mizuki-Sone ANDプロトコルの疑似コード(turn, {3, 4})(perm, (2 4 3))(shuf, {id, (1 4)(2 5)(3 6)})
(perm, (2 3 4))(turn, {1, 2})if ♡ appears then(result, (3, 4))
else(result, (5, 6))21

シャッフルの性質
shuf, Π, ℱ : 分布ℱ に従って, 置換 𝜋 ∈ Π を適用➢ℱが一様分布のとき、そのシャッフルは一様と言う➢ Πが閉じている（部分群になっている）とき、そのシャッフルは閉じていると言う• ランダムカットやランダム二等分割カットは、どちらも一様で閉じているシャッフルである• 一般に、一様で閉じているシャッフルは、人間が実装しやすいと考えられている
22

目次
1.

導入

2.

非コミット型2入力ANDプロトコル

3.

コミット型2入力ANDプロトコル

4.

多入力ANDプロトコル

5.

汎用的なプロトコル

23✓ Den Boer の Five-Card Trick [DB90]は, 5 枚の非コミット型ANDプロトコル：
？？ ？？
a

b

a∧b = 1a∧b = 0✓ 4 枚の非コミット型ANDプロトコル [MKS12]：

？？？？
a

b

？ ？

？ ？

？？

？？

a∧b = 1a∧b = 0

[MKS12] Takaaki Mizuki, Michihito Kumamoto, and Hideaki Sone. The five-card trick can be done with four cards.
Advances in Cryptology—ASIACRYPT 2012, volume 7658 of LNCS, pages 598–606, Berlin, Heidelberg, 2012. Springer

24

Mizuki-Kumamoto-Sone AND プロトコル[MKS12]=0=1

1. コミットメントを置き，ランダム二等分割カットを適用する：？？ ？？

[ ？？ ？？ ]

？？？？

a
b
2. 中央の二枚に普通のシャッフルを適用する：？？？？

？ ？？ ？

？？？？

3. 2枚目をめくり，(1) 黒なら4枚目，(2) 赤なら1枚目をめくる：(1) ？ ？？

？ ？

またはa∧b = 1
(2) ？ ？？

？？
a∧b = 1？ ？
a∧b = 0または？？
a∧b = 025

非コミット型ANDプロトコルのまとめ
？ ？

？ ？

a

b

a∧b = ?

枚数等
Den Boer5[DB09]
MizukiKumamotoSone[MKS12]

4

シャッフル回数1
2
26

非コミット型2入力ANDプロトコルの現在地• 知られているものは、Five-Card TrickとMizukiKumamoto-Soneプロトコルの2つだけ• （このモデルにおいて）4枚というカード枚数は最小であり、これ以上減らせない• 出力フォーマットやシャッフルについては検討の余地がありそう27

Mizuki-Kumamoto-Soneプロトコルの2つのシャッフル[ ？？ ？？ ]？ ？？ ？

(shuf, {id, (1 3)(2 4)})
(shuf, {id, (2 3)})

どちらも一様で閉じている

これらは1つのシャッフルに結合できる：(shuf, {id, (1 3)(2 4),(2 3),(1 3 4 2)})
しかし、この置換の集合は閉じていない（部分群になっていない）【課題】
一様で閉じているシャッフル1つで4枚非コミット型
ＡＮＤプロトコルは構成できるか？
28

目次
1.

導入

2.

非コミット型2入力ANDプロトコル

3.

コミット型2入力ANDプロトコル

4.

多入力ANDプロトコル

5.

汎用的なプロトコル

29

コミット型ANDプロトコルの歴史（2009年まで）：
？？ ？？
a

…

…

b

？？
a∧b

枚数等

ランダム
カット

二等分割 シャッフル
カット
回数

Crépeau-Kilian[CR94]

10

8

Niemi-Renvall[NR98]

12

7.5

Stiglic[Sti01]

8

2

Mizuki-Sone[MS09]

6

1
30
30

枚数等

ランダム
カット

二等分割 シャッフル
カット
回数

Crépeau-Kilian[CR94]

10

8

Niemi-Renvall[NR98]

12

7.5

Stiglic[Sti01]

8

2

Mizuki-Sone[MS09]

6

1[CK94] Claude Crépeau and Joe Kilian. Discreet solitary games. Advances in Cryptology—CRYPTO’ 93, volume 773 of
LNCS, pages 319–330, Berlin, Heidelberg, 1994. Springer[NR98] Valtteri Niemi and Ari Renvall. Secure multiparty computations without computers. Theor. Comput. Sci., 191(1–2):173–183, 1998.
[Sti01] Anton Stiglic. Computations with a deck of cards. Theor. Comput. Sci., 259(1–2):671–678, 2001.

31
31

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

finiteuniform

closed

6枚より減らせるか？
32shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5finiteuniform

closed[KWH15] Alexander Koch, Stefan Walzer, and Kevin H ̈artel. Card-based cryptographic protocols
using a minimal number of cards. Advances in Cryptology—ASIACRYPT 2015, volume 9452 of
LNCS, pages 783–807, Berlin, Heidelberg, 2015. Springer.

33

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5

有限でない

finiteuniform

closed

一様でない[KWH15] Alexander Koch, Stefan Walzer, and Kevin H ̈artel. Card-based cryptographic protocols
using a minimal number of cards. Advances in Cryptology—ASIACRYPT 2015, volume 9452 of
LNCS, pages 783–807, Berlin, Heidelberg, 2015. Springer.

34

(shuf, {id, (1 3)(2 4)})
(shuf, {id, (2 3)})(turn, {2})if visible seq. = (?, , ?, ?) then(turn, {2})(shuf, {id, (1 3)})1 (shuf, {id, (1 2)(3 4)}, id→1/3, (1 2)(3 4)→2/3)(turn, {4})if visible seq. = (?, ?, ?, ) then(result, 1, 2)
else if visible seq. = (?, ?, ?, ♡) then(turn, {4})else if visible seq. = (?, ♡, ?, ?) then(shuf, {id, (1 3)})(turn, {2})(perm, (1 3 4 2))(shuf, {id, (3 4)})
goto 22 (shuf, {id, (1 3)(2 4)}, id→1/3, (1 3)(2 4)→2/3)(turn, {1})if visible seq. = (♡, ?, ?, ?) then(result, 2, 4)
else if visible seq. = ( , ?, ?, ?) then(turn, {1})(shuf, {id, (3 4)})
(perm, (1 2 4 3))
goto 135

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5finiteuniform

closed閉じていない(shuf, {id, (5 4 3 2 1)}, id→2/3, (5 4 3 2 1)→1/3)
36

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5finiteuniform

closed一様かつ閉じるようにできないか？

37

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5

Abe et al. [AHMS18]

5

finiteuniform

closeduniform closed＆5枚で実現[AHMS18] Yuta Abe, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Five-card AND protocol in committed
format using only practical shuffles. In 5th ACM on ASIA Public-Key Cryptography Workshop, APKC ’18, pages
3–8, New York, 2018. ACM

38

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5

Abe et al. [AHMS18]

5

Koch [Koc22]
Ruangwises, Itoh [RI19]

4

finiteuniform

closed5Koch et al., [KWH15]のをベースに，uniformへ[Koc22] Alexander Koch. The landscape of optimal card-based protocols. Mathematical Cryptology, 1(2):115–131, 2022
[RI19] Suthee Ruangwises and Toshiya Itoh. AND protocols using only uniform shuffles. Computer Science–Theory andApplications, volume 11532 of LNCS, pages 349–358, Cham, 2019. Springer.

39

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5

Abe et al. [AHMS18]

5

Koch [Koc22]
Ruangwises, Itoh [RI19]

4

finiteuniform

closed5

次ページで、下界と最適なプロトコルを示す
40

※ハッセ図をこのように使う初出は文献 [KKW+17]

プロトコル：[Koc22] [RI19]

プロトコル：[MS09]{有限, 閉, 一様}: 6枚

下界：[KKW+17]{有限, 閉}: 6枚プロトコル：[AHMS18]{有限, 一様}: 5枚{閉, 一様}: 5枚

下界：[Koc22]{有限}: 5枚{閉}: 4枚{一様}: 4枚プロトコル：[Koc22] [RI19]

下界：[KWH15]{}: 4枚プロトコル：[KWH15][KKW+17] Julia Kastner, Alexander Koch, Stefan Walzer, Daiki Miyahara, Yu-ichi Hayashi, Takaaki Mizuki, andHideaki Sone. The minimum number of cards in practical card-based protocols. Advances in Cryptology—
ASIACRYPT 2017, volume 10626 of LNCS, pages 126–155, Cham, 2017. Springer.

41

コミット型2入力ANDプロトコルの現在地• 許されるシャッフルを「有限」「一様」「閉じている」の三つで条件を作り、各条件に対して、カード枚数が最小という意
味で計算限界は解明されている• しかし、シャッフルの回数や種類を考慮して条件を作ると、まだまだ計算限界は解明されていない（最適なプロトコルは見つかっていない）

42

shuffleProtocols# of cards

Niem-Renvall [NR98]

12

Stiglic [Sti01]

8

Mizuki-Sone [MS09]

6

Koch et al. [KWH15]

4

Koch et al. [KWH15]

5

Abe et al. [AHMS18]

5

Koch [Koc22]
Ruangwises, Itoh [RI19]

4

finiteuniform

closed5

ランダムカットとランダム二等分割カット
を計7回（期待値）使う
43

shuffleProtocols
Abe et al. [AHMS18]# of cards

finiteuniform

closed5

ランダムカットとランダム二等分割カット
を計7回（期待値）使う
その後、7回から4.5回に改良されている[AHMS21]。

【未解決問題】
一様で閉じているシャッフルに限定し、4.5より少ない回数（期待値）のシャッフルで5枚コミット型ＡＮＤプロトコルは構成できるか？
[AHMS21] Yuta Abe, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Five-card AND computations in committed format
using only uniform cyclic shuffles. New Gener. Comput., 39(1):97–114, 2021.

44

シャッフルをランダムカットのみに限定すると、以上のものに加え、2回のランダムカットで6枚コミット型ANDプ
ロトコルを構成できることが2021年に示されている[AMS21] 。
下界：[KKW+17]{有限, 閉}: 6枚[AMS21] Yuta Abe, Takaaki Mizuki, and Hideaki Sone, Committed-format AND Protocol Using Only Random Cut, Natural
Computing, Springer, vol.20, no.4, pp.639-645, 2021.

45

枚数等
Crépeau-Kilian[CR94]

10

Niemi-Renvall[NR98]

12

ランダム
カット

シャッフル
回数

8
有限でない

7.5
有限でない

Stiglic[Sti01]8

Abe et. al[AMS21]

6

2
有限

2
有限

す
べ
て
ラ
ン
ダ
ム
カ
ッ
ト
し
か
使
わ
な
い

【未解決問題】
シャッフルはランダムカットしか使えないという条件のもと、5枚コミット型ＡＮＤプロトコルは構成できるか？（有限ではない）
46

目次
1.

導入

2.

非コミット型2入力ANDプロトコル

3.

コミット型2入力ANDプロトコル

4.

多入力ANDプロトコル

5.

汎用的なプロトコル

47

多入力ANDプロトコル

𝑥2

⋯

𝑥1

? ?

⋯

? ? ? ?

𝑥1 ∧ 𝑥2 ∧ ⋯ ∧ 𝑥𝑛

𝑥𝑛

追加カード何枚？

シャッフル何回？

48
48

多入力ANDプロトコル
𝑥2

⋯

𝑥1

? ?

⋯

? ? ? ?

𝑥1 ∧ 𝑥2 ∧ ⋯ ∧ 𝑥𝑛

𝑥𝑛

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）• 追加カード1枚 → シャッフル 𝑛 − 1 回（非コミット型）• 追加カードなし →◼ 𝑛 = 3 のとき、シャッフル 5 回（非コミット型）◼ 𝑛 ≥ 4 のとき、シャッフル 𝑛 + 1 回（非コミット型）[Miz16] Takaaki Mizuki. Card-based protocols for securely computing the conjunction of multiple variables.
Theor. Comput. Sci., 622(C):34–44, 2016.

49
49

多入力ANDプロトコル
𝑥2

⋯

𝑥1

? ?

⋯

? ? ? ?

𝑥1 ∧ 𝑥2 ∧ ⋯ ∧ 𝑥𝑛

𝑥𝑛

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）• 追加カード1枚 → シャッフル 𝑛 − 1 回（非コミット型）• 追加カードなし →◼ 𝑛 = 3 のとき、シャッフル 5 回（非コミット型）◼ 𝑛 ≥ 4 のとき、シャッフル 𝑛 + 1 回（非コミット型）[Miz16] Takaaki Mizuki. Card-based protocols for securely computing the conjunction of multiple variables.
Theor. Comput. Sci., 622(C):34–44, 2016.

50
50

2016年に与えられた上界[Miz16]：• 追加カードなし →◼ 𝑛 = 3 のとき、シャッフル 5 回（非コミット型）

シャッフル回数[回]◼ 𝑛 ≥ 4 のとき、シャッフル 𝑛 + 1 回（非コミット型）
9
8
7
6
5
4
3
2
1
0

Mizuki [Miz16]

Mizuki-Kumamoto-Sone [MKS12]

1

2

3

4
5
入力の数（n入力）

6

7

8
51
51

シャッフル回数[回]追加カードなしの2回シャッフルの3入力AND [ITS+21] ：

9
8
7
6
5
4
3
2
1
0

Mizuki [Miz16]

Isuzugawa et. al [ITS+21]

Mizuki-Kumamoto-Sone [MKS12]

1

2

3

4
5
入力の数（n入力）

6

7

8[ITS+21] Raimu Isuzugawa, Kodai Toyoda, Yu Sasaki, Daiki Miyahara, and Takaaki Mizuki. A card-minimal three-input AND
protocol using two shuffles. Computing and Combinatorics, volume 13025 of LNCS, pages 668–679, Cham, 2021. Springer.

52
52

6入力以上の場合の改善 [CSS2021] ：10
9シャッフル回数[回]8
7

CSS20216
5
43

Isuzugawa et. al [ITS+21]

2
1

Mizuki-Kumamoto-Sone [MKS12]

0
1

2

3

4

5

6

7

8
・・・

[CSS2021] 五十鈴川頼宗，宮原大輝，水木敬明，「最小枚数の非コミット型６入力ANDプロトコルのシャッフル回数の改善」 ，コン
ピュータセキュリティシンポジウム (CSS 2021)，2021.

53
53

追加カードなし非コミット型n入力ANDプロトコルの現在地• 一様で閉じているシャッフルのみを使った、追加カードなし
非コミット型n入力ANDプロトコルは存在する• しかしながら、最小のシャッフル回数はわかっていない【未解決問題】
4入力と5入力について（6入力以上も）、既存のプロトコルよりも少ないシャッフル回数で非コミット型ANDプロトコルを構成できるか？ ただし、シャッフルは一様で閉じているとする。
補足• コミット型はKoch et al. [KWH15] の繰り返しで• Mizuki-Kumamoto-Soneは（閉じていない）シャッフル1回
にできる
54

再掲
Mizuki-Kumamoto-Soneプロトコルの2つのシャッフル[ ？？ ？？ ]？ ？？ ？

(shuf, {id, (1 3)(2 4)})
(shuf, {id, (2 3)})

どちらも一様で閉じている

これらは1つのシャッフルに結合できる：(shuf, {id, (1 3)(2 4),(2 3),(1 3 4 2)})
しかし、この置換の集合は閉じていない（部分群になっていない）【課題】
一様で閉じているシャッフル1つで4枚コミット型
ＡＮＤプロトコルは構成できるか？
55

多入力ANDプロトコル
𝑥2

⋯

𝑥1

? ?

⋯

? ? ? ?

𝑥1 ∧ 𝑥2 ∧ ⋯ ∧ 𝑥𝑛

𝑥𝑛

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）• 追加カード1枚 → シャッフル 𝑛 − 1 回（非コミット型）• 追加カードなし →◼ 𝑛 = 3 のとき、シャッフル 5 回（非コミット型）◼ 𝑛 ≥ 4 のとき、シャッフル 𝑛 + 1 回（非コミット型）[Miz16] Takaaki Mizuki. Card-based protocols for securely computing the conjunction of multiple variables.
Theor. Comput. Sci., 622(C):34–44, 2016.

56
56

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）
バッチングという技術 [SN21] を使うと、シャッフル回数を減らせることがわかっている [ISEC202305]
60
50
40
30
20
10

0
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
ISEC202305
自明な上界[SN21] Kazumasa Shinagawa and Koji Nuida. A single shuffle is enough for secure card-based computation of any
Boolean circuit. Discrete Applied Mathematics, 289:248–261, 2021

[ISEC202305] 吉田拓叶, 中林佳祐, 田中滉大, 千田栄幸, 水木敬明,``2枚の追加カードを用いた多入力AND秘密計算におけるシャッフル回数の削減,'' 電子情報通信学会信学技報, Vol.123, No.26, ISEC2023-7, pp.35-42 (May 2023).

57
57

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）
バッチングという技術 [SN21] を使うと、シャッフル回数を減らせることがわかっている [ISEC202305]
60
50
40
30
20

【課題】
更にシャッフル回数を減らせるか？

10

0
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
ISEC202305
自明な上界[SN21] Kazumasa Shinagawa and Koji Nuida. A single shuffle is enough for secure card-based computation of any
Boolean circuit. Discrete Applied Mathematics, 289:248–261, 2021

[ISEC202305] 吉田拓叶, 中林佳祐, 田中滉大, 千田栄幸, 水木敬明,``2枚の追加カードを用いた多入力AND秘密計算におけるシャッフル回数の削減,'' 電子情報通信学会信学技報, Vol.123, No.26, ISEC2023-7, pp.35-42 (May 2023).

58

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）
バッチングという技術 [SN21] を使うと、シャッフル回数を減らせることがわかっている [ISEC202305][YTN+23]60 Takuto Yoshida, Kodai Tanaka, Keisuke Nakabayashi, Eikoh Chida, andTakaaki Mizuki. Upper bounds on the number of shuffles for two-helping-card multi50 protocols. Cryptology and Network Security, volume 14342 of LNCS, pages
input AND
211–231, 2023, Springer.
40
30
20

【課題】
更にシャッフル回数を減らせるか？

10

0
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
ISEC202305
自明な上界[SN21] Kazumasa Shinagawa and Koji Nuida. A single shuffle is enough for secure card-based computation of any
Boolean circuit. Discrete Applied Mathematics, 289:248–261, 2021

[ISEC202305] 吉田拓叶, 中林佳祐, 田中滉大, 千田栄幸, 水木敬明,``2枚の追加カードを用いた多入力AND秘密計算におけるシャッフル回数の削減,'' 電子情報通信学会信学技報, Vol.123, No.26, ISEC2023-7, pp.35-42 (May 2023).

59

2016年に与えられた上界[Miz16]：

このページを追加しています• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）
バッチングという技術 [SN21] を使うと、シャッフル回数を減らせることがわかっている [IYTN+23]【追記】
SCIS 2024において石崎と品川は、一般化パイルスクラ
ンブルシャッフルやブランチング技術を導入することで、シャッフル回数を減らせることを示している [SCIS2024][SCIS2024]石崎悠斗, 品川和雅,``追加カード 2 枚の多入力 AND 計算におけるシャッフル回数の新しい削減方法,''
SCIS2024 暗号と情報セキュリティシンポジウム, 3D1-1 (January 2024).

[SN21] Kazumasa Shinagawa and Koji Nuida. A single shuffle is enough for secure card-based computation of any
Boolean circuit. Discrete Applied Mathematics, 289:248–261, 2021
[YTN+23] Takuto Yoshida, Kodai Tanaka, Keisuke Nakabayashi, Eikoh Chida, and Takaaki Mizuki. Upper bounds on
the number of shuffles for two-helping-card multi-input AND protocols. Cryptology and Network Security, volume14342 of LNCS, pages 211–231, 2023, Springer.

60

2016年に与えられた上界[Miz16]：• 追加カード2枚 → シャッフル 𝑛 − 1 回（コミット型）• 追加カード1枚 → シャッフル 𝑛 − 1 回（非コミット型）• 追加カードなし →◼ 𝑛 = 3 のとき、シャッフル 5 回（非コミット型）◼ 𝑛 ≥ 4 のとき、シャッフル 𝑛 + 1 回（非コミット型）【課題】
追加カード1枚の場合のシャッフル
回数については未検討

61
61

追加カード枚数を固定するのではなく、シャッフル
を１回に固定すると？
Shinagawa-Nuida [SN21] のカードベースのガー
ブルドサーキットの考えを応用すると、追加カード
2𝑛 − 2枚でシャッフル1回の𝑛入力コミット型AND
プロトコルを構成できる [KTMM22]（ただし、このときのシャッフルは閉じていない）。
【未解決問題】
更に追加カード枚数を減らせるか？
[SN21] Kazumasa Shinagawa and Koji Nuida. A single shuffle is enough for secure card-based computation of any
Boolean circuit. Discrete Applied Mathematics, 289:248–261, 2021
[KTMM22] Tomoki Kuzuma, Kodai Toyoda, Daiki Miyahara, and Takaaki Mizuki. Card-based single-shuffle protocols forsecure multiple-input AND and XOR computations. In ASIA Public-Key Cryptography, pages 51–58, NY, 2022. ACM.

62

目次
1.

導入

2.

非コミット型2入力ANDプロトコル

3.

コミット型2入力ANDプロトコル

4.

多入力ANDプロトコル

5.

汎用的なプロトコル

63任意の𝑛入力論理関数（ 𝑛 ≥ 4 ）に対して、追加カード6枚でコミット型プロトコルを構成できる[NHMS15a]

6枚で十分
𝑥2

⋯

𝑥1

? ?

? ?

𝑥𝑛

𝑓

⋯

? ? ? ?

【未解決問題】
6枚から追加カード枚数を減らせるか？

[NHMS15a] Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Card-based protocols for any Booleanfunction. Theory and Applications of Models of Computation, volume 9076 of LNCS, pages 110–121, Cham, 2015. Springer.

64

おわりに

昨年度のスライドここまで

ANDプロトコルにまつわる未解決問題• 2色カード組、1ビット2枚符号化• 標準モデル（パブリックモデル、シャッフルモデル） [MS14]• 2入力や多入力のANDを秘密計算するプロトコル• コミット型、非コミット型

カードベース暗号の研究分野にはたくさんの未解決問題や課題があります
皆様の参入を期待しています
本研究は九州大学マス・フォア・インダストリ研究所 共同利用・共同研究拠点の支援を受けた．（2023年度短期共同研究「産学連携によるカードベース暗号の数理的未解決問題と新課題の整理」（2023a020）

65

カードベース暗号の研究分野の俯瞰
カードベース暗号の計算モデル
プロトコル

計算限界の解明
カード枚数やシャッフル回数の下界の発見

抽象機械
𝑃 = 𝐷, 𝑈, 𝑄, 𝐴

疑似コード
1 input …
2 perm …

自然言語
step1. 入力
step2. 並べ替え…

…

・プロトコルの開発（=上界の発見）

計算モデルのリファイン
道具・操作を計算モデルに適用させる

現実世界
教育応用
人間
カード組
操作

・情報科学への興味の喚起
・暗号・セキュリティ教育- パズルのゼロ知識証明

・抽象化の理解

実利用のプロトコルとして展開
ex.) ・気まずくならない告白
・みんなで食事会を開くか決める・金持ち比べ（→socialな身近な問題への解決）

2023年以降に出版された論文（Scopusより）
著者名

タイトル

出版年 出版物名 会議名

Ruangwises S.

Verifying the first nonzero term: physical ZKPs for ABC End View, Goishi Hiroi, and 2024
Toichika
Journal of Combinatorial Optimiz

Ono T., Shinagawa K., Nakai T., WatanabeSingle-Shuffle
Y., Iwamoto
Card-BasedM.
Protocols with Six Cards per Gate

2024 LNCS

ICISC 2023

Hatsugai K., Asano K., Abe Y.

2024 LNCS

COCOON 2023

A Physical Zero-Knowledge Proof for Sumplete, a Puzzle Generated by ChatGPT

Robert L., Miyahara D., LafourcadePhysicalP., Mizuki
ZKP
T. protocols for Nurimisaki and Kurodoko

2023 Theoretical Computer Science

Shikata H., Miyahara D., Mizuki T. Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions2023
with Proceedings
Arbitrary Ranges
APKC
of the2023
10th ACM As
Ruangwises S.

An improved physical ZKP for nonogram and nonogram color

2023 Journal of Combinatorial Optimiz

Shinagawa K., Miyamoto K.

Automorphism Shuffles for Graphs and Hypergraphs and Its Applications

2023 IEICE Transactions on Fundamen

Abe Y., Nakai T., Watanabe Y., Iwamoto
A Computationally
M., Ohta K. Efficient Card-Based Majority Voting Protocol with Fewer Cards2023
in theIEICE
PrivateTransactions
Model
on Fundamen
Suga Y.

Relationship between AND extension and XOR extension of 3-valued input with 2-party
2023card-based2023 IEEEICCE-Asia
protocols
International
2023
ConferenRuangwises S.

The Landscape of Computing Symmetric n-Variable Functions with 2n Cards

2023 LNCSICTAC 2023

Yoshida T., Tanaka K., NakabayashiUpper
K., Chida
BoundsE., Mizuki
on the NumberT.
of Shuffles for Two-Helping-Card Multi-input and Protocols
2023 LNCSCANS 2023

Manabe Y., Shinagawa K.

Free-XOR in Card-Based Garbled Circuits

CANS 2023

Suga Y.

A classification for commutative three-element semigroups with local XOR structure2023
and2023
its implementability
International
ICCE-Taiwan
Conferenceof card-bas
2023 oTanaka K., Mizuki T.

Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

Suga Y.

POSTER: A Card-Based Protocol that Lets You Know How Close Two Parties are in2023
their LNCS
Opinions (agree/disagree)
ACNS 2023
by U

Ruangwises S.

Physical Zero-Knowledge Proofs for Five Cells

2023 LNCS

LATINCRYPT 2023

Tozawa K., Morita H., Mizuki T.

Single-Shuffle Card-Based Protocol with Eight Cards per Gate

2023 LNCS

UCNC 2023

Hand S., Koch A., Lafourcade P., Miyahara
Check AlternatingD., RobertPatterns:
L.
A Physical Zero-Knowledge Proof for Moon-or-Sun

2023 LNCSIWSEC 2023

Nuida K.

Efficient Card-Based Millionaires’ Protocols via Non-binary Input Encoding

2023 LNCSIWSEC 2023

Ruangwises S.

Physically Verifying the First Nonzero Term in a Sequence: Physical ZKPs for ABC End
2023View
LNCS
and Goishi
IJTCS-FAW
Hiroi 2023

Suga Y.

Security Considerations for the Fourth Data Over Non-Committed 3-Valued Card-Based2023 Protocols
2023 International
ITC-CSCC
Technical
2023 Con

Guillen L.

The Asymmetric five-card trick: working with variable encoding in card-based protocols
2023 Journal of Cryptographic Enginee2023 LNCS
2023 LNCSFCT 2023

Shimano M., Sakiyama K., Miyahara
Towards
D.
Verifying Physical Assumption in Card-Based Cryptography2023 LNCSSECITC 2022

Komano Y., Mizuki T.

Card-Based Zero-Knowledge Proof Protocol for Pancake Sorting

2023 LNCSSECITC 2022

Ruangwises S.

Physical Zero-Knowledge Proof for Ball Sort Puzzle

2023 LNCS

CiE 2023

スペースの都合で切れている箇所があり申し訳ありません。機械的に抽出しているため漏れがあるかもしれません。

67

国際会議発表から今日のご講演
Tomoki Ono, Kazumasa Shinagawa, Takeshi Nakai, Yohei
Watanabe, Mitsugu Iwamoto, Single-Shuffle Card-BasedProtocols with Six Cards per Gate. ICISC 2023
Kyosuke Hatsugai, Kyoichi Asano, Yoshiki Abe, PhysicalZero-Knowledge Proof for Sumplete, a Puzzle Generated by
ChatGPT. COCOON 2023
Yoshihiro Takahashi, Kazumasa Shinagawa, Hayato Shikata
and Takaaki Mizuki, Efficient Card-Based Protocols for
Symmetric Functions Using Four-Colored Decks, APKC 2024
Yuki Ito, Hayato Shikata, Takuo Suganuma and Takaaki
Mizuki, Card-Based Cryptography Meets 3D Printer, UCNC
2024
68

10:40-11:20
小野 知樹(電気通信大学)
ゲートあたり6枚で実行できるカードベースガーブルド回路
11:20-12:00
高橋 由紘(茨城大学)
多色カードを用いた効率的な対称関数プロトコル
14:10-14:50
初貝 恭祐(電気通信大学)
Sumpleteに対する物理的ゼロ知識証明
15:45-16:25
伊藤 優樹(東北大学)
3Dプリンタのカードベース暗号への応用
69

おまけ（２つ宣伝）70

真に高機能暗号の社会展開に資する物理・視覚暗号
科学研究費

基盤研究(A)

23H00479

研究代表者
花岡 悟一郎
研究分担者
品川 和雅、宮原 大輝、矢内 直人、
Attrapadung Nuttapong、渡邉 洋平、岩本 貢、
松田 隆宏、水木 敬明、宮本賢伍、山下 恭佑

71

真に高機能暗号の社会展開に資する物理・視覚暗号
科学研究費 基盤研究(A)23H00479

高機能暗号は安全なデータ利活用を可能とする技術として極めて有効であるが、機能や安全性の概念が複雑であり、潜在的な利用者企業が必ずしも十分に理解が出来ず社会展開があまり進んでいない。本研究では、高機能暗号の事業展開を検討している企業と連携し、高機能暗号技術について、潜在的利用者に対する機能や安全性の平易な説明を可能とする物
理・視覚暗号の設計および実装を行う。

72

暗号の理論と技術
量子時代のセキュリティ理解のために
国廣昇・編著
安田雅哉／水木敬明／高安敦／
高島克幸／米山一樹／大原一真／江村恵太・著
発行：2024/05/22
ISBN：978-4-06-53563

73暗号の理論と技術
量子時代のセキュリティ理解のために
1章 暗号技術の基礎
2章 現代の暗号技術を支える数学
3章 カードベース暗号
4章 格子理論を用いた暗号攻撃
5章 量子計算基礎とその暗号への応用
6章 耐量子計算機暗号
7章 形式手法による安全性検証
8章 秘密計算9章 証明可能安全性と高機能暗号74

暗号の理論と技術
量子時代のセキュリティ理解のために

3章 カードベース暗号
3.1 カード組を用いた秘密計算
3.2 コミット型プロトコル
3.3 金持ち比べプロトコル
3.4 ゼロ知識証明プロトコル75

10:00-12:00 オープニング・セッション１
10:00-10:10
須賀 祐治(株式会社インターネットイニシア
ティブ)
オープニング
10:10-10:40
水木 敬明(東北大学)
昨年の研究集会からのアップデート
10:40-11:20
小野 知樹(電気通信大学)
ゲートあたり6枚で実行できるカードベース
ガーブルド回路
11:20-12:00
高橋 由紘(茨城大学)
多色カードを用いた効率的な対称関数プロト
コル
13:30-15:30 セッション２
13:30-14:10
安部 芳紀(電気通信大学 <現：セコム株式会
社 IS研究所>)
数独に対する物理的ゼロ知識証明

14:10-14:50
初貝 恭祐(電気通信大学)
Sumpleteに対する物理的ゼロ知識証明
14:50-15:30
宮原大輝(電気通信大学)
月か太陽に対する物理的ゼロ知識証明
15:45-17:45 セッション３・クロージング
15:45-16:25
伊藤 優樹(東北大学)
3Dプリンタのカードベース暗号への応用
16:25-17:05
品川 和雅(茨城大学)
一様巡回群分解に基づく一様閉シャッフルの実現方法とその応用
17:05-17:35
須賀 祐治(株式会社インターネットイニシア
ティブ)
正則グラフでアクセス構造を表現する非コ
ミットメント型カードプロトコル
17:35-17:45
須賀 祐治(株式会社インターネットイニシア
ティブ)
クロージング76