準同型暗号とは？簡単な解説とPythonでの実装

Last updated at 2024-11-08Posted at 2024-11-07

はじめに

準同型暗号（Homomorphic Encryption） は、データを暗号化したまま計算や処理を行うことができる画期的な暗号技術です。
これにより、データのプライバシーを保護しつつ、安全にデータ分析や処理が可能になります。

Appleのブログ記事を読んで、準同型暗号（Homomorphic Encryption） の存在を知り、簡単に調べた内容をまとめました。

Apple Machine Learning Research - Homomorphic Encryption

これらの技術はAppleのLLMで使用される（されている？）可能性が高く、AI時代のプライバシー保護の先駆けとなる重要な技術の1つといえそうです。

本記事では、準同型暗号の基本概念と、Pythonでの簡単な実装例をご紹介します。

参考リンク

より詳細な解説については、以下の記事を参考にしてください。

準同型暗号とは？

基本概念

通常、データを暗号化すると、そのデータに対する計算や分析は難しくなります。
準同型暗号は、暗号化されたデータ同士で直接計算を行い、その結果も暗号化されたまま得られる特徴を持ちます。
最終的に、復号することで計算結果を確認できます。

主な利点

プライバシー保護: データを暗号化したまま第三者に処理を委託できる。
セキュリティ強化: データ漏洩のリスクを低減。
クラウドコンピューティングとの相性: クラウド上で安全にデータ処理が可能。

準同型暗号の種類と特徴の詳細説明

準同型暗号には、同型性のレベルや対応する演算に応じていくつかの種類があります。
それぞれの特徴を理解することで、用途に応じた適切な暗号方式を選択することが可能です。

部分準同型暗号（Partial Homomorphic Encryption, PHE）

部分準同型暗号は、特定の一種類の演算（加算または乗算）のみについて同型性を持つ暗号方式です。
代表的なものに以下があります：

パイリー暗号（Paillier Cryptosystem）: 加算に対して同型性を持つ。
RSA暗号: 乗算に対して同型性を持つ。

利点

計算が比較的高速であり、実装が容易。
特定の用途に対して高い効率性を発揮。

欠点

一種類の演算に限定されるため、複雑な計算には向かない。

多少準同型暗号（Somewhat Homomorphic Encryption, SHE）

多少準同型暗号は、加算と乗算の両方に対して部分的に同型性を持つ暗号方式です。
これにより、限られた回数の演算が可能となります。

利点

複数種類の演算が可能。
パフォーマンスと柔軟性のバランスが取れている。

欠点

演算回数に制限があり、大規模な計算には適さない。

完全準同型暗号（Fully Homomorphic Encryption, FHE）

完全準同型暗号は、任意の数の加算および乗算を暗号化されたデータに対して実行できる暗号方式です。
これにより、複雑な計算やアルゴリズムの実行が可能となります。

利点

任意の計算が可能で、非常に柔軟。
データのプライバシーを完全に保護しながら高度な処理が実現可能。

欠点

計算コストが非常に高く、実用化にはまだ課題が多い。
実装が複雑で、専門的な知識が必要。

Pythonでの準同型暗号実装例

ここでは、パイリー暗号（Paillier Cryptosystem） を用いた簡単な準同型暗号の実装を紹介します。
パイリー暗号は加算に対して準同型性を持つ部分準同型暗号です。

必要なライブラリのインストール

まず、必要なライブラリをインストールします。gmpy2は大きな整数の計算に使用します。

pip install gmpy2

パイリー暗号の実装

以下のコードは、鍵生成、暗号化、復号、同型加算を行う簡易的な実装です。

import random
from math import gcd
import gmpy2

def generate_keypair(bits=16):
    """
    Paillier暗号の公開鍵と秘密鍵のペアを生成する
    
    Args:
        bits (int): 素数のビット長（デフォルト: 16）
    
    Returns:
        tuple: ((n, g), (lambda_n, mu))
            - n: 2つの素数の積
            - g: 生成元
            - lambda_n: カーマイケル関数λ(n)
            - mu: λ(n)の法nにおける乗法的逆元
    """
    # 指定されたビット長の範囲で2つの素数p, qを生成
    p = gmpy2.next_prime(random.randint(2**(bits-1), 2**bits))
    q = gmpy2.next_prime(random.randint(2**(bits-1), 2**bits))
    
    # 公開鍵nを計算: n = p * q
    n = p * q
    # λ(n)を計算: lcm(p-1, q-1)
    lambda_n = gmpy2.lcm(p-1, q-1)
    # 生成元gを設定（簡略化のためn+1を使用）
    g = n + 1
    # μを計算: λ(n)の法nにおける乗法的逆元
    mu = gmpy2.invert(lambda_n, n)
    
    return (n, g), (lambda_n, mu)

def encrypt(public_key, plaintext):
    """
    平文を暗号化する
    
    Args:
        public_key (tuple): 公開鍵(n, g)
        plaintext (int): 暗号化する平文
    
    Returns:
        int: 暗号文
    """
    n, g = public_key
    n_sq = n * n  # n^2を計算
    
    # nと互いに素なランダムな数rを選択
    while True:
        r = random.randint(1, n-1)
        if gcd(r, n) == 1:
            break
    
    # 暗号化: c = g^m * r^n mod n^2
    return (pow(g, plaintext, n_sq) * pow(r, n, n_sq)) % n_sq

def decrypt(public_key, private_key, ciphertext):
    """
    暗号文を復号する
    
    Args:
        public_key (tuple): 公開鍵(n, g)
        private_key (tuple): 秘密鍵(lambda_n, mu)
        ciphertext (int): 復号する暗号文
    
    Returns:
        int: 復号された平文
    """
    n, g = public_key
    lambda_n, mu = private_key
    n_sq = n * n
    
    # 復号: m = L(c^λ(n) mod n^2) * μ mod n
    # ここでL(x) = (x-1)/n
    l = (pow(ciphertext, lambda_n, n_sq) - 1) // n
    return (l * mu) % n

def homomorphic_add(public_key, c1, c2):
    """
    2つの暗号文の同型加算を行う
    
    Args:
        public_key (tuple): 公開鍵(n, g)
        c1, c2 (int): 加算する2つの暗号文
    
    Returns:
        int: 加算結果の暗号文
    """
    n, _ = public_key
    n_sq = n * n
    # 暗号文同士の積を取ることで平文の和が得られる
    return (c1 * c2) % n_sq

def main():
    # 鍵ペアの生成
    public_key, private_key = generate_keypair()
    print(f"公開鍵 (n): {public_key[0]}")
    print(f"秘密鍵 (lambda): {private_key[0]}")
    
    # テスト用の平文を設定
    m1, m2 = 5, 10
    print(f"平文 m1: {m1}, m2: {m2}")
    
    # 平文を個別に暗号化
    c1 = encrypt(public_key, m1)
    c2 = encrypt(public_key, m2)
    print(f"暗号文 c1: {c1}")
    print(f"暗号文 c2: {c2}")
    
    # 暗号文同士の同型加算を実行
    c_sum = homomorphic_add(public_key, c1, c2)
    print(f"暗号文の和 c_sum: {c_sum}")
    
    # 加算結果の暗号文を復号
    m_sum = decrypt(public_key, private_key, c_sum)
    print(f"復号された和 m_sum: {m_sum}")
    print(f"実際の和: {m1 + m2}")
    # 同型演算の結果が正しいことを確認
    assert m_sum == m1 + m2, "同型演算の結果が一致しません！"

if __name__ == "__main__":
    main()

コードの説明

鍵生成 (generate_keypair):
- 大きな素数 p と q を生成し、n = p * q を計算。
- 公開鍵は (n, g)、秘密鍵は (λ, μ)。
暗号化 (encrypt):
- ランダムな数 r を選び、c = g^m * r^n mod n² を計算。
復号 (decrypt):
- m = (L(c^λ mod n²) * μ) mod n を計算し、元の平文を取得。
- ここで L(u) = (u - 1) / n。
同型加算 (homomorphic_add):
- 暗号文同士を乗算し、c_sum = c1 * c2 mod n² とすることで、対応する平文の和を得る。
メイン関数 (main):
- 鍵を生成し、平文 m1 と m2 を暗号化。
- 暗号文を加算し、結果を復号して和を確認。

実行例

公開鍵 (n): 35317
秘密鍵 (lambda): 17640
平文 m1: 5, m2: 10
暗号文 c1: 2533
暗号文 c2: 18692
暗号文の和 c_sum: 25825
復号された和 m_sum: 15
実際の和: 15

この例では、平文 5 と 10 を暗号化し、暗号文を加算した結果を復号して 15 を得ています。
これにより、データを暗号化したまま安全に計算ができることが確認できます。

実世界での応用例の紹介

準同型暗号は、その強力なプライバシー保護機能により、さまざまな分野での応用が期待されています。
以下に、いくつかの具体的な応用例を紹介します。

クラウドコンピューティング

クラウドサービスでは、大量のデータを外部サーバーに保存し、処理を依頼することが一般的です。
しかし、データを暗号化せずに送信すると、プライバシーやセキュリティのリスクが伴います。
準同型暗号を利用することで、データを暗号化したままクラウド上で計算を行い、結果も暗号化された状態で受け取ることが可能です。
これにより、クラウドサービスの利便性を享受しつつ、データの機密性を保護できます。

データ分析と機械学習

企業や研究機関では、機密性の高いデータを用いた分析や機械学習モデルのトレーニングが必要です。
準同型暗号を用いることで、暗号化されたデータ上で直接モデルのトレーニングや予測を行うことが可能となります。
これにより、データのプライバシーを保護しながら、統計的な分析やAI技術の活用が実現します。

金融業界

銀行やフィンテック企業では、顧客の取引データや個人情報を安全に管理する必要があります。
準同型暗号を利用することで、暗号化された状態でトランザクションの処理や分析を行うことが可能となり、データ漏洩のリスクを大幅に低減できます。
さらに、顧客データを第三者と共有する際にも、安全にデータを提供する手段として有効です。

他の準同型暗号方式の紹介

パイリー暗号以外にも、さまざまな準同型暗号方式が存在します。以下に代表的なものを紹介します。

ElGamal暗号

ElGamal暗号は、離散対数問題に基づく公開鍵暗号方式で、乗算に対して同型性を持ちます。
具体的には、暗号文の乗算が平文の乗算に対応します。
ElGamal暗号は、暗号化と復号のプロセスが比較的シンプルであり、暗号化強度も高いとされています。

特徴

乗算に対して同型性を持つ部分準同型暗号。
鍵生成、暗号化、復号がシンプル。
暗号文サイズが大きくなる傾向がある。

BFV暗号（Brakerski/Fan-Vercauteren暗号）

BFV暗号は、完全準同型暗号の一種であり、加算および乗算の両方に対して同型性を持ちます。
これにより、任意の複雑な計算を暗号化されたデータ上で実行することが可能です。

特徴

完全準同型暗号として、任意の計算が可能。
パフォーマンスの最適化が進んでおり、実用化に向けた研究が活発。
計算コストが高く、効率的な実装が求められる。

CKKS暗号（Cheon-Kim-Kim-Song暗号）

CKKS暗号は、同型性を持つ暗号方式の一つであり、特に近似計算に強みを持ちます。
機械学習やデータ分析において、浮動小数点数を扱う際に有効です。

特徴

浮動小数点数の近似計算に対応。
同型性を持つため、暗号化されたデータ上での複雑な計算が可能。
近似誤差が生じるため、精度の管理が必要。