カードベース暗号について
この研究室ではカードベース暗号という分野を主に研究しています。カードベース暗号は暗号理論の一分野ですが、通常の暗号技術がコンピュータ(電子計算機)上の実装を想定するのに対して、カードベース暗号は(トランプのような)物理的なカード組による実装を目指す研究分野です。誤解を恐れずにイメージを伝えるとすれば、トランプマジックやカードゲームのような雰囲気で暗号プロトコルを実現するという研究分野です。具体的なイメージを持ってもらうために、カードベース暗号における研究テーマの例として二つ紹介します。
カード枚数の削減:カードベース暗号の研究テーマの一つにカード枚数の削減があります。特に、ANDプロトコル(二つの入力ビットの論理積を計算するプロトコル)やXORプロトコル(二つの入力ビットの排他的論理和を計算するプロトコル)のカード枚数の削減は精力的に研究されているテーマです。なぜこれらのプロトコルの効率化が重要かというと、どのような関数もAND関数やXOR関数の組合せとして表現できるため、これらのプロトコルの効率化は一般の関数に対するプロトコルの効率化をもたらす場合が多いからです。特に、ANDプロトコルはXORプロトコルに比べて構成が難しく、今でもANDプロトコルについて完全に解明されたわけではありません。最近では、カード枚数だけでなく、シャッフル回数やシャッフルの種類に注目したり、符号化やカードの種類を変更したりする場合についても研究が行われています。
パズルのゼロ知識証明:パズルのゼロ知識証明は近年精力的に研究されているテーマの一つです。これは、パズル(例えば数独)の出題者のアリスと、解答者のボブの間で行われるプロトコルで、ボブが答えの存在を疑っているが、パズルを解く楽しみ自体は失いたくない、という状況下で使えるものです。プロトコルを実行すると「ボブは答えの情報自体は得られないけれど、そのパズルに答えが存在することは納得できる」ということを実現できます。これまでにさまざまパズルについてプロトコルが構成されているのですが、その中でも特に人気のあるパズルは数独です。数独は世界的にも有名なパズルですし、パズルの条件が単純であるにも関わらず、プロトコルの構成法がたくさんあり、多くの研究が行われています。
カードベース暗号にはこれ以外にもさまざまな方向性の研究があります。理論限界を追求する研究も面白いですし、実用性や楽しさを重視した研究も面白いです。そのどちらの研究にも価値があり、そして両者は互いに深く関係しています。理論限界を追求した結果として実用的なプロトコルが発見できることもありますし、逆に実用性を重視した結果として理論的に興味深い現象が現れたりすることもあります。
もっと詳しく知りたい方へ
もっと詳しくカードベース暗号について知りたい方は、可換代数と組合せ論セミナーの講演スライドを参考にしてください。これを読むと、カードベース暗号のおおまかな歴史と、最近の進展のいくつかが把握できます。もちろん、ここに書かれていない面白い研究テーマもたくさんあります。
研究室の目標
新しい研究成果が得られたら、それを学会発表することを目指しましょう。暗号理論・情報セキュリティ分野の規模の大きな国内研究会としては、毎年10月頃に開催されるコンピュータセキュリティシンポジウム(CSS)と1月頃に開催される暗号と情報セキュリティシンポジウム(SCIS)があります。まずはこれらの国内研究会で発表することを目指しましょう。最終的には、英語論文を書いて国際論文誌(あるいは国際会議)に投稿することを目指しましょう。
最近の研究テーマの例
正多角形カードを用いた投票プロトコル
コインを用いた秘密計算プロトコル
数コロ(ペンシルパズルの一種)に対するゼロ知識証明プロトコル
数独に対するゼロ知識証明プロトコル
多色カードを用いた対称関数プロトコル
トランプカードと部分開示操作を用いたANDプロトコルとXORプロトコルとCOPYプロトコル
インジェクション攻撃に対する脆弱性の解析
追加カード2枚の設定で多入力ANDプロトコルのシャッフル回数の削減
出題者なしでヒット&ブローをプレイする方法
M2の本多由昂さんとM1の池田昇太さんの以下の論文が国際会議CANS2025に採択されました。(2025/7/11)
Yoshiaki Honda and Kazumasa Shinagawa, "Efficient Three-Input and Four-Input AND Protocols Using Playing Cards with Partial-Open Actions"
Shizuru Iino, Shota Ikeda, Kazumasa Shinagawa, Yang Li, Kazuo Sakiyama and Daiki Miyahara, "Impossibility of Four-Card AND Protocols with a Single Closed Shuffle"
M1の池田昇太さんの以下の論文が国際会議TAMC2025に採択されました。(2025/7/2)
Shota Ikeda, Kazumasa Shinagawa, "How to Play Mastermind without Game Master"
M1の池田昇太さんとOBの高橋由紘さんの以下の論文が国際会議IWSEC2025に採択されました。(2025/6/3)
Shota Ikeda, Yoshihiro Takahashi, Kazumasa Shinagawa, Koji Nuida, "Efficient Card-Based Protocols for Symmetric and Partially Doubly Symmetric Functions"
M2の本多由昂さんとM1の池田昇太さんが九州大学伊都キャンパスで開催された研究集会「産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地II」にて以下の招待講演を行いました。(2025/5/28)
池田昇太, "ランダムカットのみの4枚XORプロトコルに対する形式検証と不可能性証明"
本多由昂, "部分開示操作を用いた効率的なカードベースプロトコル"
M1の池田昇太さんの以下の論文が国際会議APKC2025に採択されました。(2025/3)
Kazuhiro Fujita, Shota Ikeda, Kazumasa Shinagawa, Kazuki Yoneyama, "Formal Verification and Proof of Impossibility for Four-Card XOR Protocols Using Only Random Cuts"
M1の本多由昂さんが令和6年度学生表彰者に選ばれました。(2025/3)
M2の高橋由紘さんとM1の石崎悠斗さんと本多由昂さんとB4の池田昇太さんと島津大さんが2025年 暗号と情報セキュリティシンポジウム(SCIS2025)において発表を行いました。(2025/1/30)
池田昇太, 高橋由紘, 品川和雅, "2n枚の部分的二重対称関数プロトコル"
島津大, 品川和雅, "効率的な全加算プロトコルとその加算プロトコルへの応用"
高橋由紘, 品川和雅, "シャッフル回数の少ないコミット型対称関数プロトコル"
石崎悠斗, 品川和雅, 縫田光司, "バッチング技術に用いるカード枚数の削減"
本多由昂, 品川和雅, "部分開示操作を用いた効率的な3入力/4入力のANDプロトコル"
M1の佐々木駿さんの論文が国際会議SOSA2025に採択されました。(2024/12)
Kodai Tanaka, Shun Sasaki, Kazumasa Shinagawa, Takaaki Mizuki, "Only Two Shuffles Perform Card-Based Zero-Knowledge Proof for Sudoku of Any Size"
M2の佐々木駿さんと高橋由紘さんと南川侑太さんとM1の本多由昂さんとB4の池田昇太さんがコンピュータセキュリティシンポジウム2024(CSS 2024)において発表を行いました。(2024/10/24-25)
南川侑太, 品川和雅, "任意関数と対称関数に対するコインベースプロトコル"
高橋由紘, 品川和雅, 縫田光司, "2色2n+1枚あるいは3色2n枚の対称関数プロトコル"
池田昇太, 品川和雅, "Mizuki-Kumamoto-SoneのANDプロトコルの最適性"
本多由昂, 品川和雅, "部分開示を用いたトランプ1組の多変数ANDプロトコル"
佐々木駿, 品川和雅, "対話的入力を用いたパイルスクランブルシャッフル1回の数独に対する物理ゼロ知識証明"
M1の本多由昂さんが国際会議IWSEC2024において発表を行いました。この論文はBest Paper Awardを受賞しました。(2024/9/18)
Yoshiaki Honda, Kazumasa Shinagawa, "Efficient Card-Based Protocols with a Standard Deck of Playing Cards Using Partial Opening"
B4の池田昇太さんが第106回CSEC研究発表会(セキュリティサマーサミット2024)において発表を行いました。(2024/7/22)
池田 昇太, 品川 和雅, "カードベース暗号を用いたヒット&ブローの遊び方"
M2の高橋由紘さんが国際会議APKC2024において発表を行いました。(2024/7/2)
Yoshihiro Takahashi, Kazumasa Shinagawa, Hayato Shikata, Takaaki Mizuki, "Efficient Card-Based Protocols for Symmetric Functions Using Four-Colored Decks"
M1の本多由昂さんの論文が国際会議IWSEC2024に採択されました。この会議は2024年9月17日〜19日に京都で開催されます。(2024/6/20)
Yoshiaki Honda, Kazumasa Shinagawa, "Efficient Card-Based Protocols with a Standard Deck of Playing Cards Using Partial Opening"
M2の佐々木駿さんの論文が論文誌New Generation Computingに採録されました。(2024/6/9)
Shun Sasaki, Kazumasa Shinagawa, "Physical Zero-Knowledge Proof for Sukoro"
M2の高橋由紘さんが九州大学伊都キャンパスで開催された研究集会「産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地」にて招待講演「多色カードを用いた効率的な対称関数プロトコル」を行いました。(2024/5/22)
B4の池田昇太さん、島津大さんの2名が品川研究室に配属されました。(2024/4/1)
M1の高橋由紘さんの論文が国際会議APKC2024に採択されました。この会議は2024年7月2日にシンガポールで開催されます。(2024/3/12)
Yoshihiro Takahashi, Kazumasa Shinagawa, Hayato Shikata, Takaaki Mizuki, "Efficient Card-Based Protocols for Symmetric Functions Using Four-Colored Decks"
M1の佐々木駿さんと高橋由紘さんが令和5年度学生表彰者に選ばれました。(2024/3/5)
M1の南川侑太さんとB4の石崎悠斗さんと中嶋光太さんと本多由昂さんが2024年 暗号と情報セキュリティシンポジウム(SCIS2024)において発表を行いました。(2024/1/25)
石崎 悠斗, 品川 和雅, "追加カード2枚の多入力AND計算におけるシャッフル回数の新しい削減方法"
本多 由昂, 品川 和雅, "部分開示操作を用いた4枚COPYプロトコル"
中嶋 光太, 品川 和雅, "カードベースANDプロトコルのインジェクション攻撃に対する脆弱性の検証"
南川 侑太, 品川 和雅, "コインを用いた任意の論理関数に対する秘密計算プロトコル"
M1の南川侑太さんの論文が論文誌IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciencesに採録されました。こちらの論文は早期公開されています。
Yuta Minamikawa, Kazumasa Shinagawa, "Coin-based Cryptographic Protocols without Hand Operations"
M1の佐々木駿さんと高橋由紘さんとB4の本多由昂さんがコンピュータセキュリティシンポジウム2023(CSS 2023)において発表を行いました。高橋由紘さんの論文はCSS優秀論文賞を、佐々木駿さんの論文はCSS学生論文賞を受賞しました。(2023/10/30)
高橋 由紘, 品川 和雅, "多色カードを用いた効率的な対称関数プロトコル"
本多 由昂, 品川 和雅, "部分開示操作を用いた効率的なカードベースプロトコル"
佐々木 駿, 品川 和雅, "数独に対するシャッフル3回のゼロ知識証明"
B4の石崎悠斗さん、中嶋光太さん、本多由昂さんの3名が品川研究室に配属されました。(2023/4/1)
B4の南川侑太さんが令和4年度学生表彰者に選ばれました。(2023/3/7)
B4の佐々木駿さんと高橋由紘さんが2023年 暗号と情報セキュリティシンポジウム(SCIS2023)において発表を行いました。
高橋 由紘, 品川 和雅, "正多角形カードを用いた投票プロトコル"
佐々木 駿, 品川 和雅, "数コロに対する物理的ゼロ知識証明プロトコル"
B4の南川侑太さんがコンピュータセキュリティシンポジウム2022(CSS 2022)において発表を行いました。この論文はCSS2022奨励賞を受賞しました。(2022/10/24)
南川 侑太, 品川 和雅, "ハンド操作を用いないコインベースプロトコル"
B4の佐々木駿さん、高橋由絋さん、南川侑太さんの3名が品川研究室に配属されました。(2022/4/1)