ゲートあたり6枚で実行できる
カードベースガーブルド回路
電気通信大学小野 知樹

2024/05/22

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

1カードベース暗号[Boer89]⚫ 計算機ではなく，物理的なカードを用いた計算
 秘密計算，ゼロ知識証明⚫ 全ての操作は公開で行う

45

3

2

1

[Boer89] B. den Boer, “More efficient match-making and satisfiability: The Five Card Trick,” EUROCRYPT,
1989
2024/05/22

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

2

秘密計算
⚫ データを暗号化したまま計算できる技術
 例：2者のうちどちらがお金持ちであるかを比較したいが自身の資産は知られたくない⚫ 今回の目標は任意の論理回路（関数）に対する秘密計算

𝒂𝒃

Alice
2024/05/22

𝑎, 𝑏を秘匿しつつ𝑓(𝑎, 𝑏)を計算
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

Bob3

任意の論理回路に対する秘密計算⚫ 任意の論理回路：任意の計算機上で計算できる関数（公開）⚫ 互いの入力と計算途中の値（中間値）を秘匿しつつ出力を得る
 AND，XOR，NOTを計算することができればよい✓ 任意の論理回路はAND，XOR，NOTの組み合わせ
 出力は秘匿しつつ次の入力として用いることができる必要がある

例： (𝑏1 ∧ 𝑎1 ) ∧ (𝑎2 ⨁𝑏2 )を計算する論理回路
𝑏1
AND
𝑎1
AND
𝑎2
XOR
𝑏2
2024/05/22

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

4シャッフル操作⚫ 実行したプレイヤを含めプレイヤ全員が乱数を知らない並び替え 公開の場で行うため不正はできない⚫ ランダマイズのために必要⚫ 実行に課題

2024/05/22

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

5

今回のプロトコルで用いるカード⚫ 2種カード(表：裏：)⚫ 同じ模様のカードは見分けられず，裏面同士も見分けられない 裏面からは表面が一切わからない 裏返してシャッフルすると全てのプレイヤにカードの表面のマークがわからなくなる

入力

操作

入力
BobAlice
出力2024/05/22

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

6カードベース暗号の効率指標と目標⚫ カードベース暗号の効率指標は以下の二つ
 シャッフル回数：少ないほど良い カード枚数：少ないほど良い⚫ 目標：シャッフル回数を最小化（１回に）しつつ、カード枚数が少ないプロトコルの構成
 実行を容易にするため
 シャッフル回数は０回にはできない [SN21]✓ 入力が漏れないようにするため----------------------------------------------------------------------------------------------------------------------------------------------------------------------[SN21]

2024/05/22

K. Shinagawa, and K. Nuida. “A single shuffle is enough for secure card-based computationof any Boolean circuit.,” Discrete Applied Mathematics, 2021.
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

7ガーブルド回路アプローチ
任意の論理回路に対するカードベース暗号プロトコル

構成方法

ガーブルド回路アプローチ
AND, XOR, NOTプロトコルを[SN21][TMM23], [KS23],組み合わせるアプローチ（主流）[OSN+23]
プロトコルの出力をガーブルド回路を再現次のプロトコルの入力とする

シャッフル回数多い (ゲート数に応じて増える)

少ない (1回)

カード枚数少ない多い[SN21] K. Shinagawa, and K. Nuida. “A single shuffle is enough for secure card-based computation of any Boolean circuit.,”Discrete Applied Mathematics, 2021.
[TMM23] K. Tozawa et al. “Single-shuffle card-based protocol with eight cards per gate.,” UCNC, 2023.
[KS23] Y. Manabe, K. Shinagawa: Free-XOR in Card-Based Garbled Circuits. CANS 2023: 232-248[OSN+23] T. Ono et al. “Single-Shuffle Card-Based Protocols with Six Cards per Gate.,” ICISC, 2023.
2024/05/22

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

8コミット型，非コミット型⚫ コミット型
 広義には入力と出力の符号化ルールが同じもの
 狭義には入力と出力の符号化ルールが次のようなもの

01
 プロトコルを組み合わせやすい⚫ 非コミット型
 入出力が上のような符号化ルールではないもの
 効率が良くなりやすい
2024/05/22

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

9シャッフル1回のプロトコル⚫ 任意の論理回路に対するプロトコルのカード枚数を削減
𝑞 は計算対象の論理回路のゲート数, 𝑛, 𝑚は入出力ゲート数
コミット型

シャッフルの種類

プロトコル

カード枚数

Shinagawa-Nuida [SN21]

24𝑞 + 2𝑛一様閉Tozawaら [TMM23]

8𝑞 + 2𝑛一様閉

Onoら[OSN+23]

6𝑞 + 2𝑛一様

Onoら[OSN+23]

6𝑞 + 2𝑛 + 2𝑚

一様他にManabe-Shinagwa[KS23]らのプロトコルが存在
ゲートの種類がわかっている条件でXORのカード枚数を減らす
2024/05/22

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

10

1ゲート8枚のプロトコル-準備⚫ 符号化に従って，入力やゲートをカードで表す

符号化0 入力は秘密裏に作成し，裏向き⚫ NOTは左右のカードを入れ替えることで用意しておく 1AND

𝑏1 = 0𝑎1 = 110

𝑏1000

101

𝑎1

𝑎2

𝑏20101
𝑎2

XOR

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

11プロトコルの方針⚫ 目的：入力と中間値を秘匿しつつ出力を得る

出力のみ分かる 準備したカードを裏返して上手にシャッフルしてから上手にめくる

入力と中間値を秘匿し，かつ出力が変わらないシャッフル
𝑏1
符号化
入力

ゲート

𝑎101010001𝑎2𝑏22024/05/22

101101

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

12プロトコルが出力を得る方法⚫ 入力に対応する場所のカードを表にすることを繰り返す
 最後のゲートのカードが表す値が出力
 上手いシャッフルと組み合わせることで出力のみ明らかにする⚫ 例：対象の論理回路( 𝑏1 ∧ 𝑎1 ) ∧ ( 𝑎2 ⊕ 𝑏2 )𝑏1

 (𝑎1 , 𝑎2 , 𝑏1 , 𝑏2 )＝(1,0,1,1) 𝑎1

符号化
入力

ゲート

2024/05/22

𝑏2101𝑎201000110101

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

13

入力の秘匿（ビット反転）と出力の維持⚫ 入力の秘匿（カードは裏返しておく）
 入力を表す2枚のカードをシャッフル⚫ 出力を維持（カードは裏返しておく）
 入力の秘匿に合わせてゲートのカードをシャッフル

上側の入力

下側の入力
符号化
入力

ゲート

0100001112024/05/22

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

114中間値の秘匿（ビット反転）と出力の維持⚫ 中間値の秘匿（カードは裏返しておく）
 中間値を表すカードを対応させてシャッフル⚫ 出力を維持（カードは裏返しておく）
 中間値の秘匿に合わせてゲートのカードをシャッフル

01002024/05/22

10𝑎2

1𝑏21

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

15プロトコルの出力⚫ ゲートの入力に対応するカードを表向きにする⚫ 入力の値に対応するゲートのカードを表向きにする
 表向きの入力や中間値のカードはシャッフルされたので値は秘匿符号化
入力ゲート

𝑏1𝑎101010101𝑎2𝑏2

2024/05/22

1001

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

16連続するシャッフルはまとめられる[MS14]⚫ シャッフル間でカードを表にしなければ，それらのシャッフルは１回にまとめられる シャッフルは置換の集合とそれ上の置換の分布からなる（ともに任意）
 置換は合成でき，分布を選ぶことができる⚫ 1ゲート8枚のプロトコルのシャッフルは連続なのでまとめられる[MS14]T. Mizuki and H. Shizuya, “A formalization of card-based cryptographic protocols via abstractmachine,” Int. J. Inf. Sec., 2014
2024/05/22

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

17

1ゲート8枚のプロトコルの具体例-準備⚫ 対象の論理回路 ( 𝑏1 ∧ 𝑎1 ) ∧ ( 𝑎2 ⊕ 𝑏2 )⚫ (𝑎1 , 𝑎2 , 𝑏1 , 𝑏2 )＝(1,0,1,1)とするが本人のみ分かる．裏向きでおく
𝑏1

100𝑎11010𝑎200𝑏22024/05/22

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

18

1ゲート8枚のプロトコル-シャッフル⚫ 出力以外はランダムにビット反転される⚫ 連続しているシャッフルのなのでまとめると理論上１回で行える
𝑏1

100

𝑎1

10

10
𝑎200𝑏22024/05/22

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

19プロトコルの出力⚫ ゲートの入力に対応するカードを表向きにする
𝑏1
𝑎100
12024/05/22

0101𝑎2𝑏2

101

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

20

1ゲートあたり8枚のプロトコルを紹介した⚫ 任意の論理回路に対するシャッフル１回のプロトコル𝑞 は計算対象の論理回路のゲート数, 𝑛, 𝑚は入出力ゲート数

コミット型

シャッフルの種類

プロトコル

カード枚数

Shinagawa-Nuida [SN21]

24𝑞 + 2𝑛

一様閉

Tozawaら [TMM23]

8𝑞 + 2𝑛一様閉

Onoら[OSN+23]

6𝑞 + 2𝑛一様

Onoら[OSN+23]

6𝑞 + 2𝑛 + 2𝑚

一様他にManabe-Shinagwa[KS23]らのプロトコルが存在
ゲートの種類がわかっている条件でXORのカード枚数を減らす
2024/05/22

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

21

1ゲートあたり6枚のプロトコル-アイデア⚫ 1ビットを1枚で符号化
AND0

101

符号化

XOR010101⚫ 次の二つの２入力1出力のゲートは特別な方法で符号化する
常に0を出力

常に1を出力001
2024/05/2210101
産学連携と数理・暗号分野連携によるカードベース暗号の深化と新境地

22

1ゲートあたり6枚のプロトコル-準備符号化⚫ 符号化に従って，入力やゲートをカードで表す

入力⚫ ゲートの種類は公開 1ゲートあたり6枚（任意の2入力１出力ゲートを作れる）
 1入力あたり2枚

𝑏1 = 0𝑎1 = 1100 001 01

𝑏100110𝑎11𝑎2𝑎2𝑏2𝑏22024/05/22

ゲート

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

23プロトコルの方針⚫ 目的：入力と中間値を秘匿しつつ出力を得る

出力のみ分かる 準備したカードを裏返して上手にシャッフルしてから上手にめくる

入力と中間値を秘匿し，かつ出力が変わらないシャッフル
𝑏1
符号化
入力ゲート

𝑎10101001𝑎2𝑏22024/05/22

0110101

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

24プロトコルが出力を得る方法⚫ 入力に対応する場所のカードを表にすることを繰り返す
 最後のゲートのカードが表す値が出力⚫ 上手いシャッフルと組み合わせることで出力のみわかる⚫ 例：対象の論理回路

𝑏1( 𝑏1 ∧ 𝑎1 ) ∧ ( 𝑎2 ⊕ 𝑏2 )𝑎1 = 1, 𝑎2 = 0, 𝑏1 ＝1, 𝑏2 ＝1 𝑎1
符号化

入力

ゲート

2024/05/22

𝑏2101𝑎20
1000110101

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

25

入力の秘匿と出力の維持⚫ 入力の秘匿（カードは裏返しておく）
 入力を表す2枚のカードをシャッフル⚫ 出力を維持（カードは裏返しておく）
 入力の秘匿に合わせてゲートのカードをシャッフル

符号化
入力012024/05/22

ゲート

𝑏101𝑏10𝑎1

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

126中間値の秘匿（ビット反転）と出力の維持
余りのカードを使える！

⚫ 中間値の秘匿（カードは裏返しておく）

 中間値を表すカードをゲートの種類に合わせてシャッフル⚫ 出力を維持（カードは裏返しておく）
 中間値の秘匿に合わせてゲートのカードをシャッフル

𝑏101

𝑏1

1

𝑎1𝑎2𝑎2𝑏2𝑏22024/05/22

100𝑎101

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

27

シャッフルの順番⚫ 出力側のシャッフルを先に行う
 例：青緑のシャッフルを先に行う⚫ 閉じていない
𝑏1

𝑎100
1

𝑎2𝑏22024/05/22

1001

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

28

プロトコルの出力⚫ 入力に対応するカードを表向きにする⚫ 入力の値に対応するゲートのカードを表向きにする
 表向きの入力や中間値のカードはシャッフルされたので値は秘匿

符号化
入力
01ゲート

𝑏1𝑎1101𝑎2𝑏22024/05/22

000110101

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

29

1ゲート6枚のプロトコルの具体例-準備𝑏1𝑎1001𝑎2𝑏22024/05/22

1001

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

30

シャッフル⚫ 連続しているシャッフルなのでまとめられる

𝑏1
𝑎1001𝑎2𝑏22024/05/22

1001

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

31プロトコルの出力⚫ 入力に対応するカードを表向きにする⚫ 入力の値に対応するゲートのカードを表向きにする．

符号化
入力
01ゲート

𝑏1𝑎1101𝑎2𝑏22024/05/22

000

1

10101

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

32コミット型への変形⚫ 最後のゲートを１ゲート8枚のプロトコルに置き換え

𝑏1
𝑎100
1

𝑎2𝑏22024/05/22

100

1

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

33

1ゲートあたり6枚のプロトコルを紹介した⚫ 任意の論理回路に対するプロトコルのカード枚数
𝑞は計算対象の論理回路のゲート数, 𝑛, 𝑚は入出力ゲート数

コミット型

シャッフルの種類

プロトコル

カード枚数

Shinagawa-Nuida [SN21]

24𝑞 + 2𝑛

一様閉

Tozawaら [TMM23]

8𝑞 + 2𝑛一様閉

Onoら[OSN+23]

6𝑞 + 2𝑛一様

Onoら[OSN+23]

6𝑞 + 2𝑛 + 2𝑚

一様他にManabe-Shinagwa[KS23]らのプロトコルが存在
ゲートの種類がわかっている条件でXORのカード枚数を減らす
2024/05/22

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

34