はじめに

この記事では、AONT(All-Or-Nothing Transformation)と呼ばれる秘密分散法の一つを紹介します。秘密分散法については以下の記事で紹介していますので、よろしければご覧ください。

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

AONTを用いた秘密分散は以下の特徴を持っているため、情報を効率的に秘匿化する目的で使用されています。

変換後のデータ容量が元データとほぼ同じ
分割された断片(シェア)を全て集めることで復元する
シェアの大きさを任意に調整できる

ただし、Multi-party Computation(MPC)に使用することができないというデメリットもありますので注意が必要です。MPCについてはこちらの記事を参照してください。

https://acompany.tech/privacytechlab/multi-party-computation/

それでは、AONTの仕組みについてみていきましょう。

AONTによる秘密分散化の仕組み

あるデータ$m$ をAONTで秘密分散させることを考えます。

この時の秘密分散化処理は以下になります。

データ$m$ を分割した$s$ 個のブロック $m_1, m_2, \cdots, m_s$
秘密分散後の$s+1$ 個のシェア $m_1', m_2', \cdots, m_s', m_{s+1}'$
共通鍵暗号の鍵 $K$
公開された共通鍵暗号の鍵 $K_0$
任意の共通鍵暗号化 Enc(鍵, 平文)

$s$ 番目までの全てのブロックをシェアに変換する $m_i' = m_i \oplus Enc(K, i)$ $i = 1, 2, \cdots, s$
シェアのハッシュ値を得る $h_i = Enc(K_0, m_i' \oplus i)$
$s+1$ 番目のブロックをシェアに変換する $m_{s+1}' = K \oplus h_1 \oplus h_2 \oplus \cdots \oplus h_s$
鍵$K$ を破棄する

上記の方法を用いてデータ$m$ のシェアを生成することができました。この時、シェアのサイズが各ブロックのサイズと同じであることで、変換後のシェアデータ全体の大きさが、変換前のデータとほぼ同じになります。また、分割するブロックのサイズは任意に決めることができます。

復号の仕組み

復号時には以下の方法を用いて元のデータを得ます。

シェアのハッシュ値を得る $h_i = Enc(K_0, m_i' \oplus i)$
共通鍵$K$ を復号する $K= m_{s+1}' \oplus h_1 \oplus h_2 \oplus \cdots \oplus h_s$
シェアからデータ$m$ を復号する $m_i = m_i' \oplus Enc(K, i)$

重要な点は、シェア生成時に破棄した共通鍵$K$ を復号する仕組みです。復号の正しさは以下で確認できます。ただし $a \oplus b \oplus b = a$ という関係を用います。

$$\begin{array}{cll} m_{s+1}' \oplus h_1 \oplus h_2 \oplus \cdots \oplus h_s &=& (K \oplus h_1 \oplus \cdots \oplus h_s) \oplus h_1 \oplus \cdots \oplus h_s \\ &=& K\end{array}$$

このようにして、全てのシェアを集めた時にのみ共通鍵を復号することができることで、秘密分散を実現できました。ただし、共通鍵$K$ がメッセージ$m_i'$ から容易に推定できると情報が漏洩してしまうため、鍵の長さがセキュリティパラメータとなります。実際に使用する場合は適切な暗号方式と鍵を選択する必要がある点に注意してください。

まとめ

この記事のまとめは以下になります。

AONTは全てのシェアを集めることで復元できる秘密分散法の一つ
MPCに使用することはできない
元のデータ容量とほぼ同じ
内部で共通鍵暗号を用いている

参考文献

All-Or-Nothing Encryption and The Package Transform