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

2024/5/22(水) 15:45 - 16:25

3Dプリンタのカードベース暗号への応用

伊藤優樹 (東北大)目次
1. はじめに
2. Five-Card Trick用オープン装置
3. 特殊ケースの作成とコピープロトコル
4. 特殊ケースによるソート機能

5. 特殊ケースによる対称関数の秘密計算
6. まとめ2024/5/22

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

2

1. はじめにカードベース暗号とその実装• カードベース暗号◦ 物理的なカード組を用いて秘密計算等の暗号機能を実現• コミットメント◦ 秘密計算の入力ビットを表現するカード列? ?
𝑎=0=1• Five-Card Trick [DB90]◦ 歴史上最初のカードベース暗号プロトコル◦ 2入力のANDの秘密計算を5枚のカードで実現[DB90] Den Boer, B.: More Efficient Match-Making and Satisfiability The Five Card Trick, Advances in Cryptology— EUROCRYPT ’89 (Quisquater, J.-J. andVandewalle, J., eds.), LNCS, Vol. 434, Berlin, Heidelberg, Springer, pp. 208– 217(1990).

2024/5/22

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

31. はじめにFive-Card Trick• 初期状態
?

=0?

?

a?

b

(1)左2枚のカードを入れ替え=1(2)中央の を裏返す?

?

?

?

?

?

?

?

?

?

?

?

ഥa?

?

?

?

?

(4)カードをめくりa ∧bを得る

a ∧b=1?

例
2024/5/22?

b(3)ランダムカットを適用?

?

?

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

a ∧b=04

1. はじめに3Dプリンタで作成した制作物• 3Dプリンタを用いてカードベース暗号プロトコルの実装に有用なケースや装置の設計・作成◦ 部分開示用ケース• 部分開示の実装を容易かつ確実にし，効率的なプロトコルを構成◦ Five-Card Trick用オープン装置(部分開示)• トランプカードでのFive-Card Trick実行時，最終ステップで5枚をめくる際に利用可能◦ Five-Card trick用オープン装置(2色カード)• 2色カード組でのFive-Card Trick実行時，最終ステップで5枚をめくる際に利用可能

2024/5/22

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

51. はじめに特殊なシャッフル用ケース• 特殊なシャッフル用ケース◦ 複雑なシャッフル実装のためのケース◦ 既存の5枚コピープロトコルを安全に実行• 特殊ケースの追加機能・装置◦ ケース上部にカードを収容する機構◦ カードを取り出すのための補助装置• 対称関数の秘密計算への応用
カード束作成回数(回)Ruangwises, Ito[RI21]
提案手法

カード枚数(枚)n2 Τ2 + 3nΤ2 − 22n+22n-22n+1◦ 本成果は国際会議 UCNC2024 (6/17-21@韓国)で発表予定[RI21] Ruangwises, S. and Itoh, T.: Securely computing the nvariable equality function with 2n cards, Theor. Comput. Sci., Vol. 887, pp. 99–110 (2021).

2024/5/22

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

6目次
1. はじめに
2. Five-Card Trick用オープン装置
3. 特殊ケースの作成とコピープロトコル
4. 特殊ケースによるソート機能

5. 特殊ケースによる対称関数の秘密計算
6. まとめ2024/5/22

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

7

2. Five-Card Trick用オープン装置

オープン装置の設計と作成• 作成における要件◦ 一度の操作で5枚同時にオープンする機構• 実行の楽しさ，視覚的な魅力の創出◦ すべてのパーツが家庭用3Dプリンタで作成可能• 部品の調達が不要• 誰でも容易に作成可能• オープン装置の構造の設計◦ 視覚的な魅力についての検討• 3D CADのアセンブリ機能を用いてシミュレーションで動作を確認

回転軸がケース端
2023/7/24

回転軸がケース中央

セキュリティサマーサミット2023

82. Five-Card Trick用オープン装置

オープン装置の設計と作成• カードホルダーの設計◦ ホルダーとカードの間に余分な隙間が無いよう正確な寸法◦ 操作中にカードが外れず，かつ脱着がスムーズな構造• 脱落防止のツメ• カード挿入部の角度調整• 3Dプリンタでの作成◦ 家庭用3Dプリンタ(熱溶解積層 : FFF方式) を用いて作成◦ PLAフィラメントを使用

3Dプリンタでの作成の様子
2024/5/22

3Dプリンタで出力後組み立てたオープン装置

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

9目次
1. はじめに
2. Five-Card Trick用オープン装置
3. 特殊ケースの作成とコピープロトコル
4. 特殊ケースによるソート機能

5. 特殊ケースによる対称関数の秘密計算
6. まとめ2024/5/22

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

103.特殊ケースの作成とコピープロトコル

複雑なシャッフルと特殊ケース• 複雑なシャッフルの例 (shuf, {id,(1 4 2 5 3)})◦ 左2枚と残り3枚を束とし，1/2の確率で入れ替えるシャッフル◦ 人間の手のみでの実装は，束の枚数の違いから困難

123 4 5?

?

?

?

?

• 特殊ケース[NNH+15]

1 2 3 4 5? ? ? ? ?
3 4 5 1 2? ? ? ? ?

◦ (shuf, {id,(1 4 2 5 3)})の実装方法として言及されたカードケース◦ ケースを重ね，中のカード束を1つに結合[NNH+15] Nishimura, A., Nishida, T., Hayashi, Y., Mizuki, T. and Sone, H.: Five-Card Secure Computations Using Unequal Division Shuffle, Theory and Practice of
Natural Computing (Dediu, A.-H., Magdalena, L. and Martín-Vide, C., eds.), LNCS, Vol. 9477, Cham, Springer, pp. 109–120(2015).

2024/5/22

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

114.特殊ケースの作成とコピープロトコル

コピープロトコル[NNH+15](shuf, {id,(1 4 2 5 3)})を用いたコミットメントのコピー(1)カードを裏返し，入れ替え?

(2) (shuf, {id,(1 4 2 5 3)})を適用

?

?

a?

?

?

a0?

?

a1?

?

?

?

?

?

?

(4) 5枚目のカードをめくる(a)の場合，1,2と3,4枚目がa となる?
?

?

?

?

a(b)?

?

?

(3) カードを入れ替え?

?

?
aの場合，1,2枚目を入れ替え，(1)に戻る?

?

?

?

ഥa

[NNH+15] Nishimura, A., Nishida, T., Hayashi, Y., Mizuki, T. and Sone, H.: Five-Card Secure Computations Using Unequal Division Shuffle, Theory and Practice ofNatural Computing (Dediu, A.-H., Magdalena, L. and Martín-Vide, C., eds.), LNCS, Vol. 9477, Cham, Springer, pp. 109–120(2015).

2024/5/22

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

12

3.特殊ケースの作成とコピープロトコル

特殊ケースの作成• 特殊ケースの作成とプロトコルの実装◦ 3Dプリンタを用いて特殊ケースを作成◦ コミットメントのコピープロトコル[NNH+15]を実際に実行し，複雑なシャッフルにおけるケースの有用性を検証作成したケース
蓋と底がスライド可能

蓋と底のスライドによる、ケース内のカード束の結合[NNH+15] Nishimura, A., Nishida, T., Hayashi, Y., Mizuki, T. and Sone, H.: Five-Card Secure Computations Using Unequal Division Shuffle, Theory and Practice ofNatural Computing (Dediu, A.-H., Magdalena, L. and Martín-Vide, C., eds.), LNCS, Vol. 9477, Cham, Springer, pp. 109–120(2015).

2024/5/22

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

13

3.特殊ケースの作成とコピープロトコル

特殊ケースと用いた実装の様子• 入力を1としたコピープロトコル◦ 5枚目がクローバーの場合

2024/5/22

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

14目次
1. はじめに
2. Five-Card Trick用オープン装置
3. 特殊ケースの作成とコピープロトコル
4. 特殊ケースによるソート機能

5. 特殊ケースによる対称関数の秘密計算
6. まとめ2024/5/22

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

15

4.特殊ケースによるソート機能

特殊ケース利用における発展手法• ケース上部にカードを固定する手法[SCIS2022]◦ 輪ゴム等で固定する方法が示されている• 3Dプリンタで作成した特殊ケース◦ 上面に固定する機構を付与◦ シャッフル操作においても安定してカードを固定[SCIS2022] 四方隼人，豊田航大，宮原大輝，水木敬明： 最小のカー ド枚数による対称関数の秘密計算について，2022 年暗号 と情報セキュリティシンポジウム,1F4-3 (2022).

2024/5/22

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

16

4.特殊ケースによるソート機能[SCIS2022]の一般化: サイズの異なる束のソート? ?
𝑥? ? ? ?

? ? ? ?

?
? ?
𝑥?

=0=1

かきまぜて，上部のカードをめくる
𝑥の値を秘密にしたままサイズの異なる束をソートのハコを下にして結合𝑥=0? ? ? ?

?

𝑥=1? ? ? ? ?

[SCIS2022] 四方隼人，豊田航大，宮原大輝，水木敬明： 最小のカー ド枚数による対称関数の秘密計算について，2022 年暗号 と情報セキュリティシンポジウム,1F4-3 (2022).

2024/5/22

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

17目次
1. はじめに
2. Five-Card Trick用オープン装置
3. 特殊ケースの作成とコピープロトコル
4. 特殊ケースによるソート機能

5. 特殊ケースによる対称関数の秘密計算
6. まとめ2024/5/22

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

18

5. 特殊ケースによる対称関数の秘密計算

対称関数の秘密計算(コミットメントの加算)
? ?
𝑥1? ?
𝑥2

E𝑛+1 (0)・・・

E𝑛+1 (1)・・・

E𝑛+1 (2)・・・

E𝑛+1 (𝑛)・・・
12 3 4・・・? ?
𝑥𝑛

n+1? ? ・・・ ?
E𝑛+1 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛
2024/5/22

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

19

5. 特殊ケースによる対称関数の秘密計算

対称関数の秘密計算
? ?
𝑥1? ?
𝑥2・・・

? ?
𝑥𝑛

既存プロトコル[RI21]◦ シャッフル

提案プロトコル◦ シャッフル• パイルシフティングシャッフル◦ 束の作成回数• n2 Τ2 + 3nΤ2 − 2 回• 特殊ケースを使用◦ 束の作成回数• 2n − 2 回? ? ・・・ ?
E𝑛+1 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛
[RI21] Ruangwises, S. and Itoh, T.: Securely computing the nvariable equality function with 2n cards, Theor. Comput. Sci., Vol. 887, pp. 99–110 (2021).

2024/5/22

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

20

5. 特殊ケースによる対称関数の秘密計算

対称関数の秘密計算• 特殊ケースを用いたコミットメントの加算◦ 2n+1枚のカードと2つの特殊ケースを使用(1) 𝑥1 と𝑥2 のコミットメントを加算し，E3 𝑥1 + 𝑥2 を得る? ? ? ?
𝑥1𝑥2?

?

? ?

?

? ? ?

ソート

2024/5/22

E3𝑥1 + 𝑥2

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

21

5. 特殊ケースによる対称関数の秘密計算

対称関数の秘密計算(2)同様の作業を繰り返し， 𝑥𝑛 まで加算する? ? ?
E3𝑥1 + 𝑥2? ? ? ?
E4𝑥1 + 𝑥2 + 𝑥3? ? ・・・ ?
E𝑛+1 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛・・・𝑛 − 1 cards◦ カード束作成回数の削減• Ruangwisesら：n2 Τ2 + 3nΤ2 − 2 回• 提案手法：2n-2 回

◦ カード枚数の削減• Ruangwisesら：2n+2 枚• 提案手法：2n+1 枚[RI21] Ruangwises, S. and Itoh, T.: Securely computing the nvariable equality function with 2n cards, Theor. Comput. Sci., Vol. 887, pp. 99–110 (2021).

2024/5/22

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

22

5. 特殊ケースによる対称関数の秘密計算

特殊ケース操作のための補助装置• 補助装置の作成◦ ケースシャッフル器• 手のみでは実装が難しいケースのシャッフル操作をサポート• 装置が高速で回転することでシャッフル操作を実現◦ カード束の結合と取り出しの補助装置• カード取り出しの際，ケースを逆さまにせず安全に排出• 束の結合と取り出しの操作を確実化

ケースシャッフル器
2024/5/22

カード束の取り出し補助装置

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

23

5. 特殊ケースによる対称関数の秘密計算

5入力加算関数の実装

E𝑛+1 (0)・・・

E𝑛+1 (1)・・・

E𝑛+1 (2)・・・

E𝑛+1 (𝑛)・・・
12024/5/22

2 3 4n+1

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

24

目次
1. はじめに
2. Five-Card Trick用オープン装置
3. 特殊ケースの作成とコピープロトコル
4. 特殊ケースによるソート機能

5. 特殊ケースによる対称関数の秘密計算
6. まとめ2024/5/22

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

25

５. まとめ• 本研究での貢献◦ カードベース暗号プロトコルの実装に役立つケース・装置を3Dプリンタを用いて作成• 部分開示ケース• Five-Card Trick用オープン装置• 特殊なシャッフル用ケース• ケース操作のための補助装置◦ 特殊ケースによる対称関数の秘密計算の実装• カード束作成回数，カード枚数の削減• おわりに◦ 秘密計算・高機能暗号の社会への普及のために *• 暗号機能の意味・意義が幅広いステークホルダーに理解される必要→ カードベース暗号とその実装が一助となることを期待* 花岡悟一郎,岩本 貢,渡邉洋平,水木敬明,安部芳紀, 品川和雅,新井美音,矢内直人: 高機能暗号の社会展開 を促進する物理・視覚暗号,電子情報通信学会論文誌 A, Vol. J106A, No. 8, pp. 214–228 (2023).

2024/5/22

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

26