イデアル類群と離散対数問題を使って加法準同型を実現するCastagnos-Laguillaumie 暗号の解説

Table of Contents

はじめに

この記事では有限巡回群+離散対数問題ベースの暗号を (無理やり) 3つのファミリーに分類して、それぞれの特徴と違い、共通点を探ります。イデアル類群を用いたCL暗号系 (Castagnos-Laguillaumie 暗号系¹²³) についても解説します。

NotebookLMで生成した説明スライド: イデアル類群と準同型暗号の数理

有限巡回群ベースの暗号の分類

現状規格化された有限巡回群/離散対数問題ベースの暗号で一般的に使われているものは「楕円曲線の有理点群」「素数位数の既約剰余類群」の2つしかありません。
そして、これにこの記事で紹介するイデアル類群⁴を加えると、提案されている暗号系ファミリーとしてはほぼ全てになります⁵。
もちろん、RSAその他離散対数問題に帰着できない暗号系は他にも多数あります。

群の名前	アルゴリズム例	ソフトウェア例	鍵サイズ	理論の難しさ（主観）
素数位数の既約剰余類群⁶	DSA, DH	PGP	大きい	比較的やさしい
楕円曲線の有理点群⁷	ECDSA, ECDH	Bitcoin, TLS, PGP	小さい	難しい
イデアル類群⁴	CL暗号(準同型暗号), Buchmann–Williams鍵交換⁸⁹, RDSA2/GPS署名¹⁰	BICYCL¹¹	大きい	難しい

イデアル類群は、楕円曲線の有理点群ほど鍵サイズが小さいわけでもなく、素数位数の既約剰余類群ほど理解しやすいわけでもないので、単に暗号を使いたいだけならば優位性はありません。そのため、もっぱら準同型暗号等の、特殊な操作が必要なケースにおいて使われます。

共通点

群構造が予測不可能であり離散対数問題を解くのが難しいというのがこれらの群の共通点です。

暗号系として気になるのは攻撃手法です。有限巡回群の群構造と、離散対数問題の困難性という共通点を持つため、以下のような攻撃手法が共通で知られています。

指数計算法, 数体ふるい法¹²¹³
ポラード・ロー離散対数アルゴリズム¹⁴¹²

相違点

上記の3つの有限巡回群は「群構造が予測不可能であり離散対数問題を解くのが難しい」という点においては共通ですが、「なぜそれらの群構造が予測不可能なのか」という点については、それぞれの群の間の関連性があるのかどうかもわかっていないというのが現状のようです。

セキュリティパラメータに対して素数位数の既約剰余類群やイデアル類群において安全とされる鍵のサイズは、楕円曲線の有理点群と比べて数十倍大きくなっています。これは楕円曲線の有理点群を使った場合には成立しない攻撃が、素数位数の既約剰余類群やイデアル類群においては成立するため、鍵のサイズを大きく取っておく必要があるためです。

したがって、下部構造を支える群が仮定している暗号学的仮定は、それぞれ違うものだと考える必要があります。具体的には「素数位数の既約剰余類群の離散対数問題」「イデアル類群の離散対数問題」「楕円曲線の有理点群の離散対数問題」は異なる仮定です。

なお、一般の有限巡回群には加法群 $(\mathbb{Z}/n\mathbb{Z},+)$ のような離散対数問題が全く難しくない群も存在します。このように、離散対数問題の困難性は下部構造によっても異なる可能性があります。

一般の有限巡回群に対する攻撃手法が開発されない限りは、攻撃の可能性として最も高いのは、それぞれ個別の有限巡回群の構造を利用した攻撃になるのではないでしょうか。

CL暗号系

概要

CL暗号は加法準同型性¹⁵を持つ公開鍵暗号系です。加法準同型性とは暗号化したまま復号することなく平文の加算が行えるという特徴をもつ暗号方式です。
もっと具体的には以下が安全に成り立つアルゴリズムの組が存在するとき、加法準同型性があるといえます。

鍵生成: (pk, sk) <- KeyGen()
暗号化: (c1, c2) <- Encrypt(pk, m)
復号: m <- Decrypt(pk, sk, (c1, c2))
加算: (c1'', c2'') <- EvalSum(pk, (c1, c2), (c1', c2'))
スカラ倍算: (c1', c2') <- EvalScal(pk, (c1, c2), α)

注) ここで (c1, c2), (c1', c2'),(c1'', c2'')は暗号文、skは秘密鍵、pkは公開鍵、αはスカラ値、mは平文です。

例えば m1 + m2 = Decrypt(pk, sk, EvalSum(pk, Encrypt(pk, m1), Encrypt(pk, m2))) が成立します。これは単純な例ですが、他の操作を何回も適用した後であっても、Decryptすれば元の平文を操作したのと同じ結果が復号の出力値として出てきます。

イデアル類群の数学的な性質

CL暗号ではイデアル類群を使います。
イデアルやイデアル類群の説明についてはこちらのブログ¹⁶¹⁷がわかりやすいです。このブログを踏まえた上で、イデアル類群における、代表元であるイデアルaで表されるイデアルの類を [a]と書きます。すると、以下のような性質が成り立つことがわかっています。

大きな判別式をもつ虚二次体 $K = \mathbb{Q}(\sqrt{-p}$ を考える。このKの類群が巡回群であり、類数がxであるとする。代表元である、とあるイデアルaを用いて、そのイデアルの類を[a]とおくとき、イデアルの積を用いて、イデアルの類を $[1], [a], [a^2], ..., [a^{x-1}]$ で全て表せるようなaが存在する。さらに、それらをイデアル類群の要素とするとき、イデアル類群の要素同士の演算を $[a^n] \oplus [a^m] = [a^{n+m}]$ のように定義することができ、これを $g^n * g^m = g^{n + m}$ のように書く。
虚二次体 $\mathbb{Q}(\sqrt{-d}$ のイデアル類群の要素を簡約化して代表元を2要素の標準形 (x, y)に変換することができる。この変換操作によって、標準形のイデアルにおける、各要素の実部における係数と $\sqrt{-d}$ 部分の係数を小さく（ $O(\sqrt{d})$ 程度に）保つことができる。さらにこの標準形は3要素からなる「二次形式」(a, b, c)と1:1対応している。
大きな判別式をもつ虚二次体 ( $K = \mathbb{Q}(\sqrt{-p})$ ) のイデアル類群の類数 $h_K$ と群構造を計算するアルゴリズムは知られているが、既知のアルゴリズムはサブ指数時間であり、暗号サイズのパラメータに対しては実用上かなり重い。標準形を求める関数をN(・)とすると、 $N\bigl(N(g^a g^b) g^c\bigr) = N\bigl(g^a N(g^b g^c)\bigr) = N(g^a g^b g^c)$ が常に成り立ち、類数や指数 (a,b,c) を知らなくても両者が同じ元であることは標準形を比較することで判定できる。一方で、ある標準形 ( $N(g^d)$ ) が与えられたとき、固定した元 (g) に対して指数 (d) を求める問題（クラス群における離散対数問題）は、既知のアルゴリズムではサブ指数時間を要し、実用的には困難と考えられている。

イデアル類群の演算定義

pが素数でも類群は一般的に巡回群にはならないため、巡回群となるようなpを先に選択しておく必要があります。体Kの種類によっては、イデアル類群の間で代表元aを使った演算が群をなすことが知られています¹⁸。虚二次体ではこの演算が群演算となります。

なお $K=\mathbb{Q}(\sqrt{-p})$ の類群が巡回になる素数 (p) を、きれいな合同条件などで特徴づける方法は不明ですが「(p) をランダムに取って計算すると、かなり高い確率で類群は巡回になる」ということは分かっています。

イデアル類群の標準形

ミンコフスキーの定理¹⁹から、そのようなイデアルが存在することは言えます。そのようなイデアルに変換する手法は講義資料²⁰に記載されています。また、標準形から二次形式への変換については講義資料²¹を参考にしてください。

暗号系におけるイデアル類群の利用

CL暗号系の説明をする前段階での、「イデアル類群暗号系」については、基本的に以下を理解していれば十分かと思います。

イデアル類群は離散対数問題が難しい有限巡回群であると考えられていること
予測不可能な群構造を持つ有限巡回群において、離散対数問題が難しい場合には、他の有限巡回群と同様に、既知の署名、鍵交換アルゴリズム、El Gamal暗号等を利用できること（ただし群固有の構造を使った攻撃に合わせて詳細は調整する必要あり）

要するに、既存の暗号アルゴリズムの下部構造である有限巡回群だけ入れ替えれば、そのまま「イデアル類群暗号系」が大まかに作成できるということです。
ただ、これだけではまだ加法準同型性を持つわけではないことに注意してください。

類数計算の困難性

CL暗号においては、加法準同型性を持たせるために、上記のイデアル類群における離散対数問題の困難性の他にもう一つ追加で暗号学的な仮定が必要になります。それが「イデアル類群における類数計算の困難性」です。与えられた類群の類数（位数）はパラメータが決まれば一般に「このくらいのサイズだろう」ということは言えますが、正確な値を知ることは難しいとされています。

類数が未知のイデアル類群における群の計算

大きな判別式を持つ虚二次体のイデアル類群については、群演算ができるにもかかわらず位数が不明であるような群になっています。これは既約剰余類群や楕円曲線上有理点群とは異なるポイントです。

群演算として $g^a$ , $g^b$ がわかっている状態で $g^{(a+b)\ \text{mod}\ x}$ を計算することになりますが、xがわからない状態で $g^{(a+b)\ \text{mod}\ x} = g^c$ が導出されます。計算者は a, b の値を知っていても cの値を知ることはできず、 $g^c$ の値だけを知ります。 c = a + b mod x だと分かっていても、位数 x が分からないため、第三者から見ると $g^c$ の離散対数 cを [0,x−1] の範囲で一意に復元することはできません。

また $(g^a)^b = (g^b)^a = g^{ab\ \text{mod}\ x}= g^d$ のような計算について $(g^a)^b$ と $(g^b)^a$ が等しいことは要素を比較することで分かっても、そのdの値の復元はできません。

離散対数問題が易しい部分群を持つが、それ自体の離散対数問題は難しいようなイデアル類群の構成

論文³ 3.1. 「A Subgroup with an Easy DL Problem」の解説です。
以下で説明する定理によって、ある群Gの部分群F で $f \in F \subset G$ という要素をm乗した $f^m$ については離散対数mが簡単に求められることが説明されます。
ここで f は Gの要素でもあるのですが、例えばG上のイデアル代表元aを用いて $f = [a^{n}]$ のように表現できたとします。すると上記の離散対数が求められるのは $[a^{nm}] \in F \subset G$ の場合だけであり、 $[a^{n+k}] \in G$ のような隣の元については離散対数を求められない、ということになります。

定理

$\Delta_K$ を $\Delta_K = 1 \ \text{mod}\ 4$ を満たす基本判別式として $\Delta_K = -pq$ の形で表す。ここでpは奇素数でありqはpと互いに素な非負整数でq > 4pを満たす。
$\Delta_p = \Delta_K p^2$ となる判別式 $\Delta_p$ を考える。この $\Delta_p$ がなす整数環 $\cal{O}_{\Delta_p}$ は $\mathbb{Q}(\sqrt{\Delta_p})$ のうち代数的整数（=整数係数多項式の根）だけを集めた整数環である。この $\cal{O}_{\Delta_p}$ 上イデアルで標準形として $t = (p^2, p) = (p^2 \mathbb{Z} + \frac{-p+\sqrt{\Delta_p}}{2} \mathbb{Z} )$ として表現できるようなイデアルtを考える。このtが属するイデアルの同値類[t] を fとする。
すなわち、fはイデアル類群 $C(\cal{O}_{\Delta_p})$ における元である。
関数 $\text{Red}$ を、イデアルを標準形に変換する関数とし、 $m \in \{1, ..., p-1\}$ に対して標準形で $\text{Red}(f^m) = (p^2, L(m)p)$ が成り立つ。
そして $L(m)$ は $L(m) = 1/m\ \text{mod}\ p$ を満たし、[-p, p]の範囲を取る奇素数になる。
またfは $C(\cal{O}_{\Delta_p})$ の位数pである部分群Fの生成元となる。

定理の証明

（大雑把な理解なので、論文の証明ほど簡潔でも正確でもない点は、大目に見てください、、、）

商群と写像の準備

写像 $\varphi_p$ は、イデアルの基礎にある整数環 ${\cal{O}}_{\Delta_p}$ をそのまま別の整数環 ${\cal{O}}_{\Delta_{K}}$ に変更する写像である。（実際にはもっと複雑だが、簡単にそのように考える）
イデアル集合の元を別のイデアル集合の元1:1に対応付ける。 $\varphi_p$ は、あるイデアルを与えるとその整数環を変更して別のイデアルを返す。

そして、 $\bar{\varphi_p}$ は、 ${\cal{O}}_{\Delta_p}$ のイデアル集合が作るイデアル類群から、 ${\cal{O}}_{\Delta_K}$ のイデアル集合が作るイデアル類群への写像であり、こちらは1:1にはならない（実際には、後で時間を掛けてp:1になることを説明する）。
$\bar{\varphi_p}$ はイデアルの代表元が与えられたとき、その整数環を変更したイデアルaを作り、さらにその変更後のイデアル集合におけるaの代表元を返す。

以下では全射 $\bar{\varphi_p}: C({\cal{O}}_{\Delta_p}) \rightarrow C({\cal{O}}_{\Delta_{K}})$ を考える。

$\bar{\varphi_p}$ のカーネルは²²²³より商群 $(({\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K})^\times / (\mathbb{Z}/p\mathbb{Z})^\times)$ と同型であることが知られている。

この商群どうしの商群という構造が分かりづらく、かつ核心的な部分なので分解して説明しておく。

分母にあたる群の剰余類

まず ${\cal{O}}_{\Delta_K}$ と $p{\cal{O}}_{\Delta_K}$ はいずれも無限個の要素を持つ整数環である。これらの整数環の要素が2次元格子上でどのように対応しているか考えてみる。 ${\cal{O}}_{\Delta_K}$ は $a + b\sqrt{\Delta_K}$ のような形を持っており、a,bはいずれも整数。一方で $p{\cal{O}}_{\Delta_K}$ は単純なp倍数の $p\mathbb{Z}$ とは違い、aとbのそれぞれについてp倍数であるような環として定義されている。すると、 ${\cal{O}}_{\Delta_K}$ における格子点は $p{\cal{O}}_{\Delta_K}$ と比べると $p^2$ 倍個の点を持っていることになる。
${\cal{O}}_{\Delta_K}$ における格子点は( $p{\cal{O}}_{\Delta_K}$ と比べて)a要素のみp倍数のものがp倍個存在し、b要素のみp倍数のものがp倍個存在するが、a要素とb要素の両方がp倍であるものは1個しか存在せず、それが $p{\cal{O}}_{\Delta_K}$ との共通の格子点である。よって、 $p^2$ 倍個の点を持っていることから ${\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K}$ の位数は $p^2$ である。

剰余類の乗法群

次に $({\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K})^\times$ という群の位数について考える。乗法群の逆元が存在しないものを $p^2$ 個の要素から抜いた数が位数になる。この位数はpと $\Delta_K$ の関係によって異なることが知られている。今回は $p | \Delta_K$ (pが $\Delta_K$ を割り切る)ケースになり、このような場合には群の位数が p(p-1)となることが知られている。要素の形は $a + b\sqrt{\Delta_K}$ となり、 $a \in (\mathbb{Z}/p \mathbb{Z})^\times$ (位数p-1), $b \in \mathbb{Z}/p \mathbb{Z}$ (位数p)である。a,bそれぞれの群の位数を掛けたものが全体の位数になっている。(※ここでa = 0のケースが除外されているが仮にa=0を許して $b\sqrt{\Delta_K}$ という要素が存在した場合、乗算の逆数をmod pで求められないということは計算してみればわかる)
また、この $({\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K})^\times$ は $(\mathbb{F}_p[X] / (X^2))^\times$ という群とも同型であり、これも位数は p(p-1)となる。

全体の商群の位数と代表元

最後に、 $(({\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K})^\times / (\mathbb{Z}/p\mathbb{Z})^\times)$ という群についても考察する。 $x, y \in ({\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K})^\times$ という要素を考える。これらx,yに対してある $\lambda \in (\mathbb{Z}/p\mathbb{Z})^\times$ が存在して $x = \lambda y$ となるとき[x] = [y] という同値類として扱うような商群が $(({\cal{O}}_{\Delta_K}/p{\cal{O}}_{\Delta_K})^\times / (\mathbb{Z}/p\mathbb{Z})^\times)$ である。この群は巡回群となり、商群の位数は p(p-1) / (p-1) = pとなる。そしてこの商群の元（代表元）は [1]と $[a + \sqrt{\Delta_K}]$ (ただし $a \in (\mathbb{Z}/p\mathbb{Z})^\times$ )の1 + (p-1) = p個になる。

商群の要素とΔpイデアル類群の対応

$g = [1 + \sqrt{\Delta_K}]$ とする。 $g^m = [(1 + \sqrt{\Delta_K})^m] = [1 + m\sqrt{\Delta_K} + \Delta_K x] = [1 + m\sqrt{\Delta_K}]$ (mod p)である。さらに $[1 + m\sqrt{\Delta_K}] = [L(m) + \sqrt{\Delta_K}]$ の標準形で表現できる(∵商群の同値類の定義より、ある $\lambda = m$ が存在しているため) 。これはm = 1...p-1に対して成り立ち、 $g^p = [1]$ となる。

ここで $\alpha_m = \frac{L(m) + \sqrt{\Delta_K}}{2} \in {\cal{O}}_{\Delta_K}$ とする。
この $\alpha_m$ は同値類 $g^m = [L(m) + \sqrt{\Delta_K}]$ の代表元として扱える(∵商群の同値類の定義より、ある $\lambda = 2$ が存在しているため)

要素 $g^m$ は写像 $\bar{\varphi_p}$ のカーネル $[\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K})]$ に対応している。ここで $\alpha_m {\cal{O}}_{\Delta_K}$ はイデアルであり、 $\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K})$ はもともとの ${\cal{O}}_{\Delta_p}$ の世界のイデアルである。その同値類である $[\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K})]$ が $C({\cal{O}}_{\Delta_p})$ の世界のイデアル類群の元になる。

²⁴から $\alpha_m {\cal{O}}_{\Delta_K} = (N(\alpha_m), -L(m)\ \text{mod}\ 2N(\alpha_m))$ という代表イデアルで表せることが知られている。ここで N(・)はノルムであり、 $N(\alpha_m) = \frac{L(m)^2 - \Delta_K}{4}$ となる。上記の $\text{mod}\ 2N(\alpha_m))$ は「余りの取り方を0 ~ M-1ではなく -M/2 ~ M/2 に取るように修正した剰余表現」である中心化ユークリッド除法(Central Euclid Division)を用いた表現になっている。

$\alpha_m {\cal{O}}_{\Delta_K}$ は ${\cal{O}}_{\Delta_K}$ の世界の話だが、 $\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K})$ はもともとの ${\cal{O}}_{\Delta_p}$ の世界のイデアルであるため、 ${\cal{O}}_{\Delta_p}$ について考える場合には、同じイデアルだが第2項がp倍になっているようなイデアルを考えなければならない。それに合わせて $\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K})$ の標準形を計算すると以下のようになる。

元の $\Delta_K$ 世界の場合: $(a, b)_{\Delta_K} = a \mathbb{Z} + \frac{-b + \sqrt{\Delta_K}}{2} \mathbb{Z}$
$\Delta_p$ 世界の場合: $(a, B)_{\Delta_p} = a \mathbb{Z} + \frac{-B + \sqrt{\Delta_p}}{2} \mathbb{Z}$ で、この後半部分の1/p倍が $\Delta_K$ 世界と一致する必要があるため $\frac{-b + \sqrt{\Delta_K}}{2} = \frac{-B + \sqrt{\Delta_p}}{2} \frac{1}{p}$ よってB = pb

したがって $\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K}) = (N(\alpha_m), -L(m)p\ \text{mod}\ 2N(\alpha_m))$ の代表元が $C({\cal{O}}_{\Delta_p})$ の世界のイデアル類群の元に対応するが、さらにこれを変換していく。

イデアル類群の代表元の表現方法を変換

$N(\alpha_m) = \frac{L(m)^2 - \Delta_K}{4}$ かつ q > 4pより $N(\alpha_m) = \frac{L(m)^2 - \Delta_K}{4} = \frac{L(m)^2 + pq}{4} \gt \frac{L(m)^2 + 4p^2}{4} \gt p^2$ となる。これが二次形式の標準形であるための条件であるから、二次形式の標準形（3項による表現）としては $(\frac{L(m)^2 - \Delta_K}{4}, -L(m)p, p^2)$ になる。これをさらに二次形式の標準形に変換すると $( p^2, L(m)p, \frac{L(m)^2 - \Delta_K}{4})$ となり、さらにこれを代表元の標準形に変換すると $( p^2, L(m)p)$ となる。

q > 4pから $|L(m)p| \lt p^2 \lt \sqrt{|\Delta_p|}/2$ であるため、これは標準形とみなせる（注意: ³のB.2参照）。

$t = (p^2, p)$ というイデアルを考える。L(m) = 1のとき $g = [1 + \sqrt{\Delta_K}], g^m = [1 + m\sqrt{\Delta_K}] = [L(m) + \sqrt{\Delta_K}]$ との対応を考えると $[t] = [\varphi^{-1}_p(\alpha_1 {\cal{O}}_{\Delta_K}) ]$ に対応していることがわかる。さらに、 $[t]^m = [\varphi^{-1}_p(\alpha_m {\cal{O}}_{\Delta_K}) ]$ であり、m = 1, ..., p-1 に対して $\text{Red}([t]^m) = (p^2, L(m)p)$ が成り立っているため、題意が示された。

イデアル類群を使った加法準同型暗号

論文³ 2.3. 「A Generic Linearly Homomorphic Encryption Scheme」の解説です。
「離散対数問題が易しい部分群」が構成できるならば、素直に計算するだけで成り立っていそう、ということはわかるかと思います。一応chatgptで論文から日本語 +texに変換させたものを再編集して貼っておきます。
この節では「DDH group with an easy DL subgroup」((G, F)) とアルゴリズム Gen, Solve が与えられている前提で、その上に ElGamal 型の LHE を載せています。

1-1. KeyGen(1^λ)

入力: 安全性パラメータ ( $1^\lambda$ )（内部的に ( $\mu$ ) も使う）
出力: 公開鍵 (pk), 秘密鍵 (sk)

群の生成

Gen を呼び出して $(B, n, p, s, g, f, G, F) \gets \text{Gen}(1^\lambda, 1^\mu)$ を得る。ここで $(G = \langle g \rangle)$ は位数 (n) の巡回群, $(F = \langle f \rangle)$ は位数 (p) の部分群, (B) は乱数範囲を決める上限。

秘密指数の生成

一様乱数 $x {\leftarrow} {0, \dots, Bp-1}$ を選ぶ。 $(h \gets g^x)$ を計算する。

鍵の定義

公開鍵 $pk \gets (B, p, g, h, f)$ , 秘密鍵 $sk \gets x$ として((pk, sk)) を返す。

1-2. Encrypt(1^λ, pk, m)

入力: 安全性パラメータ ( $1^\lambda$ ), 公開鍵 ( $pk = (B, p, g, h, f)$ ), 平文 $m \in \mathbb{Z}/p\mathbb{Z}$
出力: 暗号文 $c = (c_1, c_2)$

乱数選択

一様乱数 $r \leftarrow \{0, \dots, Bp-1\}$ を選ぶ。

暗号文成分の計算

第1成分を $c_1 \gets g^r$ として計算する。メッセージを $f^m \in F$ に埋め込み、第2成分を $c_2 \gets f^m \cdot h^r$ として計算し、暗号文 $c = (c_1, c_2)$ を返す。

1-3. Decrypt(1^λ, pk, sk, (c1, c2))

入力: 安全性パラメータ ( $1^\lambda$ ), 公開鍵 (pk), 秘密鍵 $x$ , 暗号文 $c = (c_1, c_2)$
出力: 平文 $m \in \mathbb{Z}/p\mathbb{Z}$

ElGamal 部分の除去

$M \gets c_2 / c_1^x$ を計算する。これは理想的には $\dfrac{f^m h^r}{(g^r)^x} = \dfrac{f^m g^{xr}}{g^{xr}} = f^m \in F$ となる群要素である。

簡単 DL による復号/出力

Solve を呼び出して $m \gets \text{Solve}(p, g, f, G, F, M)$ を計算し、（これは「 $M = f^m$ から $m$ を求める」アルゴリズム） $m$ を返す。

1-4. EvalSum(1^λ, pk, (c1, c2), (c1', c2'))

2つの暗号文の「平文の和」を反映した暗号文を作るアルゴリズム。

入力: 公開鍵 (pk), 暗号文 $c = (c_1, c_2)$ （m の暗号）, 暗号文 $c' = (c'_1, c'_2)$ （m' の暗号）
出力: $m + m' \pmod p$ を暗号化した新しい暗号文

暗号文の積

第1成分: $c''_1 \gets c_1 \cdot c'_1$ , 第2成分: $c''_2 \gets c_2 \cdot c'_2$
このとき、暗号化に使った乱数を $r, r'$ とすると $c''_1 = g^{r+r'},\quad c''_2 = f^{m+m'} h^{r+r'}$ という形になる。

再ランダム化

追加の乱数 $r \leftarrow \{0, \dots, Bp-1\}$ を選び、新しい暗号文として $\bigl(c''_1 g^r,\; c''_2 h^r\bigr)$ を出力する。これは分布的に「平文 $m+m'$ を通常の Encrypt で暗号化したもの」と同じになる。

1-5. EvalScal(1^λ, pk, (c1, c2), α)

1つの暗号文に対して、平文のスカラー倍 $\alpha m$ を反映させるアルゴリズム。
入力: 公開鍵 (pk), 暗号文 $c = (c_1, c_2)$ （m の暗号）, スカラー $\alpha \in \mathbb{Z}/p\mathbb{Z}$
出力: $\alpha m$ の暗号文

スカラー倍

第1成分: $c'_1 \gets c_1^\alpha = g^{\alpha r}$ , 第2成分: $c'_2 \gets c_2^\alpha = f^{\alpha m} h^{\alpha r}$

再ランダム化

乱数 $r \leftarrow \{0, \dots, Bp-1\}$ を選び、暗号文 $\bigl(c'_1 g^r,\; c'_2 h^r\bigr)$ を出力する。これも Encrypt(pk, $\alpha m$ ) と同じ分布になる。

2-1. Gen(1^λ, 1^μ)

イデアル類群実装用の具体的な Genの実装。

入力: 安全性パラメータ ( $\lambda$ ), メッセージ長（位数 $p$ のビット長）( $\mu$ )
出力: DDH group with easy DL subgroup のパラメータ $(B, n, p, s, g, f, G, F)$ （このインスタンスでは $n, s$ は使わないので $\varnothing$ ）

パラメータ条件

$\lambda > \mu + 2$ を満たすように仮定する（安全性と多項式時間アルゴリズムの実現のため）。

素数 p, q の生成

$\mu$ ビット長の素数 $p$ をランダムに選ぶ。 $2\lambda - \mu$ ビット長の素数 $q$ をランダムに選ぶ。次を満たすように選ぶ: $pq \equiv -1 \pmod{4},\quad \left(\frac{p}{q}\right) = -1$ （ $\left(\frac{p}{q}\right)$ はルジャンドル記号）。

判別式の設定

基本判別式 $\Delta_K \gets -pq$ , 非極大オーダーの判別式 $\Delta_p \gets p^2 \Delta_K$

離散対数問題が簡単な部分群 F の構成

クラス群 $C(\Delta_p)$ の元 $f \gets [(p^2, p)]$ を取り、 $F = \langle f \rangle$ とする。これは位数 $p$ の部分群になる（3.1節の結果）。

最大オーダー側の素数 r

$p$ と異なる「小さな素数」 $r$ を選び、 $\left(\frac{\Delta_K}{r}\right) = 1$ を満たすようにする（ $\Delta_K$ が mod $r$ で二次剰余）。この $r$ の上にある $\mathcal{O}_{\Delta_K}$ の素イデアル $\mathfrak{r}$ を 1 つ取る（“ideal lying above $r$ ”）。

生成元 g と群 G の構成

$\mathfrak{r}^2$ を $\Delta_p$ 側へ引き戻して $[\varphi_p^{-1}(\mathfrak{r}^2)] \in C(\Delta_p)$ を得る。一様乱数 $k \leftarrow \{1,\dots, p-1\}$ を選び、 $g \gets [\varphi_p^{-1}(\mathfrak{r}^2)]^p \cdot f^k \in C(\Delta_p)$ と定義する。 $G = \langle g \rangle$ を $g$ が生成する巡回群とする（この構成で $|G| = ps$ となるように設計されている）。

乱数範囲 B の設定

$B \gets \left\lceil |\Delta_K|^{3/4} \right\rceil$ とする。これにより $\{g^r : r \in [0, Bp-1]\}$ の分布が $G$ の一様分布に統計的に近くなる（Appendix C の評価）。

出力

本来の型は $(B, n, p, s, g, f, G, F)$ だが、このインスタンスでは $n, s$ を使わないため $(B, \varnothing, p, \varnothing, g, f, G, F)$ を返す。

2-2. Solve(B, p, g, f, G, F, X)

DDH 群上で、離散対数問題が簡単な部分群 $F$ に属する元 $X = f^m$ から $m$ を求めるアルゴリズム。

入力: パラメータ $(B, p, g, f, G, F)$ , 対象要素 $X \in F \subset G$
出力: $m \in \mathbb{Z}/p\mathbb{Z}$ または失敗記号 $\bot$

標準形への正規化

クラス群 $C(\Delta_p)$ 上の正規化アルゴリズム（既約化）を用いて、 $X$ の既約な代表イデアルを求める。うまくいけば、その標準形は $\text{Red}(X) = (p^2,\; \tilde{x} p)$ のように書ける（3.1節の構成から、 $F$ の元は必ずこの形になる）。

パターンチェック

もし標準形がこのパターン $(p^2, \tilde{x} p)$ にならなければ、（ $F$ の外の要素だったなどの理由で） $\bot$ を返す。

係数から離散対数を復元

$\tilde{x}$ を $\bmod\ p$ で逆元計算し、 $m \gets \tilde{x}^{-1} \pmod p$ を得る（命題1より $\tilde{x} \equiv L(m) \equiv m^{-1} \pmod p$ なので、 $\tilde{x}^{-1} \equiv m \pmod p$ が成り立つ）。その後 $m$ を返す。