高機能暗号について

岡本 龍明
NTT 社会情報研究所
July 26, 2023

1

もし共通鍵暗号しかないとするとインターネットの安全性をどのように守るか？
信頼できるクラウドサービスを利用してさまざまなセキュリティ機能を実現• 秘匿通信サービス• 認証・署名サービス• 秘密計算サービス• データベースサービスetc2

秘匿通信サービス（基本）
秘匿通信サービス・サーバ
利用者との間の通信はすべて共通鍵暗号で暗号化（各利用者との間の秘密鍵はサービス契約時に設定）
暗号化
利用者２へのメッセージM

利用者１

暗号化
利用者１からのメッセージM

利用者２

利用者ｎ

3

秘匿通信サービス（応用1）
秘匿通信サービス・サーバ
利用者との間はすべて共通鍵暗号で暗号化（各利用者との間の秘密鍵はサービス契約時に設定）
利用者の属性などの情報を保持
暗号化
属性( X or Y)をもつ利用者へのメッセージM

利用者１

暗号化
利用者１からのメッセージM

利用者２
属性Xをもつ暗号化
利用者１からのメッセージM

利用者ｎ
属性Yをもつ4

秘匿通信サービス（応用2）
秘匿通信サービス・サーバ
利用者との間はすべて共通鍵暗号で暗号化（各利用者との間の秘密鍵はサービス契約時に設定）
利用者のIDなどの情報を保持

暗号化
利用者nからのメッセージM

利用者 ID1

利用者 ID3

暗号化
ID1, ID3, … の利用者へのメッセージM

利用者ｎ5

認証・署名サービス（基本）認証・署名サービス・サーバ
利用者との間はすべて共通鍵暗号で認証(MAC)（各利用者との間の秘密鍵はサービス契約時に設定）(文書M1, 利用者１）を署名文書データベースに登録
MAC付（利用者１，文書M1）の署名検証依頼

文書M1の署名登録

利用者１

利用者２

署名文書データベース

MAC付
署名検証結果

利用者ｎ

6

認証・署名サービス（応用1）
認証・署名サービス・サーバ
利用者との間はすべて共通鍵暗号で認証(MAC)（各利用者との間の秘密鍵はサービス契約時に設定）
各利用者が所属するグループなどを保持
MAC付（グループ１, M1）を署名文書データベースに登録
MAC付

グループ１のメンバとして
文書M1の署名登録

利用者１

署名文書データベース(グループ１, 文書M1)の署名検証依頼

利用者２

署名検証結果利用者ｎグループ１に所属
7

認証・署名サービス（応用２）
認証・署名サービス・サーバ
利用者との間はすべて共通鍵暗号で認証(MAC)（各利用者との間の秘密鍵はサービス契約時に設定）

署名文書データベース( (利用者1, …,10), M1）を署名文書データベースに登録
MAC付（利用者1, …,利用者10）の一人として文書M1の署名登録

利用者１

利用者２

（利用者1, …,利用者10）の誰かが 文書M1の署名者であるか検証依頼

MAC付
署名検証結果

利用者ｎ8

認証・署名サービス（応用３）
認証・署名サービス・サーバ
利用者との間はすべて共通鍵暗号で認証(MAC)（各利用者との間の秘密鍵はサービス契約時に設定）

MAC付

各利用者の属性情報を保持(属性 (X or Y), M1）を署名文書データベースに登録

属性 (X or Y) をもつ利用者として文書M1の署名登録

利用者１

署名文書データベース

属性 (X or Y)をもつ利用者が 文書M1の署名者である
か検証依頼
利用者２

MAC付
署名検証結果

利用者ｎ

属性Xをもつ9秘密計算サービス
秘密計算サービス・サーバ
利用者との間はすべて共通鍵暗号で暗号化（各利用者との間の秘密鍵はサービス契約時に設定）
f(x1, x2, .., xn) を計算
暗号化

秘密 x1

暗号化

秘密 x2

暗号化

秘密 xn

利用者１

利用者２

利用者ｎ

x1

x2

xn

暗号化

計算結果 f(x1, x2, .., xn){利用者i }

10

データベースサービス
データベースサービス・サーバ
利用者との間はすべて共通鍵暗号で暗号化
アクセス制御（各利用者との間の秘密鍵はサービス契約時に設定）(DBMS)
検索依頼（データa1）に対して利用者属性 q1 がアクセス条件 f1を満足するか？

データベース

暗号化

利用者属性 q1,
検索依頼

利用者１

検索結果 a1
利用者２

利用者ｎ

11

クラウドサービスによるアプローチの問題点• クラウドに信頼性を含めてすべての機能・権限が集中（サービスが正しく機能するかは、クラウドの動作の正しさに全面的に依存。
すべての利用者のプライバシー情報はクラウドが保有）
集中／中央集権(centralized)
 分散／非中央集権(decentralized)• クラウドに負荷が集中（非効率）
 効率化

高機能暗号
12

高機能暗号• 秘匿通信ービス  （公開鍵暗号）、プロキシ暗号、再暗号化、属性べース暗号、検索可能暗号、放送型暗号• 認証・署名サービス  （ディジタル署名）、グループ署名、リング署名、しきい値署名、属性ベース署名• 秘密計算サービス  多者秘密計算、準同型暗号、ゼロ知識証明• データベースサービス  属性ベース暗号、PIR (Private Information Retrieval) 、Oblivious RAM
etc
13高機能暗号の例１：認証・署名サービス（権限の集中）
認証・署名サービス・サーバ
利用者との間はすべて共通鍵暗号で認証(MAC)（各利用者との間の秘密鍵はサービス契約時に設定）
署名文書データベース
権限が集中( (利用者1, …,10), M1）を署名文書データベースに登録
MAC付（利用者1, …,利用者10）の一人として文書M1の署名登録

利用者１

利用者２

（機能・プライバシーはサーバの信頼性に依存）（利用者1, …,利用者10）,の誰かが 文書M1の署名者であるか検証依頼

MAC付
署名検証結果

利用者ｎ14

高機能暗号の例１：リング署名

公開鍵１
利用者１

（秘密鍵1, …,秘密鍵10）のどれか一つの秘密鍵を用いて文書M1に対する署名を作成

秘密鍵１

公開鍵2, .., 公開鍵10（非中央集権化）

公開鍵２
利用者２（公開鍵1, …,公開鍵10）を用いて 文書M1の署名検証（どの秘密鍵が使われたか、誰が署名者かは分からない）
利用者ｎ

秘密鍵２15

高機能暗号の例２：データベースサービス（権限の集中）
データベースサービス・サーバ
利用者との間はすべて共通鍵暗号で暗号化
アクセス制御（各利用者との間の秘密鍵はサービス契約時に設定）(DBMS)
検索依頼（データa1）に対して利用者属性 q1 がアクセス条件 f1を満足するか？権限が集中（機能・プライバシーはサーバの信頼性に依存）

暗号化

利用者属性 q1,
検索依頼

利用者１

データベース

検索結果 a1
利用者２

利用者ｎ16

高機能暗号の例２：属性ベース暗号（非中央集権化）
データベース（暗号化）
暗号文 cを登録
Alicec = Enc(mpk, f1, a1)（条件式 f1 をパラメータとしてデータ a1 を暗号化）

c を検索

秘密鍵 sk 𝑞𝑞1（ q1 はBobの属性）

Bob

a1 = Dec(sk 𝑞𝑞1 , c)（f1(q1) =1 ならば復号可）
17

研究課題
• 耐量子高機能暗号（例：LWE/SIS仮定ベース高機能暗号）• 新しい機能への拡張（例：ブロックチェーンへの応用、Adaptor署名）• 非中央集権化の推進（例：DMA-ABE/ABS)18

非中央集権化の推進：（例）属性ベース暗号・署名（基本形）
mpk 公開mpk

マスター公開鍵: mpk
マスター秘密鍵: msk
管理者

権限が集中
（管理者が全利用者skv
属性 vの秘密鍵を保持）

ダウンロードAlice
暗号文 cc = Enc(mpk, f, m)（f: 条件式, m: 平文）

Bobm = Dec(skv,c)（f(v) = 1 を満足すれば復号可） 19

非中央集権化の推進：（例）DMA (非中央集権多管理者）属性ベース暗号・署名
各管理者は完全に独立

公開

mpk1
公開

マスター公開鍵: mpk1
マスター秘密鍵: msk1

マスター公開鍵: mpk2
マスター秘密鍵: msk2

mpk2

管理者１

管理者2

属性 v1

ダウンロード
（例）
A大学

Alice
Ver(mpk1, …, mpkt , f, m, s) = 1
f(v1 , v2, …, vt) = 1 を満足する属性をもつ
署名者による署名であることを検証

属性 v2

skv2

（例）
A大学文学部
教授

署名 s, 文書 m, 関係式 f

（例）
日本国籍
年齢 etc.

（例）
日本政府

skv1

Bobs = Sig(sk, f, m)
f(v1 , v2, …, vt) = 1 を満足すれば署名可,sk ⊆{skv1,skv2,.., skvt}

20

非中央集権化の推進：（例）DMA属性ベース署名はリング署名の一般化
f(v1 , v2, …, vt) = (v1 = pk1) ∨ (v2 = pk2) ∨ … ∨ (v2 = pk10)のときはリング署名

公開

pk1

pk2

pk10

公開

公開鍵: pk10
秘密鍵: sk10

公開

公開鍵: pk1
秘密鍵: sk1
公開鍵: pk2
秘密鍵: sk2

利用者１（管理者１）

利用者2（管理者2）

利用者10（管理者１0）21

研究課題• 耐量子高機能暗号（例：LWE/SIS仮定ベース高機能暗号）• 新しい機能への拡張（例：ブロックチェーンへの応用、 Adaptor署名）• 非中央集権化の推進（例：DMA-ABE/ABS)• 利便性・性能向上・応用の進展（例：zk-SNARK, Doubly Efficient PIR)

22

利便性・性能向上・応用の進展：（例）ゼロ知識証明•標準モデルでは、ゼロ知識証明は対話（4回以上）を必要とする。
検証者 V

証明者 P
•
•

非対話ゼロ知識証明（非標準モデル）において、標準的な仮定の下では証明サイズをある程度以上小さくできない。
非標準的なモデル／仮定（CRS（共通参照情報）をシステムで共有するモデルやジェネリック群モデルなど）では、非対話で非常に効率的な（証明サイズが小さい）ゼロ知識証明が可能。ブロックチェーンなどで利用。
（例） zk-SNARK (Succinct Non-interactive ARgument of Knowledge)
証明のサイズが命題のサイズにかかわらず固定で非常に短い（例：群要素３つ）
CRS
証明者 P

非常に短い証明

検証者 V

23

研究課題
• 耐量子高機能暗号（例：LWE/SIS仮定ベース高機能暗号）• 新しい機能への拡張（例：ブロックチェーンへの応用、 Adaptor署名）• 非中央集権化の推進（例：DMA-ABE/ABS)• 利便性・性能向上・応用の進展（例：zk-SNARK , Doubly Efficient PIR)
• 量子高機能暗号（例：量子マネー etc）

24

まとめ
• 高機能暗号： 様々なクラウドサービス（秘匿通信、認証・署名、秘密計算、データベースなど）に対して非中央集権化した効率的な解決策を提供• 研究課題：o 耐量子高機能暗号
o 新しい機能への拡張
o 非中央集権化の推進
o 利便性・性能向上・応用の進展
o 量子高機能暗号25