1.　はじめに

物流業界では，荷主がトラックを直接手配できない場合などに，サービス提供者がトラックを手配する配送マッチングサービス（以下，マッチングサービスと称す）が行われている．一般的なマッチングサービスでは，マッチング候補のトラックのルートの情報をあらかじめ収集しておき，荷主から届いた追加オーダの配送元・配送先の情報とルートの情報をもとに，適切なトラックにその追加オーダを割り当てる．荷主の追加オーダとトラックのルートには，出発地・到着地の所在地などの機微情報が含まれるので，サービス提供者に対して追加オーダとルートを秘匿することが望まれる．

本研究では秘密計算を用いてサービス提供者に対して追加オーダとルートの中身を秘匿した状態でマッチングを行う秘匿配送マッチングに取り組む．国内大手のマッチングサービス業者と同等のマッチング件数を実現しようとした場合，2.5節で述べるように289件のトラックのルートが含まれる1回のマッチングを3.6秒で処理する必要がある．秘密計算の手法として一般的な準同型暗号ではこの制約を満たすのは困難である．

一方で秘密計算を高速化する方法として，TEE（Trusted Execution Environment）によって秘密計算の一手法である関数型暗号（Functional Encryption）を実現する方法が知られている[1]．ここでTEEとは，ユーザが安全にプログラムを実行できる保護領域のことを意味し，例としてARMのTrust Zone^*1やIntel^*2のSGXが知られている．また関数型暗号は鍵生成者（Key Manager）が秘密鍵に演算を埋め込める暗号化方式であり，公開鍵で暗号化した暗号文に秘密鍵を適用すると元の平文の代わりに演算結果が取得できる．

しかしTEEによる関数型暗号においても，TEE内でルートと追加オーダを平文に復号する処理などのオーバヘッドが懸念される．そこで本研究では，秘匿配送マッチングにTEEによる関数型暗号を適用した場合の処理時間を明らかにするとともに，サービス提供者への秘匿性が満たせるか検証することを目的とする．

以降，2章で秘匿配送マッチングの課題と関連研究，3章でTEEによる関数型暗号の秘匿配送マッチングの処理内容，4章で評価環境の実装と評価，5章で得られた知見，6章でまとめを述べる．

2.　課題と関連研究

本章では，本研究で対象とする配送マッチング問題および秘匿配送マッチングの処理概要を述べ，課題と関連研究を説明する．

2.1　配送マッチング問題

マッチングサービスにおいて，複数のトラックのルートと1つの追加オーダに対して，その追加オーダをどのルートに割り当てるかを求める問題を配送マッチング問題と定義する．マッチングサービスでは，サービス提供者がルートと追加オーダをもとに配送マッチング問題をマッチングPF（Platform）上で解いて，追加オーダの割り当て先のトラックを決める．

ここでルートはマッチングを行う前にドライバが属する運送会社等が事前に決定しているが，そこに荷主からの追加の配送依頼（追加オーダ）を割り当てる．トラックは1回の配送業務で最初の出発地（起点と称す）から最終到着地（終点と称す）まで，途中の各地点で荷物の荷積み・荷降ろしを行いながら向かう．ルートはトラックの配送業務ごとに作成され，トラックが立ち寄る複数の地点が順番に記載される．たとえば「起点→地点1→地点2→終点」と記載する．また各地点には緯度・経度が紐づいており，ルートは地点を節点，地点間を結ぶ直線を辺とするグラフとみなすことができる．追加オーダには荷主がトラックに運んで欲しい荷物の出発地（発送元）と到着地（配送先）が記載されている．

2.2　割り当て先のトラックの決定方法

マッチングサービスのサービス提供者は以下の条件を加味して，追加オーダの割り当て先のトラックを説明する．なお，荷物の積載量や各地点への到着時間の制約も加味することも可能だが，本稿では対象外とする．

条件1．トラックは追加オーダ中の出発地から到着地に直接向かい，途中でルートに含まれる他の地点には立ち寄らない

条件2．追加オーダを割り当てた場合の追加距離が最小となるルートの辺に割り当てる

条件1について図1を用いて説明する．図1は2つのトラックが存在する場合に，地点7から8へ配送する追加オーダを割り当てる配送マッチング問題の例を示している．条件1はトラックが地点7から8に荷物を運ぶ途中に，そのトラックが立ち寄る予定のルートに含まれる他の地点（例．トラック1であれば地点1，2，3）に立ち寄らないことを意味する．これは，途中で他の地点に寄って別の荷物の荷積み・荷降ろしがあると，追加オーダの出発地（地点7）で積んだ荷物がトラックの荷台の奥に行ってしまい到着地（地点8）における荷降ろしがしづらくなる，また別の地点での荷降ろし時に出発地（地点7）で積んだ荷物が荷降ろし作業を阻害するといった懸念があるためである．

条件2について説明する．一般的な配送計画問題では，ドライバの労働時間やトラックの燃料代が過多とならないように，走行距離が最小となるようにルートを策定する[2]．配送マッチング問題においても，マッチングで割り当てた追加配送がドライバの負担とならないよう，追加距離最小となるルートの辺に追加オーダを割り当てる．なお追加距離は地図上の経路に沿った距離で評価することも考えられるが，経路に沿った距離がすぐに得られない場合には2地点（(x₁, y₁), (x₂, y₂)）間の直線（ユークリッド）距離（sqrt{(x₂-x₁)^2+(y₂-y₁)^2}），または碁盤目状に道路が有る場合にはマンハッタン距離（|x₂-x₁|+|y₂-y₁|）で評価することが一般的であり，文献[2]でも直線距離を用いている．そこで本研究でも追加距離は直線距離で評価するが，マンハッタン距離に変更することも容易である．

ルートの地点iから地点jの辺の途中に出発地kから到着地lの追加オーダを割り当てた場合の追加距離Lは，

L = 地点iと出発地kの直線（ユークリッド）距離 +

　出発地kと到着地lの直線距離 +

　到着地lと地点jの直線距離 －

　地点iと地点jの直線距離

と定義される．

2.3　配送マッチングで用いるデータと処理内容

配送マッチング問題で用いるトラックのルートの内容を表1，荷主の追加オーダの内容を表2にそれぞれ示す．ルート，追加オーダとも1回の配送（辺）の出発地・到着地をあらかじめ各トラックおよび荷主の端末で保持している住所情報のテーブルに登録されている場所IDを用いて指定する．またトラックのルートには複数の辺が存在する．次に，各トラック・荷主が用いる住所情報を表3に示す．住所情報は緯度・経度と住所（地番）が登録されており，トラック・荷主ごとに自身の端末で保持し，マッチングPFや他者には共有されない．配送マッチングでは，ルートと追加オーダ中の出発地・到着地の地点IDを緯度・経度に変換してマッチングPFに送信し，同PF上で割り当て先のトラックを決定する．

マッチングPFは各トラックのルートを1日の配送が始まる前にあらかじめ入手しており，トラックはマッチングPFにルートを毎日決められた時刻までに送ることを想定している．トラックが最初の出発地を出発する前にマッチングが行われ，追加オーダがマッチングPFに届くとマッチングPFに揃っているルートを用いてマッチング処理が始まる．マッチングPFは各トラックのルートのどの辺に割り当てたら追加距離最小となるかを探索し，追加オーダの割り当て先を決める．たとえば図1の場合，2つのルートR1，R2にはそれぞれ3つの辺（例．R1であれば地点1→2，2→3, 3→1）が存在する．このそれぞれの辺に対し追加オーダを割り当てた際の追加距離が最小となる辺に追加オーダを割り当てる．ここで，トラックや荷主がマッチング結果を承諾しなかった場合は，そのトラック以外のトラックのルートで最も追加距離が短いルートの辺を割り当て先とする．

2.4　秘匿配送マッチング

荷主とトラックにとって，マッチングPFを運営するサービス提供者に出発地・到着地の緯度・経度が分かると，web等で検索すれば取引先企業名が分かり望ましくない．そこで本研究では，出発地・到着地の緯度・経度をマッチングPFに秘匿した状態でマッチングを行う秘匿配送マッチングに取り組む．図2に秘匿配送マッチングの概要を示す．以降，秘匿配送マッチングを実施するマッチングPFを秘匿配送マッチングPFと称す．トラックと荷主のクライアント端末，および秘匿配送マッチングPFとクライアント端末間の通信路のセキュリティについては既存の方法で担保するものと考え，本研究の対象外とする．

2.5　処理時間の目標

配送マッチングの国内大手の1社であるT社では日々6,000件（2021年度）のマッチングを成立させており，日々13,000社の運送会社のルートを45拠点で扱っている[3]．なおT社では，秘匿配送マッチングのように追加オーダとルートを秘匿した状態でのマッチングは行っていない．本研究では追加オーダとルートを秘匿した状態でT社と同等のマッチング件数をめざすものとする．ただし，処理時間の評価対象は秘匿配送マッチングPFがルートと追加オーダを受信して割り当て先のトラックを導出するまでの時間とする．ここで，マッチングサービスは荷主が翌日のトラックを手配できない場合に利用されることが多く，午後（13–17時）に利用が集中すると考えられる．仮に2/3の4,000件がこの4時間に集中した場合，1時間あたり1,000件（1回あたり3.6秒以内）のマッチングを成立させる必要がある．

次に1回のマッチングで取り扱うルート数について説明する．T社では一日13,000件の空車情報を扱っており，1件の空車情報にトラック1台のルート情報が含まれる．T社と同様に45拠点で分けてマッチングを行うものとすると，1回のマッチングでは，13,000 / 45 = 289件のルートを扱う想定となる．以上からT社と同規模のサービスを1台のサーバで実現するものとし，289件のルートが含まれるマッチングを1回あたり3.6秒以内に成立することを目標とする．

2.6　秘匿配送マッチング実現の課題

秘匿配送マッチングにおいては秘匿配送マッチングPF上で暗号化されたルートと追加オーダから，追加オーダをルートの各辺に割り当てた際の追加距離を計算し，その最小値を取得する．データを暗号化した状態で計算する技術は，一般に秘密計算と呼ばれる．秘密計算の手法の例として，暗号文のままで線形演算と乗算が可能な完全準同型暗号（Homomorphic Encryption：HE）がある．しかし処理時間の課題があることが知られている[4]．

たとえばライブラリとしてMicrosoftのSEALを用いて表4に示すクラウド環境上で秘匿配送マッチングの処理を実装した場合，4つの辺が含まれる100件のルートに対して行った場合の処理時間を計測したところ，1回のマッチング（追加距離の算出と最小追加距離の算出）に約42秒掛かることが分かった．ここでSEALでは準同型暗号のベースとなる格子暗号の方式として，実数を整数に見立てて計算するCKKS（Cheon, Kim, Kim, Song）方式を用いた．

そのため，289件のルートが含まれるマッチングを3.6秒以内に成立することは実現困難である．また他の準同型暗号のライブラリでも処理速度は同等である[4]．準同型暗号よりも高速な秘密計算の手法として秘密分散があるが，ユークリッド距離計算における乗算の処理などにおいてサーバ間の通信のオーバヘッドが発生し，やはり処理速度が課題になると考えられる[4]．

そこで，ハードウェア的に高速な秘密計算が実施可能であるTEEを用いて秘匿配送マッチングシステムを構築し，処理時間およびデータの秘匿性を検証する．ここで処理時間については，TEEを用いた場合にはTEEの内部でルートと追加オーダを平文に復号してからマッチング処理を行うが，その復号に掛かる処理時間などのオーバヘッドが懸念されるため，2.5節で述べた処理時間の制約を満たせるかは不明という課題がある．

2.7　関連研究

本研究と同様に，暗号化された状態でユークリッド距離計算を行う研究として，中西らは準同型暗号を用いた顔認証基盤を開発している[5]．認証処理で行われる画像間の類似度算出の際に，準同型暗号でユークリッド距離計算を行うが，この処理時間の高速化が必要と述べている．

このようなソフトウェアによる秘密計算に対して，近年のCPUで提供されているTEEを用いたハードウェアによる秘密計算の実現も行われている[6]．FischらはTEEとしてSGXを用いて，関数型暗号を実現するIRONを提案している[1]．TEEを用いない一般的な関数型暗号では処理速度の課題があるが，TEEを用いることで従来の関数型暗号よりも数桁高速な処理が期待できると述べている．

ここで関数型暗号は鍵生成者が秘密鍵に任意の演算や処理を埋め込める暗号化方式であり，データ（平文）を公開鍵で暗号化した後，暗号文に秘密鍵を適用すると，元の平文は秘密鍵の利用者に秘匿しつつ任意の演算・処理結果を得ることができる[7]．また複数の暗号文を入力として秘密鍵を施すと演算結果が得られる多入力関数型暗号も存在する[8]．IRONでは鍵生成者が生成した秘密鍵をサーバ管理者が取得できない方法でTEEに送付し，TEEの中で暗号文を秘密鍵で平文に復号して演算を行い，演算結果をTEEの外に出力する．また鍵生成者がTEE内の処理で一意に決まるハッシュ値を認証することで，鍵生成者が許容した処理以外はTEE内で実施できない．これにより関数型暗号に該当する処理をTEEで実現している．

次に，加納らはIRONを拡張し，一定時間が経過するまで復号できないことを保証した関数型暗号である，関数型タイムリリース暗号を提案している[9]．またBhatotiaらは，IRONを拡張しシステムの内部状態に依存し，かつランダム化された関数型暗号を実現したSteelを提案している[10]．[9], [10]ともIRONを拡張して関数型暗号で取り扱い可能な関数の種別を拡大することを目的としているが，本研究の配送マッチングのように具体的な適用先の問題（アプリケーション）に対して適用評価を行ったものではなく，[9], [10]で開発した暗号が実用的であるかの評価が課題である．

岩田らは，SGXを用いて個人のゲノムデータをサーバに秘匿して解析を行う手法を提案している[11]．ここで，SGXではメモリサイズの制限があることから，分割したゲノム情報の暗号文を高速かつ安全にTEE内に展開するためにデータの牽引化とパス型ORAM [12]（Oblivious RAM：サーバからアクセスパタンを秘匿しつつランダムアクセスを行うための暗号学的技術）を用いている．またMandalらは，同じくゲノムデータのχ二乗分布の解析をSGXで行っており，サーバにゲノムデータを秘匿するとともにORAMを用いることでメモリアクセスパタンの秘匿も図っている[13]．最後に，Felsenらは2つのパーティがお互いの入力値は明かさずに公開された関数の出力値を得るSecure Function Evaluation，および片方のパーティが関数を明らかにせずにもう片方のパーティからの秘匿化された入力値に対する結果を得るPrivate Function Evaluationを，SGXで実現している[14]．また処理時間を評価し，処理が複雑になってもYaoのガーブル回路[15]とGMW（Goldreich, Micali, and Wigderson）[16]のプロトコルに比べて高速であることを述べている．

[11], [13], [14]とも入力データを暗号化してSGXに送り，平文で処理を行う点は本研究と共通であるが，関数型暗号で考慮される鍵生成者が不在なため，仮にTEE内の処理をサービス提供者（サーバ管理者）が書き換えた場合TEE内の復号鍵を入手できることを考慮していない課題がある．

3.　関数型暗号による秘匿配送マッチング

本章では，TEEによる関数型暗号を用いた秘匿配送マッチングの処理内容について説明する．

3.1　TEEによる関数型暗号

FischらはTEEとしてSGXを用いてハードウェア的に関数型暗号を実現することで，TEEの外に入力値を秘匿した状態で任意の関数を高速に処理し，その結果を取得できるIRONと呼ばれるシステムを開発している[1]．そこで本研究ではIRONと同様にTEEとしてSGXを用いて関数型暗号を実現し，秘匿配送マッチングに適用する．SGXでは主記憶装置上にEnclaveと呼ばれる保護領域を形成し，その内部で秘密情報を保持しながらプログラムを実行できる．

IRONでは鍵生成者がSGXに復号用秘密鍵を渡す際に，Remote Attestationと呼ばれるEnclaveで実行するバイナリが意図したものであるか外部から確認することができる機能を用いる．このようにKey Managerは単に鍵を生成するのみならず，Enclave内の処理の妥当性を確認する役割を担う．

また，IRONでは関数型暗号の処理を行うPFであるDecryption Node PFにおいて，関数型暗号の演算を行うFunction Enclave（以降，FEと称す）と，鍵生成者から秘密鍵を受け取り，FEを認証した後に秘密鍵を提供するDecryption Enclave（以降，DEと称す）の2つのEnclaveから構成される．DEがFEを認証する際は，同一CPU上のEnclave間の認証であるLocal Attestationの機能を用いる．Local Attestation，Remote Attestationともに，Enclaveを認証する際にはSGXがEnclaveプログラムの生成（ビルド）時にEnclaveプログラムから計算するハッシュ値mrenclaveが用いられる．mrenclaveはEnclaveプログラムに依存する．

次に関数型暗号では，秘密鍵の利用者が秘密鍵で暗号文を復号する際に，任意の演算結果を得ることができるものであり，複数の暗号文を入力として秘密鍵を施すと演算結果が得られる多入力関数型暗号も存在する[8]．本研究では，複数のルートと1つの追加オーダの暗号文から追加距離最小となる割り当て先のルートの辺を求める多入力関数型暗号に該当し，サービス提供者は演算結果である割り当て先のルートの辺のみを取得する．

3.2　秘匿配送マッチングシステムの全体像

図3を用いて，TEEによる関数型暗号秘匿配送マッチングシステムの全体像を説明する．IRONでは任意の関数型暗号の処理（図中の関数f）を扱えるように設計されているが，本研究では関数fは秘匿配送マッチングに特化し，追加距離計算と割り当て先トラック決定を行う．図3で，秘匿配送マッチング向けに実装した箇所を点線で示す．図3における各略号の意味を以下に示す．

• ・DE：Decryption Enclaveの略
• ・FE：Function Enclaveの略
• ・KME：Key Manager Enclaveの略
• ・PF App.：秘匿配送マッチングPFのEnclave外のアプリ
• ・Key Manager App.：Key ManagerのEnclave外のアプリ
• ・（pk_pke, sk_pke）：ルート・追加オーダの暗号用公開鍵，復号用秘密鍵
• ・関数f：FEで行う処理の関数
• ・（vk_sign, sk_sign）：関数fの署名検証鍵，署名用秘密鍵
• ・mrenclave_f：FEから生成されるハッシュ値mrenclave
• ・mrenclave_DE：DEから生成されるハッシュ値mrenclave
• ・sig_f：mrenclave_fに対する電子署名

関数型暗号による秘匿配送マッチングシステムは，1．鍵生成とDEの認証，2.FEの認証，3．マッチングの3つの処理からなる．これらの処理を構成する要素として秘匿配送マッチングPFとKey Manager（鍵生成者）が定義される．秘匿配送マッチングPFにはDEとFEの2つのEnclave，およびPF App.が内部モジュールとして存在する．また，Key Managerには内部モジュールとしてKMEとKey Manager App.が存在する．ここでKey ManagerはIRONではTrusted Authorityの役割を兼ねるが，本研究でも同様にTrusted Authorityを兼ねるものとし，秘匿配送マッチングPFを運営するサービス提供者の不正を監視する．Key Managerはサービス提供者とは独立した立場の第三者認証機関が担当する．

ここで，DEの認証はKey ManagerがRemote Attestation（以降，R.A.と称す）を用いて行い，通常のR.A.に加えて，Key ManagerがDEのmrenclave値であるmrenclave_DEの正解値をあらかじめ保持しておき，R.A.でDEから送付されるmrenclave_DEが毎回同じであるかを確認することで，DE内のソースコードの改変が無いかを確認する．また，FEの認証は，DEがFEの中の処理に改ざんがないことを認証する処理である．以降，各処理とその構成要素を説明する．

1.　鍵生成とDEの認証

Key Managerは（pk_pke, sk_pke），（vk_sign, sk_sign）をKME内で生成する．また，Key Manager App.はDEからのR.A.を受けて，DEを認証後に署名検証鍵vk_signとルート・追加オーダの復号用秘密鍵sk_pkeを提供する．その際，KMEにてDEのmrenclave値（mrenclave_DE）が，KMEはあらかじめ保持している正解値のmrenclave_DEの値と比較して一致検証を行う．これにより，第三者による秘匿配送マッチングPFの成りすまし，サービス提供者や第三者のDEの改ざんを抑止する．ここでR.A.にはEnclaveの認証の際に，Intel社のIAS（Intel Attestation Service）と呼ばれるサーバに問い合わせる方式であるEPID（Enhanced Privacy ID）方式[17]を用いる．

2.　FEの認証

Key Manager App.はPF App.からFEの処理内容（関数f）のハッシュ値であるmrenclave_fを受けてKMEに送り，KMEにてmrenclave_fにsk_signで署名を行い，その結果であるsig_fをPF App.に送る．PF App.は，sig_fを取得後FEに送信する．

次に，FEはDEに対してLocal Attestationを要求し，sig_fをDEに提供する．DEは署名検証鍵vk_signでsig_fを復号して得られるmlenclave_fの値がLocal Attestation（以降，L.A.と称す）で得られるmlenclave_fの値と一致するか検証し，検証結果がTrueであればFEに復号用秘密鍵sk_pkeを提供する．これによりFEの処理内容がKey Managerが署名した処理から改ざんがなされていないことを担保する．

ここで，FEとDEを分離した理由を説明する．KMEではmrenclave_DEの値（正解値）を保持しているが，KMEの正解値の書き換えが頻繁に起きるのは管理上望ましくない．ここで，DEはFEに比べて処理内容の変更が少ないと考えられる．FEとDEを分離すれば，KMEで保持するのは書き換え頻度の少ないDEのmrenclaveで良く，分離しない場合と比べて正解値の書き換え頻度を減らすことが可能となる．

3.　マッチング処理

トラックと荷主はPF App.から公開鍵pk_pkeを取得し，それぞれルート・追加オーダを暗号化してPF App.に送る．PF App.はFEに暗号化されたルート・追加オーダを送り，FEはsk_pkeにてルートと追加オーダを平文に戻し，マッチング処理を行う．FEはマッチング処理結果をPF App.に通知する．

3.3　鍵生成とDEの認証の処理詳細

まず，Key ManagerがDEを認証してsk_pkeとvk_signを送付するまでの手順について，図4を用いて説明する．

(1)KMEは鍵生成を行う

(2)DEはR.A.をKey Manager Appに要求

(3)sk_pkeとvk_signをDEに配布

sk_pkeとvk_signはDEが一度受け取ったら，秘匿配送マッチングPFのメモリにSealing（SGX内のデータを暗号化してメモリに書き込む処理）で保持しておき，秘匿配送マッチングPFのメモリから取得するが，DEの認証は定期的（例．1日に1回）に行いDEの不正を抑止する．

またDEは原則的に処理内容を変更しないものとするが，もし処理の変更が必要な場合は，Key ManagerはDEから新たなmrenclave_DEを取得しKMEで保持している正解値のDEのmrenclaveを置き替え，sk_pkeとvk_signを再発行する．

3.4　FEの認証

次に，DEがFEを認証してsk_pkeを送付するまでの処理を同じく図4を用いて説明する．

(4)PF App.はmrenclave_fを取得し，mrenclave_fをKey Manager App.に送付

(5)KMEはmrenclave_fをsk_signで署名してsigfを生成

(6)Key Manager App.はsig_fをPF App.に送付し，PF Appはsig_fをFEに送付

(7)FEはDEにL.A.を要求し，sig_fを送付

(8)DEはsig_fをvk_signで復号し，L.A.で取得したFEのmrenclave値と一致するか検証

(9)DEは（8）の検証結果がTrueであれば，L.A.成立．DEはFEにsk_pkeに送付

（4）～（6）は初回およびFEの処理内容の変更やFEの追加があった場合のみ行うものとし，sig_fはPF App.が一度Key Managerから取得したらPF App.が保持する．一方（7）～（9）は定期的（例．1日に1回）に行うことで，Key Managerが署名を行った処理のみが秘匿配送マッチングPF上で行われるようにする．

3.5　マッチング処理の詳細

図5を用いてマッチングの処理の詳細を説明する．なお（17）以降の処理は将来的に秘匿配送マッチングサービス事業を実現する際には必要となるが，本研究における処理時間の評価対象には含めていない．

(10)PF App.はあらかじめKey Managerから取得した暗号用公開鍵pk_pkeをクライアントに配布（初回のみ）

(11)トラックはルートを暗号化し，PF App.に送付

(12)FEはPF App.からルートを取得し復号

(13)荷主は追加オーダを暗号化しPF App.に送付

(14)FEはPF App.から追加オーダを取得し復号

(15)FEはマッチング処理にて割り当て先トラック・辺を決定．

(16)FEは割り当て先のトラックと辺をPF App.に通知．

(17)PF App.は割り当て先のトラックに通知

(18)トラックは受諾するかを選択し，受諾結果をPF App.に通知，およびPF App.が荷主に受諾結果・トラックを通知

(19)荷主が承諾結果をPF App.に通知し，PF App.はFEに承諾結果を通知

(20)DEはSealingでsk_pkeとvk_signを保存

（1日の処理終了後）

ここで（12）にてPF App.はルートをSGXのメモリ制約

（第一世代のSGXではEPC（Enclave Page Cash）96 MB）の上限を超えない範囲で複数件まとめて送る．また（17）でトラックに通知する際に，あらかじめFEで追加オーダをsk_pkeで暗号化してトラックに送付し，トラックはpk_pkeで追加オーダを復号して，受諾するか否かを選択する．また，（18）（19）でトラックや荷主が承諾しなかった場合は，そのトラックのルート以外で追加距離が最短の辺を割り当て先として，（17）以降の処理を繰り返す．なお（19）でFEに承諾結果を通知するのは，一度マッチングが成立したルートは次のマッチングの割り当て候補から外すためである．

3.6　サービス提供者の不正抑止

ここで，FEを実行するサービス提供者が，FEの処理に不正を加えると秘密鍵や復号したルート，追加オーダを閲覧できる懸念がある．そこで，3.4節で説明したようにKey ManagerがFEの処理内容の認証を行ってsig_fを生成し，DEがFEを認証することで，秘匿配送マッチングPFではKey Managerが認証したプログラム以外は実行できないようにしている．

またKey Managerは，3.4節の（4）～（6）を行う際に，秘匿配送マッチングPFにmrenclave_fと合わせてFEのソースコードを提出させ，FEの処理に不正（例：SGX内で平文にしたルートと追加オーダをOCALLでPF App.に出力するなど）がないかを確認する想定である．またDEの処理についても，初回および処理内容を変更した際にKey Managerにソースコードを提出させて不正がないか確認する想定である．

4.　評価環境の実装と評価

本章では，評価環境の実装および処理時間の評価と，サービス提供者に対する秘匿性の評価について述べる．

4.1　評価環境の実装

3章で説明した秘匿配送マッチングの評価環境の実装を行った．開発に用いたPCや開発環境等を表5に示す．

評価環境では，Key Managerおよびトラック，荷主は秘匿配送マッチングPFと同じPCで実装している．また（17）以降の処理は秘匿配送マッチングPFの処理時間に与える影響はわずかと判断し評価対象外とする．（2）のR.A.については秘匿配送マッチングPFの処理とは切り分けて実装し，処理時間を評価する．

4.2　処理時間の評価方法

2.5節で述べた，289件のトラックのルートが含まれる配送マッチング問題を1回あたり3.6秒以内に解く目標を満たせるか確認する．また，ルート件数をSGXのメモリサイズの上限を超えない最大5万件まで増やした場合の処理時間を評価する．各トラックのルートには4つの辺が含まれるものと仮定する．これはたとえば倉庫や集配所などの出発地から3地点（例．朝出発して午前中1地点，午後2地点）に立ち寄って各地点で荷降ろしと荷積みを行い，出発地に戻る場合のルートに該当する．処理時間の計測にはWindowsのQuery Performance Counterを使用した．処理時間は10回処理を行った平均値を用いる．

ここでSGXではStackとHeapのサイズについて，双方のサイズの和がEPCの上限を超えない範囲で変更ができる．Intel SGX SDKで設定されているStackとHeapの初期値はそれぞれ0.26 MBと1.0 MBであるが，同じルート件数の場合にStackとHeapのサイズを変えて処理を試行しても処理時間は殆ど変わらないことが分かった．また評価環境ではHeapに平文にしたルートと追加オーダを保持しているため，ルート件数を増やすとHeapの枯渇が起き，マッチング処理が行われなくなる．そこでルート件数を増やすに連れてHeapサイズを増大させて処理時間を評価する．なお，StackはEnclave内外のデータの授受に用いられるメモリで，FEの中にルート，オーダを送る際に使われているが，Stackサイズを変えても処理時間への影響はない．

4.3　処理時間の評価結果

評価結果を説明する．評価結果は秘匿配送マッチングPFにおけるマッチング処理（暗号化されたルートと追加オーダをFEに送り，割り当て先のトラックを導出する処理）とマッチング処理よりも前に行う処理（鍵生成とFE，DEの認証およびルートと追加オーダの暗号化）に分けて説明する．

表6にマッチング処理よりも前に行う処理とその実施頻度を示す．R.A.に約4秒掛かるが，利用の少ない夜間などに行えば良い処理のため，問題ない．なお本研究と同じEPID方式のR.A.の処理時間は，文献[17]では数10 msec，文献[18]では約1.8秒と述べており，[18]にて大部分がIASへの問い合わせに要する時間と報告されている．[17], [18]のR.A.の処理時間が本研究の計測結果より短いのは，NW環境（[17]は1 Gbイーサネット，[18]は詳細未公表であるが大学の学内LANを介してIASに接続）やCPUの性能差（[17]はIntel Core i5-10400@4.3 GHz，[18]はIntel Core i7-9700K@3.60 GHz）によるものと考える．またルートと追加オーダの暗号化については本来クライアント端末で行うが，いずれも所要時間はわずかである．

次に，表7にルート件数と秘匿配送マッチングPFにおけるマッチング処理の所要時間の関係を示す．ルート件数が1,000件以下の場合はStackとHeapとも8.4 MBに設定し，1万件，5万件のときはHeapの枯渇が起きないようにHeapサイズを設定した．ルート件数がいずれの場合でも，FE内で行うルートの復号に掛かる時間が支配的であり，1～3の処理全体の99%以上を占めるが，ルートが289件の場合でも1～3の処理を合わせて2.5秒でマッチングができ，2.5節で示した3.6秒以内という制約を満たすことができる．またルート件数とルートの復号に掛かる処理時間の関係を図6に，ルート件数と割り当て先トラック決定に掛かる処理時間の関係を図7にそれぞれ示す．双方の処理時間ともルート件数に対して線形で増えることが分かる．

ここでStackとHeapのサイズはルート件数5万件のときに設定した合計86.65 MBが上限であり，それ以上のサイズを割り当てるとEnclaveの起動ができなくなった．但しこれはWindows環境下で第一世代のSGXを用いた場合の事象であり，Linux環境下では処理速度が低下する代わりに，より大きなメモリサイズを設定できることが知られている．なお第二世代のSGXでは上限のEPCサイズを動的に変更でき，ルート件数や各トラックの辺の数をさらに増やすことが可能と考えられる．

ここで，評価環境ではルートを全件まとめてSGXの中に送り復号して，それが完了したら荷主の追加オーダをSGXに送って復号後にマッチングをしている．一方，実際のサービスにおいては秘匿配送マッチングPFにルートが到着したら順次あらかじめSGXの中に送って事前に復号しておけばよく，荷主にとっての応答時間は表7の2と3の合計と考えることができる．すると，ルート件数が5万件の場合でも，荷主にとっては174.3 msecで応答が返って来ることから，十分高速なマッチングができている．

なお本来は荷主端末と秘匿配送マッチングPFとの通信時間を考慮する必要がある．荷主から秘匿配送マッチングPFには表2に示す追加オーダをRSA-2048 bitで暗号した暗号文を送信し，また秘匿配送マッチングPFから荷主にはマッチング結果を送信するが，ともにデータサイズは数kBであるため，通信時間はわずかと考える．

4.4　サービス提供者に対する秘匿性の評価

本節では，サービス提供者に対するルート・追加オーダの秘匿が実現できているか検証する．表8に想定されるサービス提供者のルートと追加オーダの閲覧方法とそれに対して本研究で検討した対策を示す．

まず秘密鍵sk_pkeをKey ManagerからDEに提供する際にサービス提供者が不正入手する可能性がある．これについては，SGXではR.A.を行った際に，ECDH鍵交換が行われAES共通鍵が生成される[18], [19]．この共通鍵でsk_pkeを暗号化した後にKey ManagerからDEに渡すことで，サービス提供者のsk_pkeの入手が抑止できる．なお[18]ではこの共通鍵はEnclave外から入手不可能と述べているが，DEのソースコードをサービス提供者が改変すれば入手できる可能性が有る．しかし，そうするとmrenclave_DEの値が変わってKey Managerが保持している正解値と一致せずDEの認証が通らなくなるため，DEのソースコードの改変は不可能である．

次に，サービス提供者がFE，DEのソースコードを改ざんして秘密鍵sk_pkeを入手する，ECALLやOCALLなどによってルート・追加オーダを閲覧できる可能性がある．これらに対してもDEについては，Key ManagerはDEの認証時にR.A.に加えてmrenclave_DEの値をあらかじめ保持している正解値と照合してDEの処理の不変性を検証しているため，DEの改ざんを防ぐことができる．FEについてもDEがFEを認証する際にmrenclave_fの値がsig_fを復号して得られるmrenclaveの値と一致するか検証しているため，FEの改ざんを防ぐことができる．

よって，サービス提供者がFE, DEの中の処理を改ざんしてルート，追加オーダを閲覧することはできない．なお，サービス提供者がFE，DEの処理を変更する正当な理由がある場合はKey Managerがソースコードを確認することで，不正が無いことを確認する想定である．

4.5　今後の課題

SGXではサイドチャネル攻撃からの脆弱性が指摘されており，良く知られているものとして，プログラムの中身や実行順序をメモリの配置される場所から推測して情報を得るキャッシュタイミング攻撃がある[9]．対策として，文献[11], [13]のようにORAMを用いてメモリやディスク上に保管したデータへのアクセスパタンを秘匿する方法が一般的であるが，計算時間が大きく増加する懸念がある．それに対して，Costanらはメモリアクセスパタンが秘匿可能なTEEを実現したSanctumを開発しており，処理時間のオーバヘッドは通常のTEEの10%程度である[20]．今後本研究でも適用を検討する．

その他，本研究ではサービス提供者への秘匿性を評価対象としたが，Key Managerやクライアント端末，通信路のセキュリティ，および秘匿配送マッチングPFにおける秘匿性以外のセキュリティの担保方法についても検討が必要と考える．また現在は追加距離最小という指標でのみ割り当て先トラックを決定しているが，積載量や時間制約などの他の指標を加味したマッチングについても検討する．

5.　得られた知見

本研究では準同型暗号のライブラリとしてSEALを用いた場合（2.6節に記載）と，TEEとしてSGXを用いて関数型暗号を実施した場合の秘匿マッチングの処理時間を計測し，後者の場合において処理時間の制約を満たせることを確認するとともに，処理時間はSGXのメモリサイズの上限内でトラックのルート数に対して線形で増加することが知見として得られた．

また復号処理に掛かる時間が秘匿配送マッチングPFのマッチング処理時間の99%以上を占めることが分かった．ただし秘匿配送マッチングPFでは受信したトラックのルートを随時TEE内に送り復号して保持しておくことで，ルート件数が増えても高速なマッチング処理が実施でき，荷主に対する応答時間を十分に短くできる．準同型暗号では暗号文を用いて演算を行うため事前にルートを復号しておくことはできないが，TEEの場合は事前に復号することで荷主に対する応答時間を担保できることがTEEの利点である．

また準同型暗号とTEEの双方を用いて実装して得られたTEEの利点の知見として，TEE内では平文の処理のため，準同型暗号（SEALを使用）に比べてマッチング処理自体の実装は容易でマッチングアルゴリズムの拡張性も高いこと，またアルゴリズムを拡張した場合の追加の処理時間は平文と同等と考えることができ，処理時間を見積もりやすいことが挙げられる．このように秘匿配送マッチングで求められる高速性と拡張容易性の面でTEEは準同型暗号よりも優れており，現時点ではTEEを用いることが適切と考える．

6.　まとめ

サービス提供者に対してルートと追加オーダを秘匿した状態で配送マッチングを実現する秘匿配送マッチングにおいては処理時間の課題があり，準同型暗号では制約を満たせない．一方関数型暗号をTEEで実現すれば高速化が可能であることは知られていたが，TEEの中でルートと追加オーダを平文に戻す際のオーバヘッドがあるため，処理時間の制約を満たせるかは不明であった．

本研究では，IRON [1]のプロトコル（システム構成，処理手順）をベースに，SGXを用いた多入力関数型暗号を実現し，評価環境を構築して処理時間を評価した．その結果トラックのルートが289件存在するマッチングを約2.5秒で実施でき，3.6秒以内という制約を満たせることを確認した．また，サービス提供者にルートと追加オーダが秘匿できることを確認し，秘匿マッチングにおけるTEEを用いた関数型暗号の有効性を確認した．

謝辞　本研究の推進に際し，多数のご助言をいただいた薦田憲久 大阪大学名誉教授に感謝いたします．