はじめに

本記事では、Function Secret Sharing (以後、FSS という) について紹介します。

本記事は、Boyle 氏らの論文 [1] をベースとしています。

秘密分散法についての知識がある方を前提として書かれていますので、先にこちらの記事を参照することをおすすめします。

https://acompany.tech/privacytechlab/mpc-secret-sharing/

FSS の概要

FSS は、その名の通り、関数 $f$ をシェア化する手法のことを指します。

より正確には、以下の条件を満たしつつ、関数 $f: \{0, 1\}^n \rightarrow \mathbb{G}$ を $p$ 個のシェア $f_i: \{0, 1\}^n \rightarrow \mathbb{G}, 1\leq i \leq p$ に分割する手法のことを FSS と言います ($\mathbb{G}$ はアーベル群)。

(1) $\sum_{i=1}^p f_i(x) = f(x)$
(2) 集合 $\{ f_1, f_2, \cdots, f_p \}$ の任意の真部分集合から、$f$ を復元することはできないすなわち、$f_1, f_2, \cdots, f_p$ を全て得た場合のみ、$f$ を復元することができる

FSS は、概念としては加法的秘密分散法 (additive secret sharing) と非常に似ています。加法的秘密分散法は「秘密情報 $s$ を分散する手法」ですが、FSS は「関数 $f$ を分散する手法」です。加法的秘密分散法について気になる方は、こちらの記事を参照してください。

https://acompany.tech/privacytechlab/mpc-secret-sharing/

FSS の適用例

FSS は、下記を行うことをモチベーションとして提案された技術です。

安全な検索 (securely searching)
分散データの安全な更新 (securely updating distributed data)

安全な検索 (securely searching)

FSS を使用することで、実行する関数 (クエリと置き換え可) 及び実行結果を秘匿したまま、安全にデータの検索を行うことができます。この機能はプライベート情報検索 (Private Information Retrieval, PIR) とも呼ばれます。

例えば、$m$ 個のデータを保持しているサーバに対してクエリを発行し、$i$ 番目のデータを取得することを考えます。従来であれば、ユーザからのクエリを確認することで、ユーザがどのデータにアクセスしたのかを知ることができてしまいますが、FSS を使用することでクエリの実行内容・及び実行結果を秘匿したまま、 $i$ 番目のデータを取得することができます。

分散データの安全な更新 (securely updating distributed data)

FSS を使用することで、実行する関数 (すなわち更新クエリの内容) を秘匿したまま、安全に分散データの更新を行うことができます。

例えば、各秘密情報のシェアが格納されている $p$ 台のデータベースが存在するとします。

とある秘密情報 $a$ の値を、安全に (すなわち、どの秘密情報に対して、どのくらいの値を加算するのかを秘匿したまま) $c$ だけ加算することを考えます。

通常であれば、クライアントが $c$ のシェア $[c]$ を作成し、各データベースに対して、$[a]$ に $[c]$ を加算するような更新クエリを打つことになりますが、この手法だと $c$ という値自体は秘匿できますが、$a$ に対して何らかの値を加算するという行為までは秘匿できていません。

一方で、FSS を使用することで、クエリの実行内容・及び実行結果を秘匿したまま、安全にデータの更新を行うことができます。

FSS の仕組み

FSS における重要な関数 DPF (Distributed Point Function)

上記で言及した「安全な検索」と「分散データの安全な更新」を行うためには、DPF (Distributed Point Function) [2] という関数が重要な役割を果たします。

DPF とは、Point Function (点関数) を複数 Party で秘匿計算する手法のことを指します。

点関数は、特定の入力値 $a$ が入力された場合のみ $b$ を出力し、それ以外の場合は 0 を出力する関数です。数式で表現すると、以下のようになります。

$$ f(x) = \begin{cases} b&\quad x = a, \\ 0 &\quad otherwise \end{cases} $$

「安全な検索」の実現方法

データベースに登録されているデータの集合を $D \ (|D| = n)$ とし、$i (1 \leq i \leq n)$ 番目のデータを $D_i \in \mathbb{G}$ とします。また、FSS Party は $p$ 台とします。

例えば、$a$ 番目のデータ ($D_a$) を安全に検索する場合を考えます。

まず、下記点関数 $f$ をシェア化し、各 Party $P^{(i)}$ にその関数シェア $f_i$ を送信します (関数 $f_i$ の実体については、後の章で説明します)。

$$ f(x) = \begin{cases} 1 &\quad x = a, \\ 0 &\quad otherwise \end{cases} $$

続いて、各 Party $P^{(i)}$ が以下の $z^{(i)}$ を計算します。

この時、各 Party $P^{(i)}$ は「何の関数を実行しているのか認識していない」点に留意してください。

$$ z^{(i)} \leftarrow \sum_{j\in [n]} D_jf_i(j) $$

全ての計算結果 $z^{(1)}, z^{(2)}, \cdots, z^{(p)}$ をクライアントに送信し、クライアントはその総和を取ることで、$z = D_a$ を復元することができます。

$$ \begin{aligned} z &= \sum_{i\in [p]} z^{(i)} \\ &= \sum_{i \in[p]} \left(\sum_{j\in [n]} D_jf_i(j) \right) \\ &= \sum_{j\in [n]} D_jf(j) \\ &= D_a \end{aligned} $$

「分散データの安全な更新」の実現方法

各 Party $P^{(i)}$ が保持する分散データの集合を $D^{(i)} \ (|D^{(i)}| = n)$ とします。集合 $D^{(i)}$ における、$j \ (1 \leq j \leq n)$ 番目のデータを $D^{(i)}_j$ とします。

例えば、$a$ 番目のデータ $D_a ( = D^{(1)}_a + D^{(2)}_a + \cdots + D^{(p)}_a)$ に対して、安全に $c$ を加算することを考えます。

まず、下記点関数 $f$ をシェア化し、各 Party $P^{(i)}$ にその関数シェア $f_i$ を送信します。

$$ f(x) = \begin{cases} c &\quad x = a, \\ 0 &\quad otherwise \end{cases} $$

各 Party $P^{(i)}$ が各 $j (1 \leq j \leq n)$ に対して以下を計算し、データを更新します。

全ての $j$ に対して以下の計算を実施しているため、実際にどのデータに $c$ を加算しようとしているのかは秘匿されていることに留意してください。

$$ D^{(i)}_j \leftarrow D^{(i)}_j + f_i(j) $$

$a$ 番目のデータ $D_a$ は、更新後 $D_a + c$ になっており、それ以外のデータ $D_j (j \neq a)$ は $D_j$ のままになっています。

$$ \sum_{i \in [p]} (D^{(i)}a + f_i(a)) = D_a + c\\ \sum{i \in [p]} (D^{(i)}_j + f_i(j)) = D_j \ (\rm{if} \ \it{j \neq a}) $$

関数シェア $f_i$ の実体

前章で、点関数 $f$ のシェア $f_i$ を生成する工程がありましたが、$f_i$ の実体については説明していませんでした。この章で簡単に説明したいと思います。

ただし、本記事では詳細な Algorithm の説明は行いません。詳細な情報は [1] をご参照ください。

FSS を実行する際は、大きく分けて2つのアルゴリズムを実行します。

Gen Algorithm ($f_i$ を生成する)
Eval Algorithm ($f_i$ を用いて計算する)

詳細は割愛しますが、Eval Algorithm 内では、各ノードに疑似乱数文字列を持つ二分木 (binary tree) を使用して計算を進めます。実は関数シェアは、この二分木を構成する「鍵」の役割を担います。

例えば 2-party DPF の場合、参考文献 [1] の Algorithm 1 (Gen Algorithm) を実行することで、

関数シェア $(f_0, f_1)$ に相当する鍵 $(k_0, k_1)$ を生成します。

そして [1] の Algorithm 2 (Eval Algorithm) において、先ほど生成した鍵 $(k_0, k_1)$ を使用して計算を進めることで、$f_0(x), f_1(x)$ に相当する値が計算できます。

まとめ

FSS は関数 $f$ をシェア化する手法である。
FSS は、下記を行うことをモチベーションとして提案された技術である。安全な検索分散データの安全な更新
「安全な検索」と「分散データの安全な更新」を行うために、DPF (Distributed Point Function) という関数が重要な役割を果たす。

参考文献

[1] https://www.iacr.org/archive/eurocrypt2015/90560300/90560300.pdf

[2] https://www.iacr.org/archive/eurocrypt2014/84410245/84410245.pdf