ヘテロジニアス IoT システムにおける暗号プロトコルに関する研究
代表研究者

酒井 和哉

東京都立大学大学院システムデザイン研究科 准教授

1 要約
本研究では、多種多様な IoT 端末で構成される IoT システムにおいて、セキュリティを担保するための暗号プロトコルの開発に取り組んだ。具体的には、１）アセット RFID 電子タグを想定したセキュアかつゼロ知識の性質を持つ認証プロトコルと２）カメラセンサーなどから生成されるデータの完全性を担保するためのデータ検証プロトコルを開発した。提案手法は、シミュレーションによる性能評価と簡易プロトタイプ実装
による実験によって、それらの有効性を検証した。

2 RFID ゼロ知識認証プロトコル
本研究では、計算能力が非力な IoT 端末の一種であるアセット RFID を対象として、ゼロ知識認証プロトコルを開発した。平方剰余を応用した認証プロトコルを設計し、プロトコル実行中に秘密鍵に関するいかなる情報も漏洩しない手法を開発した。また安全性に関しては、ランダムオラクルを用いた識別不可能生を証明するとともに、シミュレータによってゼロ知識の性質を担保することを証明した。さらに提案手法をラズベ
リーパイに実装し、提案手法が認証に要する処理時間を計測した。
2-1 予備知識（１）平方剰余群𝔾について、𝑥 # = 𝑦 となるような要素𝑥 ∈ 𝔾が存在するとき、要素𝑦 ∈ 𝔾を平方剰余 (quadratic
residues) という。また素数𝑝を法としたアーベル群ℤ∗) について、𝑥 # = 𝑦 mod 𝑝 となるような要素𝑥 ∈ 𝔾が存在するとき、要素𝑦 ∈ 𝔾は平方剰余である。ℤ∗) 内の半分の要素が平方剰余であり、その部分集合を𝑄𝑅) と表す。素数𝑝を知っていれば、要素𝑦が平方剰余か否かを判定することは簡単であるが、複合モジュロの場
合は計算困難な問題となる。
整数𝑁を大きな素数の積𝑝 ⋅ 𝑞とする。このとき要素𝑦 ∈ ℤ∗4 は𝑦 mod 𝑝が𝑄𝑅) に含まれ、かつ𝑦 mod 𝑞が𝑄𝑅5に含まれるとき、𝑦は𝑄𝑅4 に含まれる。平方剰余の計算困難性は以下のように定義できる。
𝑁と𝑦、ℤ∗4 が与えられたとき、𝑦が𝑄𝑅4 に含まれるか否かを判定することは困難である。
（２）ゼロ知識証明
証明者𝑃が検証者𝑉に対して、プロトコルを介してある秘密情報を知っていることを証明するときに、秘密情報に関する情報をいっさい漏洩しないならば、そのプロトコルはゼロ知識であるという。正規または悪意のある検証者を𝑉8とする。𝑃と𝑉8がプロトコルを実行したときのトランスクリプト（プロトコル実行時に互いにやり取りしたメッセージのリスト）を𝑡𝑟;,=> (Π)とする。ここで、Πはプロトコルパラメータである。
本質的に𝑡𝑟;,=> (Π)は乱数のリストである。また𝑀C𝑉8, ΠDを多項式時間のプロトコルシミューレータとする。
シミュレータで生成されたトランスクリプトを𝑡𝑟E(=>,F) とする。
もしシミュレータが実際のプロトコル実行と同じ確率分布のトランスクリプトを生成できるならば、証明者𝑃を介さずに実際のプロトコルをシミュレーションできる。言い換えるとプロトコル実行時に秘密情報を使用せずにプロトコルをシミュレーションできるため、秘密情報が一切漏洩しない。このようなプロ
トコルをゼロ知識と呼ぶ。

1
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

2-1 関連研究（１）軽量 RFID 認証プロトコル
電子タグは計算能力が非力であるため、簡単なオペレーションだけで構成する暗号技術を用いる。ハッシュロック[2]と呼ばれる手法では、秘密鍵のハッシュ値を用いることで電子タグを認証する。システ
ム内の電子タグの数を𝑙とした場合、計算速度は𝑂(𝑙)となる。
大規模な RFID システムでは、効率的に電子タグを認証するために鍵構造を構造化し、𝑂(log 𝑙) の認証
速度を測る。これまでに２分木[3]やグループ構造[4]、スキップリスト[5]、スキップグラフ[6]、K 近
傍グラフ[7]を用いた鍵構造が提案されている。しかしながらこれらの手法は、それぞれの鍵が依存する
ため、一部の電子タグが危殆化されると、他の電子タグの安全性に影響する。
（２）平方剰余を用いた RFID 認証プロトコル
平方剰余を用いた RFID 認証プロトコルは、比較的計算能力が高いアセット電子タグを想定している。基
本的なアイディアは文献[8]で提案されているが、リプライ攻撃などの基本的な攻撃に対処できない。また
文献[9]で提案された手法は、なりすまし攻撃に対処できない。一方、文献[10]の手法では安全性の担保できるが、暗号プロトコルの性質上、正規の電子タグの認証に失敗することがある。
（３）ゼロ知識証明システム
ゼロ知識の概念が提案されたのは、秘密情報をいっさい漏洩させないインタラクティブな証明システ
ム [11]である。ゼロ知識の概念が RFID セキュリティ分野に適応されたのは文献[12]であるが、悪意のあるリーダに対してゼロ知識を保証するものではない。
したがって、悪意のあるリーダ（検証者）に対してゼロ知識の性質を持つ RFID 認証プロトコルは未だに報告されていない。
2-3 提案手法（１） 問題の定義
本研究において、IoT システムは図１に示すとおり、複数の電子タグとリーダ、サーバから構成される。それぞれ𝑇 = {𝑡M , 𝑡# , ⋯ , 𝑡O }と𝑅、𝑆と記述する。また攻撃者は、サーバとリーダ間、リーダと電子タグ間の通信データにアクセスすることができる。
各々の電子タグは、識別子𝑇𝐼𝐷T と𝑛-bit の秘密鍵𝑠𝑘T に関連付けられており、平方剰余の法を𝑁M = 𝑝M ⋅𝑞M並びに𝑁# = 𝑝# ⋅ 𝑞# とする。なお𝑁Mと𝑁#は公開鍵であるが、それらの因数は秘密情報として保管する。
暗号プリミティブとして、暗号論的ハッシュ関数𝐻: {0,1}∗ → {0,1}] を定義する。また𝐺𝑒𝑛と𝐸𝑛𝑐、𝐷𝑒𝑐をそれぞれ鍵生成アルゴリズムと暗号化アルゴリズム、復号化アルゴリズムとする。本研究で用いる暗号スキームをΠ ≔ (𝐺𝑒𝑛, 𝐸𝑛𝑐, 𝐷𝑒𝑐, 𝐻)とする。

図１. システムアーキテクチャ.

2
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

（２）攻撃モデル
本研究では、以下の攻撃を検討した。
•

盗聴（eavesdropping）：攻撃者は、電子タグとリーダ、サーバ間で送受信されるデータを得ること
ができる。

•

危殆化攻撃（compromise attacks）：攻撃者は、一部の電子タグを危殆化し、関連する秘密情報を得ることができる。

•

トレース攻撃（tracing attacks）：攻撃者は、複数のインテロゲーションをまたいで電子タグのリ
プライをトレースすることができる。

•

クローン攻撃（cloning attacks）：攻撃者は、電子タグのリプライをコピーし、異なるセッション
で当該電子タグのなりすましを行う。

•

中間者攻撃（man-in-the-middle）：攻撃者は、サーバと電子タグ間の通信データを仲介し、セッションハイジャッキングを実施する。

（３）平方剰余を用いたゼロ知識認証プロトコル（ZKAP）
本研究では、平方剰余の計算困難性に基づき、ゼロ知識認証プロトコルを提案する。提案手法は、初期化フェーズ、認証フェーズから構成される。
初期化フェーズ：サーバ𝑆は、二つの大きな素数のペア(𝑝M , 𝑞M ), (𝑝# , 𝑞# )をランダムに生成し、𝑁M = 𝑝M ⋅ 𝑞M
並びに𝑁# = 𝑝# ⋅ 𝑞# を計算する。各々の電子タグ𝑡について、識別子𝑇𝐼𝐷と秘密鍵𝑠𝑘を初期化する。サーバは、
タプル(𝑠𝑘, 𝑇𝐼𝐷, 𝑁M , 𝑝M , 𝑞M , 𝑁# , 𝑝# , 𝑞# )を保管し、電子タグのメモリーに(𝑇𝐼𝐷, 𝑠𝑘, 𝑁M , 𝑁# )を記録する。
認証フェーズ：認証フェーズは、五つのムーブ（エンティティ間でデータを送受信する回数）で構成される。
•

ムーブ１（リーダから電子タグ）：リーダは二つの𝑛-bit の乱数𝑟c ∈ {0,1}] 並びにベクトル𝑒⃗ ←{𝑒M , 𝑒# , ⋯ , 𝑒f }を一様分布で生成する。ここで、1 ≤ 𝑖 ≤ 𝑐について、𝑒T ∈ {0,1}とする。メッセージ𝑚M ≔〈𝑟c , 𝑒⃗〉を構成し、𝑚M を電子タグ𝑡に送信する。

•

ムーブ２（電子タグからリーダ）：電子タグは、リーダから𝑚M ≔ 〈𝑟c , 𝑒⃗〉を受信する。𝑛-bit の乱数
𝑟l ∈ {0,1}] を一様分布で生成し、受信したデータと自身が持つ秘密鍵から𝑦 ← 𝑠𝑘 ⊕ 𝑟l ⊕ 𝑟c を計算する。もし𝑦がℤ∗4n に含まれない場合は、乱数𝑟l の生成からやり直す。次に平方剰余を用いた暗号化を次の通りに行う。
𝑈 ← 𝐸𝑛𝑐(𝑟l ): = 𝑟l# mod 𝑁#
𝑌 ← 𝐸𝑛𝑐(𝑦): = 𝑦 # mod 𝑁#
𝐾 ← 𝐻(𝑇𝐼𝐷||𝑠𝑘)𝑥 ← 𝐸𝑁𝑐(𝐾) ⊕ 𝑟l ≔ (𝐾 # mod 𝑁M ) ⊕ 𝑟l𝑏t⃗ ≔ [𝑏M, 𝑏# , ⋯ , 𝑏f ], 𝑤ℎ𝑒𝑟𝑒 𝑏T ← 𝑟l 𝐾 yz mod 𝑁M
最後に、𝐻(𝑟l )と𝐻(𝑦)を計算し、メッセージ𝑚# ≔ 〈𝑈, 𝑌, 𝑥, 𝑏t⃗ , 𝐻(𝑟l ), 𝐻(𝑦)〉を構成しる。電子タグ𝑡は、
𝑚# をリーダ𝑅に送信する。

•

ムーブ３（リーダからサーバ）：リーダは、電子タグから𝑚# ≔ 〈𝑈, 𝑌, 𝑥, 𝑏t⃗ , 𝐻(𝑟l ), 𝐻(𝑦)〉を受信する。
ムーブ 1 で生成した情報を加えて、メッセージ𝑚{ ≔ 〈𝑚# , 𝑟c , 𝑒⃗〉を構成し、これをサーバ𝑆に送信する。

3
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

ムーブ４（サーバからリーダ）：サーバは、リーダから𝑚{ ≔ 〈𝑚# , 𝑟c , 𝑒⃗〉を受信する。まず𝑐個の要素•について、(𝑏T )# = 𝑟l# (𝑥 ⊕ 𝑟l )yz mod 𝑁M（ここで1 ≤ 𝑖 ≤ 𝑐）を計算し、等式が成立しない𝑖が存在すれば、認証を却下する。パスすれば、次に示すとおりに暗号化したデータの復号化を行う。
C𝑟l,M , 𝑟l,# , 𝑟l,{ , 𝑟l,| D ← 𝐷𝑒𝑐(𝑈)𝑟l ← 𝑟l,T 𝑠. 𝑡. 𝐻C𝑟l,T D = 𝐻(𝑟) for 1 ≤ 𝑖 ≤ 4(𝑦M , 𝑦# , 𝑦{, 𝑦| ) ← 𝐷𝑒𝑐(𝑌)𝑦 ← 𝑦T 𝑠. 𝑡. 𝐻(𝑦T ) = 𝐻(𝑦) for 1 ≤ 𝑖 ≤ 4
𝑠𝑘 ← 𝑦 ⊕ 𝑟l ⊕ 𝑟c
なお複合平方剰余を用いているため、𝑈と𝑌を復号化したときに、四つの平方剰余の候補が存在する。
ムーブ２で𝑟l と𝐻(𝑦)を計算しておくことで、正しい平方剰余を求めることができる。サーバは復元した秘密鍵𝑠𝑘がデータベース内に存在するか否かを確認し、存在しなければ却下する。正規の電子タグである場合は、相互認証のためにリプライを生成する。ACK として、𝑌•f‚ ← 𝐻C𝑠𝑘ƒ|𝑟l |ƒ𝑟c D並びに𝐻(𝑌•f‚ )を計算し、メッセージ𝑚| ≔ 〈𝐻(𝑌•f‚ )〉を構成する。サーバは、リーダに𝑚| を送信する。また
インテローゲーション毎に電子タグの秘密鍵を更新するため、𝑠𝑘 ← 𝐻(𝑇𝐼𝐷ƒ|𝑟c |ƒ𝑟l )を実行する。
ムーブ５（リーダから電子タグ）：リーダ𝑅は、サーバ𝑆から𝑚| ≔ 〈𝐻(𝑌•f‚ )〉を受信し、メッセージ•𝑚„ ≔ 𝑚| ≔ 〈𝐻(𝑌•f‚ )〉をそのまま電子タグ𝑡に転送する。タグは𝑚„ を受信し、ACK が正しいか否かを判定する。𝐻(𝑇𝐼𝐷 ⊕ 𝑟l ⊕ 𝑦)を計算し、それが受信した𝑚„ 内の𝑌•f‚ と同じであれば、サーバを認証し、𝑠𝑘 ← 𝐻(𝑇𝐼𝐷ƒ|𝑟c |ƒ𝑟l )を計算することで、自身の秘密鍵を更新する。また異なれば、ACK を却下する。
2-4 性能評価（１） 安全性とゼロ知識
ランダムオラクルを用いたプライバシー実験を設定し、識別不可能性を示すことによって、提案した認証プロトコルの安全性を証明した。安全性の定義は、RFID 分野で一般的に用いられる指標[5]を用いた。
ゼロ知識に関しては、提案手法の各ムーブで生成されるメッセージと同じ確率分布のデータを生成するシミュレータを設計することで証明する。各々のムーブで生成されるメッセージは、以下の要領で構成する。
•

ttt⃗… を得る。また擬似的な秘ムーブ１：シミュレータ𝑀は悪意のあるリーダ𝑅とやり取りをして、𝑟c… と𝑒
密鍵𝑝𝑠𝑘 ← {0,1}] をランダムに生成する。リーダが生成した𝑟c… は使用せずに、ランダムに生成した
𝑟E… ←† {0,1}] をを乱数として使用する。シミュレータはメッセージ𝑚‡ M ≔ 〈𝑟E… , ttt⃗𝑒 … 〉を構成する。

•

ムーブ２：シミュレータ𝑀は、乱数𝑟c… ←† {0,1}]をランダムに生成し、𝑦 … ← 𝑝𝑠𝑘 ⊕ 𝑟l… ⊕ 𝑟c… を計算する。
𝑦′ ∈ ℤ∗4n でなければ、再度乱数を生成して𝑦を計算し、𝑦 … ∈ ℤ∗4n となるまで繰り返す。提案手法と同‡# ≔様 に 𝑈 … 、 𝑌 … 、 𝐾 … 、𝑥 … 、𝑏t⃗ … 、 𝐻(𝑦 … ) 、 𝐻(𝑦 … ) を 計 算 す る 。 シ ミ ュ レ ー タ は メ ッ セ ー ジ 𝑚‰𝑈… , 𝑌 … , 𝑥 … , ttt⃗𝑏 … , 𝐻(𝑦 … ), 𝐻(𝑟l… )Šを構成する。

•

ムーブ３：シミュレータ𝑀はリーダ𝑅とやり取りをするが、リーダからのデータは破棄する。すでに計算済みのデータから、メッセージ𝑚‡ { ≔ C𝑈 … , 𝑌 … , 𝑥 … , ttt⃗𝑏 … , 𝐻(𝑦 … ), 𝐻(𝑟l… ), 𝑟E… , ttt⃗𝑒 … Dを構成する。

•

ムーブ４：シミュレータ𝑀は、𝑌•f‚ ← 𝐻(𝑃𝐼𝐷) ⊕ 𝑟l… ⊕ 𝑦 … と𝐻(𝑌•f‚ )を計算し、メッセージ𝑚‡| ≔〈𝐻(𝑌•f‚ )〉を構成する。
4
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

•‡„ = 𝑚‡ | とする。最後に乱数𝑒⃗を一様分布によってランダムに生成
ムーブ５：𝑚„ = 𝑚|であるため、𝑚tt⃗と一様分布で生成した𝑒⃗の全ての要素が同じなるまで、ループ構造によっする。リーダが生成した𝑒′tt⃗を生成しようとて、ムーブ１からムーブ５の処理を繰り返す。これによってリーダがどのような𝑒′e of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JIOT.2021.3138557, IEEE Internet ofThings Journal
tt⃗が一様分布になることを保証する。
も、𝑒′L. 14, NO. 8, AUGUST
2015
10
以上のように、シミュレータで生成した各々のメッセージは、実際のプロトコルで送受信されるメッ
1

ZKAP

Authentication time (sec)Authentication time (sec)

セージと同じ確率分布を持ち、多項式時間で動作する。そのため提案手法はゼロ知識の性質を持つ。
10.8（２）提案手法の実装と実験結果

ZKAP
0.8

本研究では、アセット電子タグとしての機能をラズベリーパイに実装し、提案手法と既存法[10]を実装
0.6
0.6

した。またサーバとリーダの機能は、Ubuntu マシンに実装した。セキュリティーパラメータは𝑛 ∈ [12,28]、0.4⃗の大きさは𝑐 ∈ [4,9]と設定した。
ベクトル𝑒

0.4

実験結果の一例を図２と図３に示す。図２は、公開情報のビット数（X 軸）に対する提案手法の実行速
0.2

0.2

度（Y 軸）を示す。ビット数が大きいほど、セキュリティ強度が高くなるが、それと同時にプロトコルの計

0
算処理が大きくなる。図３はプロトコルの成功率を示す。従来法[10]は一定の確率で認証が失敗するが、
26
28
22
28
0
2This
218 for publication
220
2in
2∗24
226journal,2but
article2 has been
accepteda future
issue
of thishas not been
Citation
218 fully edited.
220 Content
222 may change
224 prior
226to final publication.
228∈ℤ
であることを担保するため、１００％の確率で正規の電子タグを認証す提案手法では、ムーブ２で𝑦4nN2The size of product
N1
Things
TheJournal
size of rr
ることができる。

r different p2 JOURNAL
Fig. 4. The
timefor14,
different
p1
AT X CLASS FILES,OF Lauthentication
VOL.
NO. 8, AUGUST
2015
Fig. 5.
The authentication time for different rr .
E
and q1 .
1

1
ZKAP
0.995
0.8
0.99

4
0.8

0.985
0.6

3
0.6
2
0.4

226

228

0.98

0.4
0.975
0.97
0.2
0.965

1
0.2
0
0
218

1

Authentication time (sec)

1ZKAP
ZKAP

Authentication time (sec)
The success rate

Authenticationtime
time(sec)(sec)
Authentication

5

24

220 5
2

222 6
2

224 7
2

226 8
The size of product N2 2

Yeh’s
ZKAP

00.96
218 29 220 210 222 211

228 9
2

224212226213

0.8
0.6
0.4
0.2
0
218

228
214

The
Thesizesizeofofproductprimes pN1and q

The size of vector e

ZKAP

図２.
認証プロトコル実行速度.
図３.
プロトコルの成功率.
Fig. 3. The
authentication
time for different p2 Fig.
authentication
foranddifferent
p1
Fig.4.8.The
The
probabilityof timeZKAP
the Yeh’sFig. 5. The adifferent rt . andFig.q 7.. The authentication time for different c. and q .
protocolsucceedingfordifferent
p
and
q
.
2
1

The success rate

Authentication time (sec)Authentication time (sec)11ntication time withrespect to the ACKNOWLEDGMENTS
ZKAP
ZKAP
or !e is c. Whenc increases from 29
3 データ検証プロトコル
0.8
This research has been0.8
funded in part by the Telecommunications
changes from 0.5
to 0.8 seconds.
本研究課題では、IoT システムのエッジにおいて、IoT端末が生成するデータの完全性を担保するためのAdvancement Foundation.
he authentication
0.6 time. Therefore,
0.6
データ検証プロトコルを開発する。IoT
システムにおけるデータ完全生問題の特徴としては、１）センサー
arameters settingis thelisted機能を持つ
IoT one
端末はストリーム型のデータを生成する、２）IoT
端末自体は非力なデバイスであるため重

1
0.995
0.99
0.985
0.98
0.975

0.4
0.4
たい処理はサーバ側（IoT
ブローカー）で実施する、３）複数のセンサー端末がデータを生成するため
join
R
EFERENCES
0.97
オペーレーションをサポートする必要がある、といった点である。これらの問題を解決するために、本研究
0.2
0.2
0.965
ではカメレオンハッシュ関数を応用した認証データ構造を提案し、データ検証プロトコルを提案する。
[1] S. A. Ahson and M. Ilyas, RFID Handbook: Applications, Technology,

0.96
Security, and Privacy. 0 CRC press, 2017.
29
26
28
4
5
6
7
8
9
A. Juels,“RFID
A Research22222 Security2and Privacy:22
2 Survey,”
2 IEEE J.
2 Sel.
are Yeh’s protocol with ZKAP
2006.
Thetosize of rtAreas Commun., vol. 24, no. 2, pp. 381–394,
The size ofvector e
KAP and Yeh’s protocol succeed- [3] A. Mitrokotsa, M. R. Rieback, and A. S. Tanenbaum, “Classification ofFig. 8. The
Fig. 6. The authentication time forRFID
different
rt . Gen.,
Fig.
7. The authentication time for different c.
Attacks,”
5 vol. 15693, no. 14443, p. 14, 2010.
protocol succ
and q . The successprobabilities of[4] A. Czeskis, K. Koscher, J. R. Smith, and T. Kohno, “RFIDs and Secret
ontrary, Yeh’s protocol shows nonFigure 7 presents the authentication
time withagainst
respect
to the ACKNOWLEDGMENTS
Handshakes: Defending
Ghost-and-Leech
Attacks and Unauthore for different p and q , especially
9 公益財団法人電気通信普及財団
rized
Reads
with
Context-Aware
Communications,”
in
CCS, 2008, pp.
2
size of vector !e. The size of vector !e is c. When c increases from
研究調査助成報告書
第37号 2022年度
This
researchhas been funded in
479–490.
mall.
14
0
218

20

22

[2]24

to 2 , the authentication time changes from 0.5 to 0.8 seconds.

3-1 予備知識（１） カメレオンハッシュ関数
衝突困難性を持つハッシュ関数を暗号論的ハッシュ関数（Cryptographic hash functions）と呼ぶ。すなわち関数𝐻: {0,1}∗ → {0,1}]について、𝐻(𝑥) = 𝐻(𝑦)となるような異なる入力𝑥と𝑦を計算することは困難であるという。
またトラップドア付きの暗号論的ハッシュ関数をカメレオンハッシュ関数（Chameleon hash functions）と呼ぶ。ハッシュ関数𝐶ℎに関する秘密情報（トラップドア）を持つ場合にのみ、衝突を発見することができる。すなわちトラップドア𝑐𝑠𝑘が与えられた時、メッセージ𝑥とあるランダムな値𝑟 、さらに別のメッセージ 𝑥 … について、カメレオンハッシュアルゴリズム𝐶ℎを用いて、𝐶ℎf•‚ (𝑥, 𝑟) = 𝐶ℎf•‚ (𝑥 … , 𝑟 … )となるような異なる入力𝑟 … を効率的に計算することができる。
（２） カメレオン認証木（Chameleon Authentication Tree）
カメレオン認証木（CAT: Chameleon Authentication Tree）は [13] にて提案された認証可能なストリ
ーミングプロトコルのデータ認証手法として提案されたデータ構造である。CAT は根と全ての右ノードがカメレオンハッシュ関数で、また、全ての左ノードが衝突困難なハッシュ関数で計算された、葉の要素数が事前に決められていないマークル木である。
文献[13]において提案されているストリーミングデータ検証プロトコル VDS において、CAT は認証のためのデータ構造として利用されている。サーバ側では CAT 全体を保持していることに対し、クライアン
ト側ではある要素に対する CAT の認証パスのみを保持することで対数オーダーでの要素の検証を行うことができ、かつクライアント側ではストリーミングデータすべての保持をする必要がなく、計算資源の少ない環境でもストリーミングデータの検証を行うことができる。
3-2 関連研究
本研究と最も密接に関連する研究は、IoT アプリケーションにおけるデータの検証である。VERID [14]は、IoT サービスのための検証可能なデータ管理システムである。この研究では、プレフィックス木とマークル
木を統合した PrefixMHT を認証のためのデータ構造として用いることで、データの利用者が範囲選択・集計
クエリを行うことができるようになっている。文献[15] では、ブロックチェーンベースのデータ整合性サー
ビスのフレームワークが提案されており、スマートコントラクトを実装することで、第三者に頼ることなくデータの整合性を確保することができている。文献[16]では、ウェアラブルデバイス向けのデータ完全性ス
キームを提案しており、コンピュータのリソースを大量に消費する計算を IoT 対応のゲートウェイに委任することで、公開鍵基盤ベースの暗号化行うことができる。
また、データの完全性を保証するもう一つのアプローチは、MAC を使用することである。例えば、EPPDA [17]では、同形暗号と同形 MAC を組み合わせて、IoT ベースのヘルスケアアプリケーションにデータの完全性を提供している。しかしながら、これらの既存のデータ検証スキームはストリーミング形式のデータを保持することを想定していないため、ストリーミングデータアプリケーションには適用することができない。
3-3 提案手法（１）問題定義
本研究で想定する IoT システムは、IoT 端末（センサーなど）と IoT ブローカー（サーバ）、クライアント（パソコン、スマホなど）で構成される。IoT 端末はデータを生成し、それらを IoT ブローカーに送信する。IoT ブローカーは生成されたデータの認証データ構造を構成し、データの完全性を担保する。IoT ブロ

6
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

ーカーは、クライアントからのクエリーを送信することによって、データサービスを提供する。
（２）攻撃モデル
データ検証プロトコルの安全性については、選択メッセージ攻撃（Chosen message attacks）に対して偽装不可能生（Unforgeability）に基づいて実証する。また偽装不可能生については、どのようなメッセージ
でも良いので、正規の認証コードを生成することを目的とした、存在的偽装不可能生（Existential
forgery）を想定する。当該攻撃モデルでは、攻撃者はセキュリティパラメータ（鍵の長さ）とオラクル（クエリーに対してメッセージ認証コードを返す）を与えられ、自ら選択したメッセージに対応する認証コードを学習することができる。オラクルにメッセージを送信することができる回数は多項式回数に制限される。攻撃者は学習後に任意のメッセージとそれに対応する正規の認証コードを出力する。
提案プロトコルの安全性に関しては、ランダムオラクルを用いて、秘密鍵を持たない攻撃者がデータを注入し、セグメント CAT に認証コードを追加と認証コードの改ざんができないことを証明する。
（３）セグメント CAT データ構造
本研究では、データ検証のためのデータ構造として、セグメント CAT を提案する。これは、前述の CAT をセグメント木に応用したものである。セグメント木は完全二分木であり、各節点によって区間を管理するデータ構造である。根は区間全体を管理し、各節点の子は親の区間を二等分した２つの区間の片方を管理する。
これにより、区間に対する操作を𝑛個の要素に対して、 𝑂(log 𝑛)時間で行うことができるという特徴がある。
このセグメント木において、根と全ての右ノードをカメレオンハッシュ関数で、また、その他全ての左ノードを衝突困難なハッシュ関数で計算する。これにより、木の深さを𝐷とした場合に、2• 個の要素を認証することができ、またデータの消費者から送信される各区間クエリについて、𝑂(log 𝑛)で応答することができる。
各節点は、値とその値をもつ葉のインデックスを管理することで、データ消費者からの要求に対して、認証パスを計算することができる。
セグメント CAT の主なオペレーションは以下のとおりである。
•

セグメント CAT の生成：𝑔𝑒𝑛C1’ , 𝐷D
セグメント CAT は入力にランダムなセキュリティパラメータλと木の深さを表す𝐷を受け取り秘密
鍵𝑠𝑝と検証鍵𝑣𝑝を返却する。

•

要素の追加： 𝑎𝑑𝑑𝐿𝑒𝑎𝑓(𝑠𝑝, 𝑣)
要素の追加を行うには、秘密鍵𝑠𝑝と新たに葉に追加する値𝑣を入力として受け取り新たな秘密鍵𝑠𝑝′、
葉のインデックス𝑖、認証パス𝑎𝑃𝑎𝑡ℎを出力する 。

•

要素の認証：𝑣𝑒𝑟𝑖𝑓𝑦(𝑣𝑝, 𝑖, 𝑣, 𝑎𝑃𝑎𝑡ℎ)要素の認証を行うには、検証鍵𝑣𝑝と葉のインデックス𝑖、葉の値𝑣、認証パス𝑎𝑃𝑎𝑡ℎを入力として受け取り、葉𝑖番目の要素が𝑣であると検証できた場合𝑡𝑟𝑢𝑒を、そうでなければ𝑓𝑎𝑙𝑠𝑒を返却する。

（４）セグメント CAT を用いたデータ検証プロトコル
セグメント CAT をデータ構造としてデータ検証プロトコルを開発する。 IoT 環境において、データの消費者が一度にメモリ上に保存することができない長さのストリーミングデータを扱うことを目的としている。
（４-１）データベースの初期化
サーバはデータベースの初期化に際して、セキュリティパラメータ 1’ 、木の深𝐷を受け取り、𝑔𝑒𝑛(1’ , 𝐷)を実行する。その結果として、秘密鍵 𝑠𝑝 = (𝑐𝑠𝑘, 𝑐𝑠𝑘M , 𝑠𝑡) と検証鍵 𝑣𝑝 = (𝑐𝑝𝑘, 𝑐𝑝𝑘M , 𝜌) が出力される。ここで𝜌は初期の空の木の頂点を表している。その後、クライアントは秘密鍵𝑠𝑝をサーバは検証鍵𝑣𝑝を保持し、7
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

空のデータベースを作成する。
（４-２）要素をデータベースに追加するときサーバ上のデータベースに要素を追加する際、クライアントは 𝑎𝑑𝑑𝐿𝑒𝑎𝑓(𝑠𝑝, 𝑣) を自身の端末上で実行し秘密鍵𝑠𝑝… 、葉のインデックス𝑖、認証パス𝑎𝑃𝑎𝑡ℎを得る。その後、𝑖、𝑎𝑃𝑎𝑡ℎ、新たに追加する要素の値𝑣、をサーバに送付する。サーバは𝑎𝑃𝑎𝑡ℎを受け取り、それを自身のセグメント CAT に新たなランダムな値𝑅と共に追加する。
（４-３）要素を取得するときサーバ上のデータベースからクライアントが要素を取得する際、クライアントは求める要素のインデック
ス𝑖 をサーバに送付する。サーバは該当する葉の値𝑣と認証パスaPathž を返却する。クライアントは、
𝑣𝑒𝑟𝑖𝑓𝑦(𝑣𝑝, 𝑖, 𝑣, 𝑎𝑃𝑎𝑡ℎ)を実行し、該当する要素が変更や改ざんされていないことを確認する。
（４-４）要素を更新するときサーバ上のデータベースを更新する際、初めにクライアントは セグメント CAT のトラップドア𝑠𝑝、状態 𝑠𝑡、トラップドアが適用されていない値のペア (𝑥T,Ÿ , 𝑟T,Ÿ ) を取得する。続いて更新したい要素のインデッ
ク𝑖をサーバに送付し、サーバから更新前の要素 𝑣)cy と認証パス 𝑎𝑃𝑎𝑡ℎ)cy を取得する。クライアントは
𝑣𝑒𝑟𝑖𝑓𝑦C𝑠𝑝, 𝑖, 𝑣)cy , 𝑎𝑃𝑎𝑡ℎ)cy D を実行し要素が正しいものであることを検証する。要素が正当なものであった
場合、葉の値を更新し新たな認証パスを計算し新たな根 𝜌′を得て状態𝑠𝑡を更新する。最後にクライアントは新たな認証パス 𝑎𝑃𝑎𝑡ℎT ′ 、新たな要素 𝑣]y 、更新後の検証鍵 𝑣𝑝′ をサーバに送付する。サーバは受け取った認証パスの正当性を確認した後、正当なものであった場合は要素と自身の検証鍵の更新を行い、正当でなかった場合は更新をせずに処理を終了する。
3-4 性能評価
本研究では、提案手法の効率性を検証するために、シミュレーションを行った。提案手法であるセグメン
ト CAT を MacBook Pro 13 インチ（Core i7）に実装し、クエリ処理を発生させて、処理時間を計測した。生成したデータ数は、10 個から 100 万個とした。
図１に範囲最小値クエリに対するシミュレーション結果を示す。縦軸には応答時間、横軸には葉の要素数が表されている。図４に示すとおり、要素数が 1000 程度までは、従来手法である CAT は応答時間が短く、要素数が 1000 を超えると、提案手法の応答時間が短くなっていることがわかる。これは、要素数が 1000程度までは、従来の手法のように葉の要素全てを巡回し最小値を計算した場合の方がセグメント木において
区間クエリを処理することよりも効果的であることに起因する。しかし、提案手法において想定している、データの消費者がメモリ上に保存しておくことができない量のデータ、例えば 100 万データなどの場合は、従来手法の約 1000 倍速くクエリに応答することができていることがわかる。範囲最大値クエリや平均値を求めるようなクエリに対しても同様の結果を得ることができている。

8
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

Processing Time [ns]1x106

Segment CAT
CAT

100000
10000
1000
100
10
10

100 1000 10000 100000 1x106
The number of elements

図４. 範囲最小値クエリに対する応答時間.

4 まとめ
本研究では、ヘテロジニアス IoT システムにおける暗号プロトコルの研究に取組んだ。まずアセット RFID
電子タグを想定した認証プロトコルの開発に取組んだ。平方剰余を用いることによってゼロ知識の性質を持
つプロトコルを設計することに成功した。また提案手法の安全性を証明するとともに、センサー端末（ラズ
ベリーパイ）に提案手法を実装・実験することで、その有効性を示した。研究成果は電子情報通信学会の ISEC研究会で発表するとともに、IEEE Internet of Things Journals に採択された。
またデータ検証プロトコルの開発にも取り組んだ。提案手法では、トラップドア付きのハッシュ関数であるカメレオンハッシュ関数を用いてデータ認証構造を設計し、ストリームデータの完全性を保証する手法を設計した。提案手法は、従来の手法ではサポートしていない join オペレーションを含む範囲最小クエリを対数時間で処理できることを示した。またミュレーションによって性能評価を行い、実時間でも十分な性能を有することを示した。今後は、提案手法をサーバに実装し、カメラセンサーから生成されたストリームデー
タからデータ認証構造を生成する簡易プロトタイプを実装する。さらに今年度中に、研究成果を国内研究会で発表するとともに、IEEE などの国際論文誌に論文を投稿する。

【参考文献】[1] S. A. Ahson and M. Ilyas, RFID Handbook: Applications, Technology, Security, and Privacy. CRC
press, 2017.
[2] S. A. Weis, “Security and Privacy in Radio-frequency Identification Devices,” Ph.D. dissertation,
Massachusetts Institute of Technology, 2003.
[3] D. Molnar and D. Wagner, “Privacy and Security in Library RFID: Issues, Practices, andArchitectures,” in CCS, 2004, pp. 210–219.
[4] M. E. Hoque, F. Rahman, and S. I. Ahamed, “Anonpri: An Efficient Anonymous Private Authentication
Protocol,” in PerCom, 2011, pp. 102– 110.
[5] M.-T. Sun, K. Sakai, W.-S. Ku, T. H. Lai, and A. V. Vasilakos, “Private and Secure Tag Access for Large
Scale RFID Systems,” IEEE Trans. Dependable Secure Comput., vol. 13, no. 6, pp. 657–671, 2015.
[6] Y. Komori, K. Sakai, and S. Fukumoto, “Fast and Secure Tag Authentication in Large-scale RFID
Systems Using Skip Graphs,” Comput. Commun., vol. 116, pp. 77–89, 2018.
9
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度

[7] K. Sakai, M.-T. Sun, W.-S. Ku, and T. H. Lai, “On The Performance Bound of Structured Key-based
RFID Authentication,” in PerCom, 2019, pp. 1–10.
[8] Y. Chen, J.-S. Chou, and H.-M. Sun, “A Novel Mutual Authentication Scheme Based on Quadratic
Residues for RFID Systems,” Comput. Netw., vol. 52, no. 12, pp. 2373–2380, 2008.
[9] T. Cao, P. Shen, and E. Bertino, “Cryptanalysis of Some RFID Authentication Protocols,” J. Commun.,vol. 3, no. 7, pp. 20–27, 2008.
[10] T. Y. Yeh TC, Wu CH, “Improvement of The RFID Authentication Scheme Based on Quadratic
Residues,” Comput. Commun., vol. 31, pp. 337–341, 2011.
[11] S. Goldwasser, S. Micali, and C. Rackoff, “The Knowledge Complexity of Interactive Proof Systems,”
SIAM J. Sci. Comput., vol. 18, no. 1, pp.186–208, 1989.
[12] H. Liu and H. Ning, “Zero-knowledge Authentication Protocol Based on Alternative Mode in RFID
Systems,” IEEE Sens. J., vol. 11, no. 12, pp. 3235–3245, 2011.
[13] D. Schroder and H. Schroder. “Verifiable Data Streaming,” In ACM CCS, pp. 953-964, 2012.
[14] X. Li, M. Wang, S. Shi, and C. Qian, “VERID: Towards Verifiable IoT Data Management,” In IoTDI,
pp. 118-129, 2019.
[15] B. Liu, X. Yu, S. Chen, X. Wu, and L. Zhu, “Blockchain Based Data Integrity Service Framework for
IoT Data,” In ICWS. pp. 468-475, 2017.
[16] Ch. Doukas, I. Maglogiannis, V. Koufi, F. Malamateniou, and G. Vassilacopoulos, “Enabling Data
Protection through PKI Encryption in IoT m-Health Devices,” In BIBE, 2012. p. 25-29. 2012.
[17] F. Almalki; SOUFIENE and B. Othman, “EPPDA: An Efficient and Privacy-Preserving Data
Aggregation Scheme with Authentication and Authorization for IoT-Based Healthcare Applications,” In
WCMC, 2021.

〈発
題
Quadratic

名Residues-Based

表

資

料〉

掲載誌・学会名等
PrivateAuthentication for RFID Systems

発表年月

電子情報通信学会・ISEC 研究会

An RFID Zero-knowledge Authentication

IEEE

Protocol based on Quadratic Residues

JournalsInternetof2020 年 11 月.

Things2021 年度採択.

10
公益財団法人電気通信普及財団
研究調査助成報告書 第37号 2022年度