カードベース暗号について

この研究室ではカードベース暗号という分野を主に研究しています。通常の暗号技術は、電子コンピュータに実装されますが、カードベース暗号の方式はトランプのようなカードを用いて実装されます。カードベース暗号は、まるでカードマジックやカードゲームをしているかのように、暗号技術を楽しく・視覚的に・物理的に実現する研究分野と言えるかもしれません。例えば、カードベース暗号では次のような問題を研究します。

• パズルのゼロ知識証明：アリスとボブは数独の愛好者です。ある日、アリスは自作の数独パズルをボブに出題しました。ボブはいつまで経っても解けないので、「この問題は不完全作で、解が存在しないのではないか」とアリスを疑い始めました。もしアリスが解答を提示すればボブの疑問は解消しますが、それだと「ボブがパズルを解く楽しみ」を奪ってしまうことになります。こんなとき、パズルのゼロ知識証明を用いると、「ボブは解答の情報は得られないが、そのパズルに答えが存在すること自体は、納得することができる」という状態を実現できます。つまり、ゼロ知識証明とは、解答は見せないのに、解答の存在自体を納得させる技術です。カードベース暗号では、いかに少ないカード枚数・シャッフル回数でプロトコルを実現できるかが研究されています。

• ゲームの仮想プレイヤー生成：アリスとボブはUNOの愛好者です。本当はUNOを4人くらいで遊びたいのですが、今日はアリスとボブの他に暇な友達はいませんでした。こんなとき、仮想プレイヤー生成プロトコルを実行すると、実プレイヤーがN人しかいない状況でも、仮想プレイヤーをM人作り出して、(N+M)人でゲームを遊ぶことができます。もちろん、仮想プレイヤーの手札情報など、秘匿すべき情報は、プロトコルの実行によって漏洩しません。この問題に対しても、いかに少ないカード枚数・シャッフル回数でプロトコルを実現できるかが研究されています。

• 秘密計算：アリスとボブとキャロルはおやつを買いに行くことになりました。彼らが一番買いたいお菓子は「たけのこ」か「きのこ」のどちらかです。あいにくお小遣いが少ないので、全員で1個を買うしかありません。もし全員が同じ派閥（「全員たけのこ」か「全員きのこ」のいずれかの状態）なら、それを買えばいいので、平和です。一方、もし誰かが異なる派閥（「1人がたけのこで、他2人がきのこ」か「1人がきのこで、他2人がたけのこ」のいずれかの状態）なら大変です。もしかしたら少数派の1人はこれがきっかけで他の人たちとギクシャクしてしまうかもしれません。そこで、もし誰かが異なる派閥に属すのなら、そもそも「たけのこでもきのこでもない、第三のおやつ」を買うことにしましょう。こんなとき、秘密計算を用いると、「全員が同じ派閥なのかどうか」を知ることができます。つまり、それぞれの入力情報は隠したまま、全員の入力情報が一致しているかどうかを知ることができるのです。一般には、任意の関数に対してこのような問題を考えます。カードベース暗号では、この問題に対しても、いかに少ないカード枚数・シャッフル回数でプロトコルを実現できるかが研究されています。秘密計算は研究の歴史も古く、「このカード枚数ではこの関数の秘密計算プロトコルは構成できない」等の下界の結果も数多く研究されています。

もっと詳しくカードベース暗号について知りたい方は、可換代数と組合せ論セミナーのスライドを見てみてください。

研究室の目標

新しい研究成果が得られたら、それを学会発表することを目指しましょう。暗号理論・情報セキュリティ分野の規模の大きな国内研究会としては、毎年10月頃に開催されるコンピュータセキュリティシンポジウム（CSS）と1月頃に開催される暗号と情報セキュリティシンポジウム（SCIS）があります。まずはこれらの国内研究会で発表することを目指しましょう。最終的には、英語論文を書いて国際論文誌（あるいは国際会議）に投稿することを目指しましょう。

本研究室の研究テーマの例

• 数独に対するゼロ知識証明プロトコル

• 対称関数に対する秘密計算プロトコル

• 部分開示操作を用いた秘密計算プロトコル

• 出題者なしでヒット＆ブローをプレイする方法

• コインを用いた秘密計算プロトコル

• M2の池田昇太さんとM1の本間日綺さん（筑波大学）の以下の論文が国際会議IWSEC2026に採択されました。（2026/8/21）

  • Kakeru Watanabe, Shota Ikeda, Kazumasa Shinagawa, Takaaki Mizuki, Kazuki Yoneyama, "Computer-Aided Proofs on Impossibility of Card-Based Protocols Using Only Random Cuts"

  • Haruki Homma, Shota Ikeda, Kazumasa Shinagawa, "Card-Based Zero-Knowledge Proofs for Norinori with Two or Three Shuffles"

• M2の池田昇太さんの以下の論文が国際会議ICICS2026に採択されました。（2026/7/25）

  • Shota Ikeda and Kazumasa Shinagawa, "Card-Based Zero-Knowledge Proofs for Necklace Splitting Problem"

• M2の池田昇太さんが九州大学伊都キャンパスで開催された研究集会「産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地III」にて以下の招待講演を行いました。（2026/7/9）

  • 池田昇太, "カードベース暗号を用いたヒットアンドブローの遊び方"

• M2の池田昇太さんが情報セキュリティ研究会において発表を行いました。（2026/5/26）

  • 池田昇太, 高橋由紘, 品川和雅, 縫田光司, "対称関数および部分的二重対称関数に対する効率的なカードベースプロトコル (from IWSEC 2025)"

• B4の本間日綺さんが第206回DPS・第112回CSEC合同研究発表会において発表を行いました。（2026/3/18）

  • 本間日綺, 品川和雅, "ポリオミノパズルに対するシャッフル3回あるいは2回のカードベースゼロ知識証明"

• M2の石崎悠斗さんと本多由昂さんとM1の池田昇太さんとB4の黒木竜馬さんと藤原愛斗さんと本間日綺さんが2026年 暗号と情報セキュリティシンポジウム（SCIS2026)において発表を行いました。（2026/1/26）

  • 本多由昂, 池田昇太, 品川和雅, "部分開示操作を用いた追加カードなしの3変数関数プロトコル"

  • 池田昇太, 本間日綺, 品川和雅, "スターバトルに対するカードベースゼロ知識証明"

  • 本間日綺, 池田昇太, 品川和雅, "バトルシップに対するカードベースゼロ知識証明"

  • 藤原愛斗, 品川和雅, "ハミルトン閉路問題に対するカードベースゼロ知識証明とHidatoへの応用"

  • 黒木竜馬, 品川和雅, "天秤を用いたSumpleteに対するゼロ知識証明プロトコル"

  • 石崎悠斗, 品川和雅, 池田昇太, "バッチング技術の多色カード組と上下回転を用いた効率化"

• M1の池田昇太さんが国際会議IWSEC2025において発表を行いました。この論文はBest Student Paper Awardを受賞しました。（2025/11/28）

  • Shota Ikeda, Yoshihiro Takahashi, Kazumasa Shinagawa and Koji Nuida, "Efficient Card-Based Protocols for Symmetric and Partially Doubly Symmetric Functions"

• M2の本多由昂さんが国際会議CANS2025において発表を行いました。（2025/11/19）

  • Yoshiaki Honda and Kazumasa Shinagawa, "Efficient Three-Input and Four-Input AND Protocols Using Playing Cards with Partial-Open Actions"

• M2の本多由昂さんと渡部翔さんとM1の池田昇太さんとB4の藤原愛斗さんと本間日綺さんがコンピュータセキュリティシンポジウム2025（CSS 2025）において発表を行いました。（2025/10/27-31）

  • 藤原愛斗, 池田昇太, 品川和雅, "テントアンドツリーに対するカードベースゼロ知識証明"

  • 本間日綺, 品川和雅, "Str8tsに対するカードベースゼロ知識証明"

  • 池田昇太, 品川和雅, "盗まれたネックレス問題に対するカードベースゼロ知識証明"

  • 池田昇太, 品川和雅, "nクイーン完成問題に対するカードベースゼロ知識証明"

  • 渡部翔, 池田昇太, 品川和雅, 水木敬明, 米山一樹, "ランダムカットのみを用いるカードベースプロトコルに対する計算機援用による不可能性証明"

  • 本多由昂, 品川和雅, "部分開示操作を用いた多入力ANDプロトコル"

• M1の池田昇太さんが国際会議TAMC2025において発表を行いました。この論文はBest Paper Awardを受賞しました。（2025/9/20）

  • Shota Ikeda, Kazumasa Shinagawa, "How to Play Mastermind without Game Master"

• M2の本多由昂さんの論文が論文誌IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciencesに採録されました。（2025/9/4)

  • Yoshiaki Honda and Kazumasa Shinagawa, "Efficient Card-Based Protocols with a Standard Deck of Playing Cards Using Partial Opening"

• M1の池田昇太さんが国際会議APKC2025において発表を行いました。（2025/8/26）

  • Kazuhiro Fujita, Shota Ikeda, Kazumasa Shinagawa, Kazuki Yoneyama, "Formal Verification and Proof of Impossibility for Four-Card XOR Protocols Using Only Random Cuts"

• 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プロトコルに対する形式検証と不可能性証明"

  • 本多由昂, "部分開示操作を用いた効率的なカードベースプロトコル"

• B4の黒木竜馬さんと藤原愛斗さんと本間日綺さんの3名が米山研究室の物理暗号Gに配属されました。（2025/4/1）

• 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の本多由昂さんが令和６年度学生表彰者に選ばれました。（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の佐々木駿さんと高橋由紘さんが令和５年度学生表彰者に選ばれました。（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の南川侑太さんが令和４年度学生表彰者に選ばれました。（2023/3/7）

• B4の佐々木駿さんと高橋由紘さんが2023年 暗号と情報セキュリティシンポジウム（SCIS2023)において発表を行いました。

  • 高橋 由紘, 品川 和雅, "正多角形カードを用いた投票プロトコル"

  • 佐々木 駿, 品川 和雅, "数コロに対する物理的ゼロ知識証明プロトコル"

• B4の南川侑太さんがコンピュータセキュリティシンポジウム2022（CSS 2022）において発表を行いました。この論文はCSS2022奨励賞を受賞しました。（2022/10/24）

  • 南川 侑太, 品川 和雅, "ハンド操作を用いないコインベースプロトコル"

• B4の佐々木駿さん、高橋由絋さん、南川侑太さんの3名が品川研究室に配属されました。（2022/4/1）