💻 computer science

Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

本論文は、CKKS 暗号における mod 関数の高精度な多項式近似法を提案し、BitStack や CRTStack といった効率的なデータパッキング方式、ホモモルフィック丸め、秘密共有からの CKKS 暗号文への変換など、その応用を通じて暗号計算の効率性と精度を大幅に向上させたことを報告しています。

原著者： Yufei Zhou

公開日 2026-04-08

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Yufei Zhou

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🎭 物語の舞台：「見えない箱」と「魔法の計算」

まず、**「ホモモルフィック暗号（HE）」という技術を想像してください。
これは、「中身が見えない透明な箱」**にデータを入れて、その箱を渡す技術です。

通常： 計算をするには箱を開けて中身を見る必要があります（＝秘密が漏れる）。
この技術： 箱を開けずに、そのまま箱の上で「足し算」や「掛け算」ができます。

しかし、ここには大きな**「弱点」がありました。
この魔法の箱は、「足し算」と「掛け算」は得意ですが、「割り算の余り（Mod）」**という計算が苦手だったのです。

例え： 「10 個のリンゴを 3 人分けすると、1 人 3 個で 1 個余る」という計算です。
問題点： 既存の技術では、この「余り」を出すのが非常に難しく、精度が悪かったり、計算範囲が狭すぎたりしました。まるで、特定の数字しか計算できない「壊れた電卓」のような状態でした。

🛠️ 解決策：新しい「余り」の出し方

この論文の著者たちは、この「壊れた電卓」を直すために、「チェビシェフ級数（Chebyshev series）」という高度な数学の道具を使って、「余り」を多項式（複雑な式）で完璧に再現する方法を考え出しました。

🌊 波のイメージ

「余り」の計算は、グラフにすると「階段」のようにギザギザしています。これを滑らかな波（多項式）で包み込むのは通常、非常に難しいです。

これまでの方法： 波の一部しかカバーできず、ギザギザの頂点で大きくズレていました。
今回の方法： 波の形を精密に調整し、**「入力される数字の全範囲」**で、ギザギザの階段をほぼ完璧に追従する波を作りました。
結果： 計算の誤差が10 億分の 1（ $10^{-8}$ ）レベルまで小さくなり、実用レベルの精度になりました。

📦 応用編 1：「詰め放題」のパッキング術（BitStack & CRTStack）

この「正確な余り計算」ができるようになったことで、**「データの詰め方」**に革命が起きました。

🍱 お弁当箱の例え

CKKS という暗号方式には、1 つの箱（暗号文）に**「おにぎり（データ）」を 3 万個（スロット）まで**詰め込める能力があります。しかし、従来の詰め方だと、おにぎりのサイズがバラバラだったり、隙間ができたりして、箱の容量を無駄にしていました。

著者たちは、この「余り計算」を使って、**「BitStack（ビット積み）」と「CRTStack（中国の剰余定理積み）」**という 2 つの新しい詰め方を提案しました。

BitStack（積み木方式）：
- 小さな数字を「2 進数（0 と 1 の積み木）」として、1 つの大きな数字に重ねて詰め込みます。
- 必要なら、後から「余り」を計算して、積み木をバラバラに分解（アンパック）できます。
- メリット： 非常にコンパクトに詰められます。
CRTStack（パズル方式）：
- 異なる「余り」のルール（法）を使って、複数のデータを同時にパズルのように組み合わせます。
- メリット： 分解する際、**「並列処理」**ができるので、とても速いです。

🚀 効果：
これにより、ユーザーは**「送信するデータ量を劇的に減ら」**すことができます。

従来： 100MB のデータを暗号化して送る。
今回： 同じデータを、1MB 以下に圧縮して送れるようになりました。
イメージ： 重い荷物を、魔法の压缩袋に入れて、スマホからでもサクッと送れるようになった感じです。

🔄 応用編 2：「秘密の分け合い」から「暗号」へ

もう一つのすごい応用は、**「秘密分散（Secret Sharing）」**という技術との連携です。

秘密分散： 重要な鍵を「パズルの破片」のように何人かに分け、全員が揃わないと鍵が開かない仕組みです。
課題： この「破片」を、サーバーが計算できる「暗号化された箱」に変換するのが難しかったです。

この論文では、「余り計算」を使うことで、破片を箱に変えるプロセスを自動化しました。

結果： 複数の人が持っていた「秘密の破片」を、サーバーが**「暗号化された箱」に丸ごと変換**できるようになりました。これにより、プライバシーを守ったまま、複雑な計算が可能になります。

🏆 まとめ：何がすごいのか？

この論文の核心は、**「難しい計算（余り）を、高精度な『波』で再現し、それを応用してデータの『詰め方』を劇的に改善した」**ことです。

精度： ほぼ完璧な計算（誤差 10 億分の 1）。
効率： データ転送量が 100 分の 1 以下に減り、スマホなどの弱い端末でもクラウド計算が現実的になりました。
応用： 医療データ、遺伝子データ、画像処理など、「小さな数字」を扱うあらゆる分野で、プライバシーを守ったまま AI 計算などが飛躍的に速くなります。

一言で言うと：
「暗号化されたデータの上で、これまで『無理やり』だった計算を、**『滑らかで正確な魔法』に変え、さらに『荷物（データ）を極小に圧縮して送れる』**ようにした画期的な技術」です。

論文「Efficient Mod Approximation and Its Applications to CKKS Ciphertexts」の技術的サマリー

この論文は、準同型暗号（HE）の主要な方式の一つである CKKS において、離散性を持つ「mod 関数（剰余演算）」を高精度に近似する新たな手法を提案し、その応用としてデータパッキング効率の向上や秘密共有からの変換などを実現した研究です。以下に詳細をまとめます。

1. 背景と課題 (Problem)

CKKS の限界: CKKS 方式は近似実数演算に優れており、SIMD（Single Instruction Multiple Data）によるベクトル処理が可能ですが、非線形かつ不連続な演算（特に mod 演算）を直接サポートしていません。
既存手法の課題: 既存の mod 近似手法（三角関数を用いたものなど）は、入力領域の限られた部分区間でのみ高精度であり、入力領域全体（特に隣接する倍数の中間点など）では誤差が急増するという問題がありました。
実用上のボトルネック: 小整数（画像データ、遺伝子データなど）を暗号化してクラウドに送信する際、1 つの暗号文に複数のデータを詰め込む（パッキングする）ことで通信コストを削減したいという需要がありますが、暗号文内のデータを分離（アンパッキング）する際に mod 演算が必要であり、これが高精度かつ効率的に行えないことが課題となっていました。

2. 提案手法 (Methodology)

2.1. 高精度な mod 関数の多項式近似

著者らは、入力区間 $[0, B]$ 内のすべての整数点において高精度に mod 関数を近似する新しい手法を提案しました。

手法: 多項式補間と**チェビシェフ級数（Chebyshev series）**の組み合わせを使用。
アプローチ:
1. 離散サンプル点 $(i, i \mod p)$ を取得。
2. 入力範囲を $[-1, 1]$ にマッピングし、チェビシェフ多項式 $T_n(x)$ の係数を最小二乗法で求解。
3. 数値的安定性の確保: 得られた係数が大きくなると CKKS における誤差増幅が起きるため、係数をスケーリングファクター $\delta$ で割って 1 未満に抑える最適化を行い、誤差増幅を抑制。
4. 評価: 高次数多項式の評価には、Paterson-Stockmeyer 法（チェビシェフ基底版）を採用し、乗算深度（Multiplicative Depth）を最小化。
特徴: 入力区間全体で均一に高精度（誤差 $10^{-8}$ 以下）を実現し、不連続点での誤差爆発を防ぎます。

2.2. 効率的なデータパッキング方式

提案した mod 近似を活用し、小整数入力向けの 2 つのパッキング方式を設計しました。

BitStack:
- 複数の小整数をバイナリ表現として連結し、1 つの大きな整数としてパッキングします。
- アンパッキング: 上位ビットから順に mod 演算（ $x \mod 2^k$ ）を繰り返し適用することで、各層のデータを抽出します。
- 特徴: 構造がコンパクトですが、抽出が逐次的に行われるため乗算深度を消費し、誤差が層間で蓄積する可能性があります。
CRTStack:
- 中国剰余定理（CRT）に基づき、互いに素な法 $P_1, \dots, P_d$ を用いて連立合同式を構築し、1 つの整数にパッキングします。
- アンパッキング: 各法 $P_i$ に対する mod 演算を並列に実行することでデータを抽出します。
- 特徴: 並列処理が可能で、層ごとの誤差が独立しているため精度が高く、中間層の精度低下がありません。

2.3. その他の応用

ホモモルフィック丸め（Rounding）: mod 関数を用いて、Floor, Ceil, Round 関数を高精度に実装（誤差 $10^{-10}$ まで）。
秘密共有から CKKS への変換: 加法秘密共有（Additive Secret Sharing）のシェアを、秘密共有スキームを変更することなく、CKKS 暗号文に変換する完全な変換スキームを提案。

3. 主要な貢献 (Key Contributions)

全入力区間での高精度 mod 近似: 不連続・周期的な性質を持つ mod 関数を、多項式補間とチェビシェフ級数を用いて入力区間全体で高精度に近似する手法を確立。
効率的なパッキング方式の設計: BitStack と CRTStack を提案し、CKKS の平文空間利用率を大幅に向上させ、暗号文のアップロードコストを削減。
丸め演算の実装: 小整数の CKKS 暗号文に対する高精度な丸め演算を実現。
秘密共有から CKKS への変換: 既存の秘密共有スキームを改変せず、CKKS 暗号文へ変換する初の完全な変換スキームを提案。

4. 実験結果 (Results)

近似精度:
- 既存手法（Lee et al. [LLL+21] や OpenFHE 標準）と比較し、入力区間全体で平均絶対誤差を劇的に改善。
- 多項式次数 45 以上で誤差が $10^{-8}$ オーダーに達し、既存手法（誤差が 1 以上になる場合も）を凌駕。
データパッキング性能:
- BitStack のアンパッキング: 既存の比較関数ベースや Scheme Switching 手法と比較し、実行時間を約 1000 秒から 15 秒程度に短縮し、誤差も数桁改善。
- CRTStack vs BitStack: CRTStack は並列化によりアンパッキング時間を短縮（BitStack より高速）でき、精度も高いが、法的选择により冗長性が生じる。
- 通信コスト削減: 単純な CKKS パッキングと比較して、Combine 2（VecConcat + CRTStack + ImgConcat）は通信コストを約 2 桁削減（2492 MB $\to$ 26 MB）。
Transcipher 比較:
- 代表的な Transcipher 方式（Rubato）と比較。
- ユーザー側の暗号化時間が短く、サーバー側のアンパッキング時間も Rubato（407 秒）に対して約 1.6 倍高速（156 秒）。
- 復号後の誤差も Rubato より 1 桁小さく、中程度の帯域幅環境（400-600 KB/s）で最も低い総遅延を示しました。

5. 意義と結論 (Significance)

実用性の向上: 小整数データ（画像、遺伝子データなど）を扱うプライバシー保護計算において、通信オーバーヘッドと計算コストの両方を大幅に削減する実用的なソリューションを提供しました。
機能性の拡張: CKKS 本来持っていなかった「mod 演算」を高精度に実装することで、暗号文上での丸め処理や、秘密共有との相互運用性を可能にし、HE の応用範囲を拡大しました。
将来への示唆: 現在の手法は小整数入力に限定されていますが、mod 関数の近似技術自体は、HE における非線形演算の処理や、より複雑なプロトコルの設計に対する重要な知見を提供しています。

総じて、この論文は CKKS における「mod 演算」という長年の課題に対し、数学的な近似手法とシステム設計の両面から解決策を提示し、実社会でのプライバシー保護データ処理の実現可能性を大きく高めた画期的な研究と言えます。