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

正則グラフでアクセス構造を表現する
非コミットメント型カードプロトコル須賀祐治
2024-05-22©Internet Initiative Japan Inc.

XOR演算は2-party 2値入力「一致関数」• 入力が同じなら出力0• そうじゃなければ出力1(入力が違った)
この考え方は自然に拡張できますね©Internet Initiative Japan Inc.

2-party 多値入力「一致関数」• 入力が同じなら出力0• そうじゃなければ出力1(入力違)

例えば4値入力©Internet Initiative Japan Inc.

須賀からの未解決問題2023 (1/2)• 2-party多値入力の一致関数の実現（ナイーブな手法については提示済）•(Hamming schemes での構成事例を提示した上で)Johnson scheme J(v,k) に関連するカードプロトコルの構成（もしくは既存のカードプロトコルがJohnson schemeと関連している事例の例示）©Internet Initiative Japan Inc.

須賀からの未解決問題2023 (2/2)• 位数4,6のアソシエーションスキームと関連するカードプロトコルの構成• 2枚入力 3-valued n-party 一致関数の構成（緩い条件：上下カード・非コミットメント型）• カード入力を制限する一般的な構成• カード入力として1枚カードを追加することによる新しいプロトコルを構成できるが，この拡張方式に呼応する一般的拡張方式の提示©Internet Initiative Japan Inc.

今回扱うカードプロトコル• 2-party k-valued（2者間 k通りの入力選択肢）• 非コミットメント型（一発勝負）• デッキ分割法を適用（わりと軽い方法だと信じてる）• カード入力に「制限」を設けることでできることのバリエーションを増やす戦略©Internet Initiative Japan Inc.

なにをやろうとしてるのか？
• 2人のプレーヤー・2色カードの利用• 事前に与えられたグラフの「頂点」を選択してカードを使って入力©Internet Initiative Japan Inc.

なにをやろうとしてるのか？
• 2人のプレーヤー・2色カードの利用• 事前に与えられたグラフの「頂点」を選択してカードを使って入力• エンコーディングルールは標準モデルではない©Internet Initiative Japan Inc.

「グラフの頂点を入力する」例• A given graph = C6 (6-gon)©Internet Initiative Japan Inc.

なにをやろうとしてるのか？
• 2人のプレーヤー・2色カードの利用• 事前に与えられたグラフの「頂点」を選択してカードを使って入力• 2人の入力値の「連結性」または「距離」に応じてプロトコル出力が変化する• 開示（出力）時に自明な状況を除いて何を入力したかを秘密にできる©Internet Initiative Japan Inc.

CSEC2024年3月の貢献• 与えられた「デッキ」（＝カード束）からの所望の入力を行う際にはランダムカットのみを用いる（＝カード入力の「制限」）• m-デッキ分割法でシャッフル（そこそこ軽い）• １ユーザm枚２スートカード配布時の完全分類(m=4,5,6,7,8)©Internet Initiative Japan Inc.

m-デッキ分割法• 1ユーザのカード入力：m枚• 1枚目同士，2枚目同士,…，ｍ枚目同士の2枚を1つのデッキとして輪ゴムで止めてぶん投げる
Alice

Bob…

…

©Internet Initiative Japan Inc.

m-デッキ分割法• 1ユーザのカード入力：m枚• 1枚目同士，2枚目同士,…，ｍ枚目同士の2枚を1つのデッキとして輪ゴムで止めてぶん投げる
Alice

Bob…

1枚目同士

…

2枚目同士

m枚目同士
…

©Internet Initiative Japan Inc.

m-デッキ分割法• 1ユーザのカード入力：m枚• 1枚目同士，2枚目同士,…，ｍ枚目同士の2枚を1つのデッキとして輪ゴムで止めてぶん投げる
Alice

Bob…

…

裏面同士をあわせて表面が見えないようにする
1枚目同士2枚目同士
m枚目同士…
©Internet Initiative Japan Inc.

m-デッキ分割法でやっていること• 以下の3つのシャッフルを同時にやっている(1) パイルスクランブル（束の入れ替え）(2) 上下シャッフル(3) ランダムカット• ポイント：各デッキは2枚しかない• これが効率的かどうかは主観的だけど©Internet Initiative Japan Inc.

1ユーザ4枚のケース• 下記で網羅してて，あとは「同型」•（全く定義してませんがスート入替も含めて2パターンしかない）©Internet Initiative Japan Inc.

初期状態からランダムカットの操作で入力できるのは4通り©Internet Initiative Japan Inc.

実際には・・・• 初期状態を表に向けて確認• 裏にしてカード束（重なった状態に）• 自分か相手かだれかがランダムカット（この状態でどこまでシフトしたかわからない）• 入力者は第3者から分かるようにランダムカットして「所望の」入力にする©Internet Initiative Japan Inc.

• m-デッキ分割法(m=4)を適用した場合
初期状態

{,}×1

{,}×2

{,}×2{,}×2{,}×3{,}×2

{,}×2

{,}×2

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

こちらの頂点から見たときも初期状態から見たときと同じ構造を持つ（∵ １回右シフトしただけ）ということはa given graph は正則グラフになる©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

• Remark：「一致関数」（完全グラフだから）©Internet Initiative Japan Inc.

• Remark：本来なら4C2=6通りの入力が可能なんだけど，敢えて4通りに「制限」する©Internet Initiative Japan Inc.

• m-デッキ分割法(m=4)を適用した場合
初期状態{,}×2}×1{,}×2}×1{,}×1{,}×2{,}×2{,}×2{,{,©Internet Initiative Japan Inc.

{,}×4

Aさん入力Bさん入力©Internet Initiative Japan Inc.

• Johnson scheme J(v,k)の定義から♡の位置をk-部分集合のindexと同一視する
Aさん入力
Bさん入力
距離＝０

©Internet Initiative Japan Inc.

• Johnson scheme J(v,k)の定義から♡の位置をk-部分集合のindexと同一視する
Aさん入力
Bさん入力
距離＝０

距離＝1

©Internet Initiative Japan Inc.

距離＝2

距離＝1

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

• Remark：距離は高々2までなので「連結性」でも同じグラフになる©Internet Initiative Japan Inc.

1ユーザ5枚のケース©Internet Initiative Japan Inc.

1ユーザ5枚のケース©Internet Initiative Japan Inc.

1ユーザ5枚のケース©Internet Initiative Japan Inc.

1ユーザ6枚のケース

C6#: 距離に応じて出力が変化するのではなくグラフ C6 のノードの「隣接性」だけを見ている©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

©Internet Initiative Japan Inc.

（再掲）1ユーザ6枚のケース

C6#: 距離に応じて出力が変化するのではなくグラフ C6 のノードの「隣接性」だけを見ている©Internet Initiative Japan Inc.

位数6でかつ対称なアソシエーションスキーム• 対称：2人の入力の順番で結果が変わらない

6-gon©Internet Initiative Japan Inc.

1ユーザ7枚のケース©Internet Initiative Japan Inc.

1ユーザ7枚のケース©Internet Initiative Japan Inc.

1ユーザ8枚のケース©Internet Initiative Japan Inc.

1ユーザ8枚のケース©Internet Initiative Japan Inc.

1ユーザ8枚のケース©Internet Initiative Japan Inc.

1ユーザ8枚のケース©Internet Initiative Japan Inc.

1ユーザ8枚のケース©Internet Initiative Japan Inc.

まとめに代えて• デッキ分割法を適用することで現れる
正則グラフの分類を紹介した• アソシエーションスキーム以外の代数的構造は1ユーザ6枚配布時にはじめて出現する• 7枚のとき面白い事例あり（K7）• 8枚もそこそこ面白い• 9枚はかなり面白い（CSS2024）©Internet Initiative Japan Inc.

少し抽象度を上げた説明• 構成できなかったカードプロトコルが実装できるかもしれない予感
実装可能な
カードプロトコル

Association
Schemes

Induced sub-Matrix
未知のカードプロトコル？？？

©Internet Initiative Japan Inc.

SubAssociationSchemes少し抽象度を上げた説明• 構成できなかったカードプロトコルが実装できるかもしれない予感
実装可能な
カードプロトコル

AssociationSchemes

実質的には「カード入力」の選択肢を制限している未知の？？？

カードプロトコル©Internet Initiative Japan Inc.

Induced sub-Matrix
SubAssociation
Schemes須賀からの未解決問題2023 (1/2)• 2-party多値入力の一致関数の実現（ナイーブな手法については提示済）•(Hamming schemes での構成事例を提示した上で)Johnson scheme J(v,k) に関連するカードプロトコルの構成（もしくは既存のカードプロトコルがJohnson schemeと関連している事例の例示）→ 両者ともナイーブな方法以外は未解決のまま©Internet Initiative Japan Inc.

須賀からの未解決問題2023 (2/2)• 位数4,6のアソシエーションスキームと関連するカードプロトコルの構成→位数7まで解決• 2枚入力 3-valued n-party 一致関数の構成→未着手（忘れてた）• カード入力を制限する一般的な構成→RCのみ• カード入力として1枚カードを追加することによる新しいプロトコルを構成できるが，この拡張方式に呼応する一般的拡張方式の提示→何言ってるかわかんない（思い出せない）©Internet Initiative Japan Inc.

未解決問題2024• 位数8以上のSymmetric association
schemes に呼応するカードプロトコルが構成可能か？
• Johnson schemeに着想を得た「ランダムカットで入力制限」する以外のバリエーション
ではどのようなグラフが構成できるか？
• RCで制限されたカード入力の集合を巡回群の元と思えば，与えられた有限群に呼応するシャッフルが必ず存在するのか？
©Internet Initiative Japan Inc.

気になっていること（位数8）• H(2,3) = 立方体のような構造 を分解すると巡回群（位数4）: 4枚のランダムカット[<1,2,3,4> | <5,6,7,8>]巡回群（位数2）:
ランダム二等分割カット?

={{1,2,3,4,{2,3,4,1,{3,4,1,2,{4,1,2,3,}©Internet Initiative Japan Inc.

5,6,7,8}, {5,6,7,8, 1,2,3,4},6,7,8,5}, {6,7,8,5, 2,3,4,1},
7,8,5,6}, {7,8,5,6, 3,4,1,2},
8,5,6,7}, {8,5,6,7, 4,1,2,3},

気になっていること（位数8）• H(2,3) = 立方体のような構造 を分解すると巡回群（位数4）: 4枚のランダムカット[<1,2,3,4> | <5,6,7,8>]巡回群（位数2）:
ランダム二等分割カット?

={{1,2,3,4,{2,3,4,1,{3,4,1,2,{4,1,2,3,}

5,6,7,8}, {5,6,7,8, 1,2,3,4},
6,7,8,5}, {6,7,8,5, 2,3,4,1},
7,8,5,6}, {7,8,5,6, 3,4,1,2},8,5,6,7}, {8,5,6,7, 4,1,2,3},

おそらくZ2 ×Z4 の群構造
©Internet Initiative Japan Inc.

• よくわからんくなってますが Z2×Z2×Z2{{1,2,3,4,{2,1,4,3,{3,4,1,2,{4,3,2,1,}

5,6,7,8}, {5,6,7,8, 1,2,3,4},
6,5,8,7}, {6,5,8,7, 2,1,4,3},
7,8,5,6}, {7,8,5,6, 3,4,1,2},
8,7,6,5}, {8,7,6,5, 4,3,2,1},[ [<1,2>|<3,4>] | [<5,6>|<7,8>] ]©Internet Initiative Japan Inc.

Stay safe and healthy©Internet Initiative Japan Inc.