準同型暗号化の仕組み

準同型暗号化は、他の暗号化と同じように、データの機密性や秘匿性を保持するための手段です。他のタイプの暗号化と異なるのは、データを暗号化した後でも、そのデータの秘匿性を保持しながら、データに対する「操作」(数学演算)を実行できることです。

この手法が画期的なのは、暗号化されたデータは通常、復号化しない限り意味をなさないことです。それまで、データを他の人と共有したければ、相手を信頼して復号化したデータの中身を見られるようにするか、そのデータでの共有作業をあきらめるしかありませんでした。

しかし、準同型暗号化を使用すれば、暗号化されたデータを相手と共有し、その当事者に暗号化前のデータの中身を知られることなく、そのデータを操作してもらえるようになります。

準同型暗号化とは？

そもそも「準同型」とはどういう意味なのでしょうか。

数学に詳しい人でなくても理解できるように説明してみましょう。準同型という言葉は、「同じ構造」を意味するギリシャ語に由来します。これは、何らかの対象に対して演算を実行でき、写像後もその対象の構造が保持されることを意味します。

数学的に言えば、「群準同型とは、群演算を保持する群間の写像」ということになります。

しかし、これでは分かりにくいので、(不完全ながら)極めて単純な例を見てみましょう。

例

2つの数字があるとしましょう。まず、この2つの数字を足し合わせてから、最後の桁を取り出します。次に、この2つの数字の最後の桁を取り出してから、足し合わせます。すると、両方の結果は同じになるはずです*。

(**「2つの数字が28と19だったら、最初の結果は7で、2番目の結果は17になりますよね」と言われれば、おっしゃるとおりです。これが不完全な例であることは承知していますが、今はできる限り群論から離れて説明しようとしています。ですから、2つの数字を足しても10を超えない例でお考えください。そして、もっとよい例があればぜひ教えてください)

実行できる演算は、加法、乗法、またはその両方です。私の不完全な例を参考にしていただければ、先の話が乗法にも当てはまることがお分かりいただけるでしょう。「部分準同型」暗号や「完全準同型」暗号といった言葉を耳にしたことがあるかもしれませんが、その違いは、写像がまだ機能しているデータに対して、どの演算を実行できるのかという点にあります。

準同型暗号化の種類

各種類の基本的な違いは、暗号文に対して実行できる数学演算の回数にあります。

• 部分準同型暗号化(PHE)：PHEの「部分」とは、暗号化された値に対して、1種類の数学演算のみ実行できることを意味します。したがって、暗号化されたデータに対して、加法か乗法のどちらかを無制限に実行できます。
• 制限付き準同型暗号化(SHE)：「制限付き」とは、加法と乗法の両方の準同型演算をサポートするという点でPHEより汎用的であるものの、暗号化されたデータに対して実行できる演算の回数が限られていることを意味します。
• 完全準同型暗号化(FHE)：PHEとSHEが演算に制限があるのに対し、完全準同型暗号化では、暗号化されたデータに対して、加法と乗法の両方の演算を無制限に実行できます。

準同型暗号化の仕組み

暗号技術に関心のある方は、部分準同型方式の1つであるRSAについてすでにご存知かもしれません。RSAでは乗法が使用されますが、その理由は、メッセージを指数で累乗することで暗号化が行われるからです。以下に言葉と記号で説明しましょう。

暗号文Cは、公開されている暗号化指数でメッセージmを累乗したもので、すべてn (適切に選択された2つの大きな素数を掛け合わせた結果)を法とします。

これは、次のように表せます。

C1 = (m1^e) (mod n)

別のメッセージに対して同じ演算を実行し、そのメッセージをm2とすると、次のようになります。

C2 = (m2^e) (mod n)

この2つの暗号文C1とC2を掛け合わせると、次のようになります。

(m1^e) (mod n) ✕ (m2^e) (mod n)

これは、次のように書き換えることができます。

(m1^e) (mod n) ✕ (m2^e) (mod n) = ( (m1^e) ✕ (m2^e) ) (mod n) = ( (m1 ✕ m2) ^e) (mod n)

メッセージを暗号化してから掛け合わせれば、その逆の操作(メッセージを掛け合わせてから暗号化)と同じ結果が得られます。したがって、RSAは乗法を用いた部分準同型暗号化となります。

準同型暗号化はユースケースが限られる

だからと言って、すべてのデータにRSAを使用して、自分を準同型のエキスパートとアピールすることのないようにしてください。超高速なAESなどの他の暗号化方法と比べて、RSAは動作が遅くてコストがかかります。そのためRSAは大きなデータブロック全体ではなく、鍵などの小さなデータの暗号化に使用します。

このブログはこちらの英語ブログの翻訳です。