AI・機械学習

CKKS – 加算と乗算

CKKS – Addition and Multiplication (jeremykun.com)

8 pointsby ibobev2026年10月17日0 コメント

要約

この記事は、CKKS（Cheon-Kim-Kim-Song）準同型暗号方式に関するチュートリアルシリーズの一部です。前回の記事で導入された暗号化・復号のルーチンに続き、今回は復号化（リニアライゼーションなし）における暗号文の加算と乗算の操作について解説します。エラーの解析や、暗号文の構造がどのように変化するかをコードと共に示しています。

全文翻訳

CKKS — 加算と乗算

これはCKKS準同型暗号スキームに関するチュートリアルシリーズの一部です。

前回の記事では、対称鍵および公開鍵の暗号化・復号ルーチンを紹介し、モジュロ多項式演算（NTTをブラックボックスとして使用）を実装しました。この記事では、暗号文（リニアライゼーションなし）に対して実行される加算および乗算操作について説明します。

CKKSに既に精通している方のために、ここではまだスキームのRNS形式を避け、64ビットのモジュラス $Q$ を使用しているため、一時的に暗号学的セキュリティを無視しています。

この記事のコードはこのプルリクエストにあります。

CKKS暗号文構造のリマインダー

簡単に復習すると、CKKSにおける対称鍵および公開鍵設定での暗号文は、環 $(\mathbb{Z}/Q\mathbb{Z})［x］ \Big / (x^N+1)$ における多項式のペア $(c_0, c_1)$ です。対称鍵と公開鍵の場合で構造は異なりますが、復号ルーチンは共通しており、それは $(1, s(x))$ とのドット積です。ここで $s(x)$ は秘密鍵多項式です。誤差が十分に小さければ、デコードアルゴリズムはスケールで割り、誤差を効果的に除去します。

対称鍵暗号の場合、構造は次のようになります。

\[ c_0(x) = -(c_1(x) s(x)) + m(x) + e(x) \]

ここで、$c_1(x)$ は一様ランダム、$e(x)$ は離散ガウス誤差多項式、$s(x)$ は三項秘密鍵、$m(x)$ は（エンコードされた）平文です。1

公開鍵暗号の場合、表記は似ていますが、$(b, a)$ は「平文」としてゼロ多項式を持つ対称暗号であり、その後 $u(x)$ は新しい一様三項ランダム多項式、そして $e_1, e_2$ も誤差多項式であり、以下の式に従います。

\[ \begin{aligned} c_0(x) &= b(x) u(x) + e_1(x) + m(x) \ c_1(x) &= a(x) u(x) + e_2(x) \end{aligned} \]

暗号文の加算

まず、暗号文の加算から始めましょう。

同じ秘密鍵 $s(x)$ の下で、それぞれ $m_c + e_c$ と $m_d + e_d$ を復号する2つの暗号文 $(c_0, c_1)$ と $(d_0, d_1)$ を考えます。これらの暗号文の和は $(c_0 + d_0, c_1 + d_1)$ として定義されます。加算の定義は対称鍵暗号文と公開鍵暗号文で同じですが、解析は若干異なります。

対称鍵暗号の場合、$c_1$ と $d_1$ はそれぞれランダムな一様サンプルなので、それらの和も一様ランダムになります。2 $c_0 + d_0$ については、定義により

\[ \begin{aligned} c_0 + d_0 &= [-c_1 \cdot s + m_c + e_c] + [-d_1 \cdot s + m_d + e_d] \ \end{aligned} \]

そして、再配置により

\[ \begin{aligned} c_0 + d_0 &= [-c_1 \cdot s + m_c + e_c] + [-d_1 \cdot s + m_d + e_d] \ &= -((c_1 + d_1) \cdot s) + (m_c + m_d) + (e_c + e_d) \end{aligned} \]

再配置された式の誤差部分ではない項は、$m_c + m_d$ の暗号化構造に正確に適合します。しかし、誤差部分は、新たに暗号化した際のガウス誤差サンプルとは正確には一致しません。3

これは、CKKSの誤差解析の厄介な詳細に初めて触れる部分です。進むにつれて、暗号文に対してますます複雑な操作を行うことになりますが、この誤差項は、特に「CKKSプログラム」全体を任意の加算、乗算、および暗号文管理操作のシーケンスとして考えると、解析的に制御するのがますます困難になります。

このため、CKKS暗号文のノイズを解析するより直接的な方法は、誤差項の分布が「サブガウス」https://en.wikipedia.org/wiki/Sub-Gaussian_distributionと呼ばれる性質を持つことを許容することです。詳細はこのチュートリアルの将来の記事に譲りますが、今のところサブガウス確率変数は、ガウス分布確率変数よりも少なくとも速く減少する裾を持つと考えてください。特に、Chernoff-Hoeffdingバウンドのようなバウンドはサブガウス分布確率変数に対して成り立つため、「このCKKS暗号文の誤差項は、$Q/2$ を超えない（したがって、正しいメッセージに復号・デコードされる）確率が $2^{-100}$ 以下である」といったことを言うことができます。

今のところ、私たちが知っておくべきことは、2つのサブガウス確率変数の和もサブガウスであり、それらの「分散」パラメータが合計されるということです。4 つまり、誤差は爆発せず、代わりに2つの加算項の誤差に線形に増加します。

これらの操作は多項式演算を必要とするだけなので、その実装は簡単で、このコミットで行われています。

from ckks_types import Ciphertext

def add(ct1: Ciphertext, ct2: Ciphertext) -> Ciphertext:
    c0, c1 = ct1.data
    d0, d1 = ct2.data
    return Ciphertext(data=(c0 + d0, c1 + d1))

暗号文の乗算

次に、乗算に移ります。

再び、それぞれ $m_c + e_c$ と $m_d + e_d$ を復号する2つの暗号文 $(c_0, c_1)$ と $(d_0, d_1)$ を考えます。乗算を定義する直接的な試みは、ある操作が暗号文 $(t_0, t_1)$ を生成すると仮定することから始まるかもしれません。

\[ t_0 + t_1 s = (m_c + e_c)(m_d + e_d) = (c_0 + c_1s)(d_0 + d_1s) \]

しかし、この方程式の左辺と右辺は $s$ に関する多項式であり、次数が異なります。左辺は線形ですが、右辺には $s^2$ の項があります。これは、秘密鍵が $s^2 = as + b$ のような関係を満たす場合にのみ機能します。5 その可能性を除外すると（脚注を参照）、次に良いのは二次であり、ここで $(c_0 + c_1s)(d_0 + d_1s)$ の式が自然な方向性を示します。これは次のように展開されます。

\[ c_0 d_0 + (c_0 d_1 + c_1 d_0)s + c_1 d_1 s^2 \]

そして、これは $(1, s, s^2)$ の新しい「鍵基底」との $(c_0 d_0, c_0 d_1 + c_1 d_0, c_1 d_1)$ のドット積として見ることができます。つまり、暗号文の概念を $(1, s, s^2)$ とのドット積で復号する3項組 $(t_0, t_1, t_2)$ を含むように一般化しています。

この積の構造は、テンソル積としても見ることができます。2つの暗号文のテンソル積は行列を生成します。

\[ \begin{pmatrix} c_0 d_0 & c_0 d_1 \ c_1 d_0 & c_1 d_1 \end{pmatrix} \]

そして、対応する二次形式 $x^TAx$ に $(1, s)$ を入力として使用すると、目的の復号が得られます。

\[ (1, s) \begin{pmatrix} c_0 d_0 & c_0 d_1 \ c_1 d_0 & c_1 d_1 \end{pmatrix} (1, s)^T = c_0 d_0 + (c_0 d_1 + c_1 d_0)s + c_1 d_1 s^2 \]

したがって、「乗算」操作の候補が得られます。

\[ (c_0, c_1) \star (d_0, d_1) = (c_0 d_0, c_0 d_1 + c_1 d_0, c_1 d_1) \]

構成により、2つの暗号文の積の「復号手順」は、$(m_c + e_c)(m_d + e_d) = m_c m_d + (m_c e_d + e_c m_d + e_ce_d)$ という量を与えます。

この式には3つの注目すべき側面があります。第一に、オペランド誤差項の積が含まれており、乗算によって誤差が増加すること（少なくとも二次的に）を示唆しています。第二に、暗号化されている平文（非常に大きいスケーリングファクター $\Delta$ を含む）に依存する線形誤差項が含まれています。最後に、メッセージは固定小数点演算を介してエンコードされているため、最初の項は $\Delta^2$ のスケーリングファクターを持つ値を生成します。つまり、何もせずに復号した場合、基になる平文の積を回復するために、デコード手順の丸めと除算を調整する必要があります。

これらすべてが、私たちが考慮しなければならない問題となります。誤差の増加は管理する必要があり、「リ・スケーリング」と「ブートストラップ」という2つの方法があります。$\Delta^2$ のスケールは $\Delta$ に戻す必要があり、これにより他の暗号文に対して $\Delta$ スケーリングファクターでさらに演算を実行できるようになります。これも「リ・スケーリング」によって管理されます。

最後に、3項組の暗号文構造を2項組の構造に戻す必要があります。そうでなければ、さらなる乗算（テンソル積のアイデアを拡張することによって）は、この暗号文タプルの長さをさらに増加させ、管理不能に大きな非効率的な操作を生み出すことになります（つまり、長さ3の暗号文の積は長さ5の暗号文を生成します）。これを処理する技術は「リニアライゼーション」と呼ばれます。

しかし、この記事の残りの部分では、コードを通じて乗算のこれらの特性を実証したいと思います。

まず、乗算の実装は簡単で、このコミットで行われています。

from ckks_types import Ciphertext, Deg2Ciphertext

def mul(ct1: Ciphertext, ct2: Ciphertext) -> Deg2Ciphertext:
    c0, c1 = ct1.data
    d0, d1 = ct2.data

    t0 = c0 * d0
    t1 = c0 * d1 + c1 * d0
    t2 = c1 * d1
    return Deg2Ciphertext(data=(t0, t1, t2))

新しい型 Deg2Ciphertext に注意してください。これは Ciphertext と同じですが、2項組ではなく3項組を使用します。

次に、同じコミットのこのセクションで、3項組暗号文の復号を実装します。

# encryption.py

def decrypt_deg2(
    ciphertext: Deg2Ciphertext,
    secret_key: PrivateKey,
) -> Plaintext:
    t0, t1, t2 = ciphertext.data
    return t0 + t1 * secret_key + t2 * (secret_key * secret_key)

そのコミットのテストでは、デコードプロセスが二乗されたスケーリングファクターをどのように考慮する必要があるかを確認できます。

# multiplication_test.py

DEFAULT_ENCODING_PARAMS = EncodingParams(
    scale=2**20,
    poly_modulus_degree=8,
    coefficient_modulus=NTT_64_BIT_PRIME,
)

PRODUCT_ENCODING_PARAMS = EncodingParams(
    scale=DEFAULT_ENCODING_PARAMS.scale**2,
    poly_modulus_degree=DEFAULT_ENCODING_PARAMS.poly_modulus_degree,
    coefficient_modulus=DEFAULT_ENCODING_PARAMS.coefficient_modulus,
)

def test_mul_two_asymmetric():
    message1 = ...
    message2 = ...
    expected = ...

    # encode with Delta
    context = CKKSContext(DEFAULT_ENCODING_PARAMS)

    sk, pk = context.generate_asymmetric_keypair()
    pt1 = context.encode(message1)
    ct1 = context.encrypt_asymmetric(pt1, pk)
    pt2 = context.encode(message2)
    ct2 = context.encrypt_asymmetric(pt2, pk)

    ct_product = context.mul_no_relin(ct1, ct2)
    decrypted_product = decrypt_deg2(ct_product, sk)

    # decode with Delta^2
    decoded_product = decode(decrypted_product, PRODUCT_ENCODING_PARAMS)
    np.testing.assert_allclose(decoded_product, expected, rtol=0, atol=0.2)

最後に、誤差の増加の公式を、このコミットの単体テストで実証します。

注記

先に進む前に、上記のいくつかの点に戻りたいと思います。

第一に、誤差の増加が平文の値に依存することを思い出してください。誤差部分は次のようになります。

\[ m_c e_d + e_c m_d + e_c e_d \]

これはCKKSでプログラムを書く上での複雑さを引き起こします。なぜなら、誤差の増加を正しく追跡するには、プログラムの変数の途中値の範囲に対するバウンドが必要になるからです。

機械学習のようなアプリケーションでは、検証セットを使用してこれらの範囲を推定できるため、これは問題ではありません（外れ値が精度に影響することを心配していない場合は、それらの範囲を、例えば1パーセンタイル/99パーセンタイル下限/上限に絞ることさえできます）。しかし、汎用プログラムにとっては、これはCKKSの深刻な制限です。

第二に、スケーリングファクターが誤差の式に現れます。スケーリングファクターを可視化して誤差の式を書くと（今、$m_c, m_d$ を基になるメッセージと考えると）、

\[ \Delta (m_c e_d + e_c m_d) + e_c e_d \]

$\Delta$ を小さくすると誤差の増加を抑えられるのではないかと期待するかもしれません。しかし、リニアライゼーションの後でカバーする「リ・スケーリング」手順は、実際には暗号文を $\Delta$ で割ります。これは、二乗されたスケーリングファクターを $\Delta$ に戻すことと、誤差項を $\Delta$ で割ることの両方の目的を果たします。これにより、誤差の式から $\Delta$ の係数が除去され、誤差の増加は（実質的に）オペランド誤差に対して線形になります。

第三に、そして最後に、次の質問にどれだけ焦点を当てるべきか分かりません。2つの暗号文の積を、オペランド暗号文の構造に似た構造に従うという点で、どの程度「CKKS暗号文」と考えるべきかということです。上記で述べたことは、「ドット積で復号できる」ということだけです。

しかし、このタプル $(c_0 d_0, c_0 d_1 + c_1 d_0, c_1 d_1)$ は特にランダムではありません。対称鍵の場合、2つの多項式を秘密とする「一般化RLWE暗号化」として表現することはできません。一つには、3番目の成分が一様ランダムではなく、$s^2$ は $s$ と独立ではありません。とはいえ、本当に重要なのは、積が安全であるということです。もし積にメッセージ $m_c m_d$ について学ぶことができるような構造があれば、それを利用してオペランドの元のCKKS暗号化を解読できてしまうでしょう。

この記事では、「m」が「メッセージ」を表すにもかかわらず、平文を $m$ で表します。↩︎
これはそれほど明白ではないかもしれません。これは、これらの分布が一様整数 mod $Q$ であるという事実に依存しています。実際、もし $A$ がそのような一様ランダム変数であり、$X$ が $A$ と独立な任意の確率変数（$\mathbb{Z}/Q\mathbb{Z}$ 上）である場合、$A+X$ も mod $Q$ で一様分布します。↩︎
合計の正確な分布は分かりませんが、格子暗号学者はこの状況を詳細に研究しており、Nicholas Genise, Daniele Micciancio, Chris Peikert, and Michael Walter によるこの論文はそれらを分析するための形式化を提供しています。特に、2つの離散ガウスの和は、合計された分散を持つ離散ガウスに「統計的に近い」です。↩︎
これは厳密には対称鍵の場合にのみ当てはまり、特に誤差が独立している場合に当てはまります。それらが依存的になったり（または最初から公開鍵の場合）、合計は依然としてサブガウスですが、分散の公式は異なります。↩︎
実際、2026年8月にIACRに掲載され、CRYPTO 2026で発表された、Aayush Jain, Huijia Lin, Zeyu Liu, and Sagnik Saha による非常に最近の論文では、潜在的に合理的な追加の仮定の下で、$s^2 = s$ または類似の二次方程式を満たす秘密 $s(x)$ を使用して、RLWEベースのFHEを実行できることが証明されています。この論文を詳細に読む時間はまだありませんでしたが、このチュートリアルの終わりに、より高度なCKKSテクニックをカバーする際に、この論文に戻りたいと思います。↩︎