⼀様巡回群分解に基づく
⼀様閉シャッフルの実現⽅法とその応⽤
2024年5⽉22⽇
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地
品川 和雅（茨城⼤）
本研究は⾦井和貴⽒ (呉⾼専)、宮本賢伍⽒ (茨城⼤)、縫⽥光司⽒ (九州⼤) との共同研究
1

本講演の概要• ⼀様巡回群分解（有限群の分解の⼀種）という概念の提案• ⼀様巡回群分解のカードベース暗号への応⽤• 論⽂情報• Uniform cyclic group factorizations of ﬁnite groups (Commu. Alg. 2023)• Kazuki Kanai, Kengo Miyamoto, Koji Nuida, Kazumasa Shinagawa• 概要：「⼀様巡回群分解」の定義と基本性質の証明• How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik's Cube (FUN 2024)• Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto and Koji Nuida• 概要：「⼀様巡回群分解」のカードベース暗号への応⽤
2

⽬次• イントロダクション• ⼀様巡回群分解（UCF）について(Comm. Alg.の結果)• 応⽤：⼀様閉シャッフルの実装(Comm. Alg.の結果 + FUNの結果)• 応⽤：パズルの秘匿ランダムインスタンス⽣成(FUNの結果)

3

Mizuki-Shizuyaモデルにおける操作• (perm, 𝜋)：𝜋 ∈ 𝑆!
• 置換𝜋で並び替える操作• (turn, 𝑇)：𝑇 ⊆ 1,2, … , 𝑛• カードをめくる操作• (shuf7le, Π, ℱ)︓ℱはΠ(⊆ 𝑆! )上の確率分布• 置換π ← ℱで並び替える操作• どの𝝅が選ばれたかは秘匿される必要がある

シャッフルを安全に実装する⽅法は⾃明ではない
4

Practicalなシャッフルたち• ランダムカット (RC)：ランダム巡回シフト• 実装⽅法：ヒンズーカット、コマ• ランダム⼆等分割カット(RBC)：⼆束のランダム巡回シフト• 実装⽅法：封筒＋ランダム交換、コマ• パイルシフティングシャッフル(PShift)：𝑘束のランダム巡回シフト• 実装⽅法：封筒＋ヒンズーカット、コマ• 完全シャッフル(CS)：ランダム置換• 実装⽅法：かき混ぜる• パイルスクランブルシャッフル(PScramble)：𝑘束のランダム置換• 実装⽅法：封筒＋かき混ぜる• これらの共通点：ランダム巡回シフトまたはランダム置換
5本研究の出発点• 巡回群シャッフル• 置換𝜋を⼀様ランダムな回数だけ適⽤するシャッフル• すなわち、⼀定の操作を繰り返すことによって実装されるシャッフル• RC/RBC/PShiftは巡回群シャッフルの⼀種• どのようなシャッフルたちが巡回群シャッフルから実現されるか？

6

本研究の成果• ⼀様巡回群分解（Uniform Cyclic group Factorization: UCF）という新しい種類の有限群の分解を提案• この概念⾃体は、純粋に有限群論的な概念• 応⽤①：⼀様閉シャッフルの巡回群シャッフルによる実装• ⼀様閉シャッフル： Πが群で、ℱが⼀様分布のシャッフル• 巡回群シャッフルは⼀様閉シャッフルの特別な場合• 応⽤②：パズルの秘匿ランダムインスタンス⽣成• ルービックキューブ＆15パズルに対して適⽤
7

⽬次• イントロダクション• ⼀様巡回群分解（UCF）について(Comm. Alg.の結果)• 応⽤：⼀様閉シャッフルの実装(Comm. Alg.の結果 + FUNの結果)• 応⽤：パズルの秘匿ランダムインスタンス⽣成(FUNの結果)

8

⼀様巡回群分解 (UCF)の定義• 群𝐺の部分群の列𝐻 = (𝐻! , 𝐻" , … , 𝐻# )が𝐺の⼀様群分解であるとは、
𝐻! 𝐻" ⋯ 𝐻# ≔ ℎ! ℎ" ⋯ ℎ# ℎ$ ∈ 𝐻$を多重集合（重複を許す集合）としたとき、以下を満たすこと• 𝐻! 𝐻" ⋯ 𝐻# に𝐺のすべての元が現れること• その重複度が⼀定であること（i.e. すべての元が同じ個数出現）• 𝐻! たちが巡回群のとき⼀様巡回群分解 (UCF)という9UCFの例• 対称群𝑆% のUCFの例(𝐻! , 𝐻" )• 𝐻! = 1,2 = 𝑒, 1,2• 𝐻" = 1,2,3 = 𝑒, 1,2,3 , 1,3,2• 𝐻! 𝐻" = 𝑒, 1,2 , 1,2,3 , 1,2 1,2,3 , 1,3,2 , 1,2 1,3,2= 𝑒, 1,2 , 1,2,3 , 2,3 , 1,3,2 , 1,3 = 𝑆%
• 交代群𝐴& のUCFの例(𝐻! , 𝐻" , 𝐻% )• 𝐻! = 1,2 3,4 = 𝑒, 1,2 3,4• 𝐻" = 1,3 2,4 = 𝑒, 1,3 2,4• 𝐻% = 2,4,3 = 𝑒, 2,4,3 , 2,3,410

⽬次• イントロダクション• ⼀様巡回群分解（UCF）について(Comm. Alg.の結果)• 応⽤：⼀様閉シャッフルの実装(Comm. Alg.の結果 + FUNの結果)• 応⽤：パズルの秘匿ランダムインスタンス⽣成(FUNの結果)

11

⼀様閉シャッフルの分解• 定理：群𝐺が⻑さ𝑘のUCF(𝐻! , 𝐻" , … , 𝐻# )を持つとする。
このとき、⼀様閉シャッフル(shuf7le, 𝐺)は𝑘個の巡回群シャッフル
shuf7le, 𝐻# , … , shuf7le, 𝐻" , shuf7le, 𝐻!に分解できる（逆順の理由は、置換の作⽤を ℎ!ℎ" 𝑥 ≔ ℎ!(ℎ" 𝑥 )としているため）
︖ ︖ ︖ ︖ ︖

︖ ︖ ︖ ︖ ︖

(shuf'le, 𝐺)≈(shuf'le, 𝐻! )︖ ︖ ︖ ︖ ︖

(shuf'le, 𝐻" )︖ ︖ ︖ ︖ ︖

︖ ︖ ︖ ︖ ︖

12

例：完全シャッフルの分解• 対称群𝑆, はUCF(𝐻, , 𝐻,-! , … , 𝐻" )を持つ• 𝐻! ≔ (1 2 3 ⋯ 𝑛)
• 𝐻!"# ≔ (1 2 3 ⋯ 𝑛 − 1)
• 𝐻$ ≔ (1 2)• 完全シャッフル(shuf7le, 𝑆, )は𝑛 − 1回のRCに分解できる

13

どのような群がUCFを持つか？
• 現状わかっていること• 任意の可解群は⼀様群分解を持つ• 可解群の例：アーベル群 (可換群)、対称群𝑆%, 𝑆&、奇数位数の群• もし任意の単純群が⼀様群分解を持てば、任意の群はUCFを持つ• UCF予想：任意の群はUCFを持つ• YES ⟹ 任意の⼀様閉シャッフルは巡回群シャッフルで実装可能
14

⽬次• イントロダクション• ⼀様巡回群分解（UCF）について(Comm. Alg.の結果)• 応⽤：⼀様閉シャッフルの実装(Comm. Alg.の結果 + FUNの結果)• 応⽤：パズルの秘匿ランダムインスタンス⽣成(FUNの結果)

15

シナリオ
• パズルの早解き競争は世界的に⼈気の競技である• スピードキュービング
• 世界パズル選⼿権• 世界数独選⼿権• スピードキュービングのインスタンス⽣成⽅法
1. ソフトウェアを⽤いてスクランブル⼿順を⽣成（PCが実⾏）
2. スクランブラという役割の⼈が⼿順を実⾏する（⼈間が実⾏）• 課題：PCと⼈間への信頼/負担を軽減できないか？
16

インスタンス⽣成に関する課題• スクランブラに対してもインスタンスを秘匿できないか？
• 現状、スクランブラはインスタンスを事前に知ってしまう• そのためスクランブラは競技に参加できない• コンピュータを⽤いずにインスタンス⽣成はできないか？
• 現状、スクランブル⼿順はコンピュータによって⽣成する• しかしコンピュータの動作の正しさの検証は必ずしも容易ではない

秘匿かつ⼀様ランダムなインスタンスを物理的に⽣成するには？
我々のアプローチ：UCFに基づくインスタンス⽣成
17

15パズルの場合

18

⾃明な⽅法とその問題点• ⾃明な⽅法• 裏向きに伏せて⼀様ランダムに混ぜる• 競技開始と同時にオモテにする• 問題点• 50%の確率で解が存在しない
解なし：奇置換(14,15)

解あり：偶置換(11,15,12)

交代群𝑨𝟏𝟓 の⼀様閉シャッフルを実装できればよい19交代群シャッフルの実現⽅法• 定理：𝐴, シャッフルは𝑛 = 2𝑚のときは3𝑚 − 3回、 𝑛 = 2𝑚 + 1のときは3𝑚 − 2回のRC/RBC/PShiftに分解できる
1.

RC： (1 2 3)

11. RBC： (1 6)(5 10)

2.

RBC： (1 3)(2 4)

12. PShift： (1 2 3 4 5)(6 7 8 9 10)

3.

RBC： (1 2)(3 4)

13. RC： (1 2 3 4 5 6 7 8 9 10 11)

4.

RC： (1 2 3 4 5)

14. RBC： (1 7)(6 12)

5.

RBC： (1 4)(3 6)

15. PShift： (1 2 3 4 5 6)(7 8 9 10 11)

6.

PShift： (1 2 3)(4 5 6)

16. RC： (1 2 3 4 5 6 7 8 9 10 11 12 13)

7.

RC： (1 2 3 4 5 6 7)

17. RBC： (1 8)(7 14)

8.

RBC： (1 5)(4 8)18. PShift： (1 2 3 4 5 6 7)(8 9 10 11 12 13 14)

9.

PShift： (1 2 3 4)(5 6 7 8)

19. RC： (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)

10. RC： (1 2 3 4 5 6 7 8 9 10)20

ルービックキューブの場合

21

ルービックキューブのインスタンス⽣成• ⾃明な⽅法：分解して、バラバラなピースをシャッフル• デタラメに並び替えると、解無しの場合もある（15パズルと同様）• 壊れる/傷がつく可能性もある• ピースを外さない実装⽅法• ⽅法１：ルービックキューブの操作を⽤いてランダマイズする• ⽅法２：⾊シールをシャッフルして、最後に貼り付ける

22⽅法１：キューブ操作を⽤いる
1. 揃った状態のキューブを⽤意し、布でキューブを隠す
2. 布の中で⼿操作でランダマイズする

23

⽅法２：⾊シールをシャッフルする
1. 8枚×6⾊の⾊シールを⽤意する
8枚

8枚

8枚

8枚

8枚

8枚

…

…

…

…

…

…

…

…

…

2. 無⾊のカバーシールを貼る…

…

…

3. ルービックキューブ群シャッフルを適⽤する
4. キューブにシールを貼る
24ルービックキューブ群シャッフル（1/2）• ルービックキューブ群の群構造• 𝐺 = ℤ.%×ℤ##$ ⋊ (𝐴/ ×𝐴#$ ) ⋊ ℤ$ （⋊は半直積）• ⼀様巡回群分解：𝐺 = 𝐶#𝐶$𝐶% ⋯ 𝐶&%• ⽅法2（⾊シール）の場合：43回のRBC/PShift
1. RBC： (2 34)(4 10)
2. RBC： (2 34)(5 26)：
43. RBC： (2 4)(34 10)(1 3)(35 27)(9 33)• ⽅法1（キューブ操作）の場合：繰り返し操作によるシャッフル
25

ルービックキューブ群シャッフル（2/2）• 表記法：𝑅, 𝑈, 𝐵等は右⾯/上⾯/背⾯の回転、 𝑅′, 𝑈′, 𝐵′等は逆操作• 「操作列の繰り返しによるシャッフル」を43回適⽤する

1. 𝑅𝐿𝐹𝑈 " 𝐹 # 𝑅𝐿# 𝑈𝐵" 𝑈′𝐹 " 𝐿" 𝑈′𝐹 " 𝑅" 𝐵" 𝐷′
2. 𝑅𝑈𝑅# 𝑈′𝑅# 𝑈′𝑅𝑈𝑅𝐵# 𝑈′𝑅" 𝑈𝑅𝐵：

43. 𝑈 # 𝑅" 𝑈′𝑅" 𝐷𝑅" 𝐷′𝐹 " 𝑈𝐹 " 𝑅"
• 操作列は計算機代数システムGAPで求めた
26

まとめ• ⼀様閉シャッフルは巡回群シャッフルから実装可能• 位数の⼩さな群はすでにUCFの構成が得られているものが多い• ⼀⽅、位数の⼤きな単純群（例：モンスター群）のシャッフルが将来⽤いられる可能性もあるが、その巡回群シャッフルへの分解は未解決• 秘匿ランダムインスタンス⽣成問題は新しい研究分野• 興味のある⽅はぜひ参⼊していただけると嬉しいです• 未解決問題• UCF予想は成り⽴つか？
• 他のパズルに対する秘匿ランダムインスタンス⽣成27