この記事は 2023年四半期カレンダー（３月版） の10日目の記事です
今回からカードベース暗号についてやっていきます．
| 何回目 | 内容 |
|---|---|
| 1 | カードベース暗号入門, 金持ち比べプロトコル |
| ２ | five-card trick |
| 3 | ランダム二等分割カット |
| 4 | ４枚版 five-card trick |
今回は，カードベース暗号入門として
・カードベース暗号とは
・金持ち比べプロトコル
の2つを解説していきます．
なお，今回のカードベース暗号の連載記事は，神奈川県立産業技術総合研究所主催の2021年11/25（木）, 11/29（月）, 11/30（火）に行われた「情報セキュリティ理解のための先端暗号技術入門」を参考にしています．
カードベース暗号
カードベース暗号とは，物理的なカードを用いて，秘密計算などを実現する暗号系のことです．
と書いたのはいいものの，これだけだと条件が緩すぎるので，今回の連載ではどのようなことを考えるのかについて補足します．
物理的なカード
まず，「物理的なカード」とは，もちろんトランプでも良いのですが，今回は次のようなカードを用いることにします．
トランプでいう，クローバーとハートで数字を無視したカード，と書けばイメージがつくでしょうか．
＊このカードは，東北大学でカードベース暗号の研究をされているグループから先ほどの講座にていただいたものです
ちなみに裏面は
このようになっていて，裏面だけでは面面が推測できないようになっています（これはどのカードでもそうですよね）
実はこのカードには他にも少し仕掛けがあるのですが，それは次回説明します
秘密計算
続いて本節初めのカードベース暗号の定義で「秘密計算」の部分として，今回の連載では大小比較と論理積について扱います
特に今回で大小比較を扱い，次回で論理積について解説します
暗号系の効率性
最後に「暗号系」の部分ですが，当然のことながらその暗号系の効率性についても考慮する必要があります
- 用いるカードの枚数
- シャッフル回数
の２つを用いて，本連載では，その暗号プロトコルの効率性を評価することにします．
その他
カードベース暗号の利点としては，ネットワークを使わずとも手軽に実行できる点が挙げられます
あとやってて楽しい
そんなカードベース暗号の初出は
B. D. Boer: ``More efficient match-making and satisfiability the five card trick'', In: Advances in Cryptology—EUROCRYPT’89: Workshop on the Theory and Application of Cryptographic Techniques Houthalen, Belgium, April 10–13, 1989 Proceedings 8. Springer Berlin Heidelberg, pp.208-217, 1990.
とされているらしいです．
＊タイトルの「five card trick」を次回扱います
シャカパチ
ここで話は変わるのですが，皆さんシャカパチはご存じでしょうか？
シャカパチとは，競技トレーディングカードゲームの場面において，プレイヤーが自身の手札のカードを用いて，音を鳴らす行為のことです
ちなみに，シャカパチの是非がどうとかという話をするつもりは一切ありませんし，具体的にどうやるかという話をするつもりもありません（どちらもググったらたくさん出てきます）
人によっては手癖となっている方もいるようですが，ハンデス（手札破壊）対策としても使われることがあります
これは自身の手札のカード列をシャッフルしていることに他ならないからです
先ほど「シャカパチの是非」と書きましたが，やはり音が出る都合上，対戦中に気になる方もいるようで，度々議論の対象となっている印象があります
しかし，そんなシャカパチもカードベース暗号の範疇であれば，誰の目を気にすることなく，音を鳴らすことができます（と言っても音を出す必要は全くないのですが）
なぜシャカパチが合法的に許されるのか，それはシャカパチが次章で紹介するランダムカットに相当するシャッフル操作だからです．
金持ち比べプロトコル
金持ち比べプロトコルとは，与えられた正整数の大小比較を行うプロトコルです．
いきなり金持ち比べプロトコルに入る前にランダムカットについて説明します
ランダムカット
ランダムカットとは，大雑把にはシャカパチ中に出てくる途中のカード列のことです
1番目から$m$番目までのインデックス付けられた$m$枚のカード列$C$に対して，0以上$m - 1$以下の正整数の乱数$r$を取ったとき，$C$に対するランダムカットとは，$C$の$r+1$番目のカードが先頭に来るような巡回的なシャッフルのこと
これだけ書いてもアレなので，具体例を紹介します．
まず，$m=4$で$C$として次のカード列を考えます:
それぞれのカードは左から1,2,3,4番目とインデックスが付けられているものとします．
このとき，$r$としてとりうる値は 0,1,2,3 のいずれかです．
r = 0 のとき
このとき，$C$に対するランダムカットは，$C$の1番目のカードが先頭に来るため，つまりそのままとなります
r = 1 のとき
このとき，$C$に対するランダムカットは，$C$の2番目のカードが先頭に来るため，つまり次のようになります:
r = 2 のとき
このとき，$C$に対するランダムカットは，$C$の3番目のカードが先頭に来るため，つまり次のようになります:
r = 3 のとき
このとき，$C$に対するランダムカットは，$C$の4番目のカードが先頭に来るため，つまり次のようになります:
ちなみに上記の状態からもう１回だけずらすと，初期状態に戻ります
金持ち比べプロトコル
さて，そんなランダムカットを用いて，金持ち比べプロトコルを紹介します
入力として，正整数$m$と1以上$m$以下の整数$a, b$をとります
Aliceは$a$，Bobは$b$のみの値を知っている際，$a, b$の値を公開することなく，$a < b$か$a \geq b$ を判定することを考えます
このとき金持ち比べプロトコルは，次のような手順で構成されます:
- Aliceは1-$a$番目にクローバー，$(a+1)$-$(m+1)$番目にハートを並べて，全てのカードを裏向きにする
- Bobは1-$(b-1)$番目にクローバー，$b$番目にハート，$(a+1)$-$(m+1)$番目にクローバーを並べて，全てのカードを裏向きにする
- Bobのカードを上下逆向きにして，Aliceと合わせた$2(m+1)$枚のカード列を構成する
- 3での$2(m+1)$枚のカード列に対して，ランダムカットを実行する
- Bob側のカードを全て公開し，ハートが出てきた箇所のみAlice側のカードを公開する
- ５でのカードがクローバーなら$a \geq b$，ハートなら$a < b$ となる
具体例
実際にまずは具体例から確認します．
$m=3$のときで，まずは$a=1, b=3$とします
1（以下説明の都合上全てカードを公開した状態にします）
2
3
4（２枚だけ動かす場合）
5, 6
4でのBobがハートの箇所（４番目の組）でAliceもハートなので，$a < b$ である（実際1<3）
続いて，$a=3, b=2$とします
1（同様に説明の都合上全てカードを公開した状態にします）
2（裏向きのカードはクローバーと思ってくださいカードが足りない）
3
4（２枚だけ動かす場合）
5, 6
4でのBobがハートの箇所（４番目の組）でAliceがクローバーなので，$a \geq b$ である（実際3>2）
大雑把な説明
なぜあのプロトコルで判定できるのか大雑把な説明をします
まず，$a < b$ のとき，Aliceの$b$番目のカードはハートで（$a + 1 \leq b$ ゆえ），Bobの$b$番目のカードもハートです
Bobはハートを１枚しか置けないため，
- Bobがハートのときに対応するAliceのカードはハートに確定
- よって（クローバー, ハート）という組は存在しない
- （ハート, ハート）という組はこの$b$番目の組のみ
となります
そして，ランダムカットを行なっても（ハート, ハート）のままどこかの位置に移動するだけなので，ランダムカット後でも（ハート, ハート）という組は１組しか存在しません
よって，Bob側のカードを全て公開した後にハートに対応するAliceのカードはハートのままですし，元を辿るとこれは $a < b$ であるためでした
同様に$a \geq b$ のとき，Aliceの$b$番目のカードはクローバーで，Bobの$b$番目のカードもハートです
Bobはハートを１枚しか置けないため，
- Bobがハートのときに対応するAliceのカードはクローバーに確定
- よって（ハート, ハート）という組は存在しない
- （クローバー, ハート）という組はこの$b$番目の組のみ
となります
そして，ランダムカットを行なっても（クローバー, ハート）のままどこかの位置に移動するだけなので，ランダムカット後でも（クローバー, ハート）という組は１組しか存在しません
よって，Bob側のカードを全て公開した後にハートに対応するAliceのカードはクローバーのままですし，元を辿るとこれは $a \geq b$ であるためでした
まとめ
今回からカードベース暗号の記事を始めました
写真を多く挿入して，視覚的にわかりやすくしたつもり（というかこうしないと書けない）でした
次回からはより複雑なプロトコルを扱い，そのプロトコルを改善するためには，という流れに入っていきます
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！