XTR

pをp  ≡ 2 mod 3かつp ² - p + 1が十分に大きな素因数qを持つ素数とする。p 2 ≡ 1 mod 3 であることから、pはを生成することがわかる^。   ${\displaystyle (\mathbb {Z} /3\mathbb {Z} )^{*}}$したがって、第3円分多項式${\displaystyle \Phi _{3}(x)=x^{2}+x+1}$は還元不可能で ある${\displaystyle GF(p)}$。したがって、根は${\displaystyle \alpha }$そして$\displaystyle \alpha ^{p}}$最適な正規基底を形成する${\displaystyle GF(p^{2})}$以上${\displaystyle GF(p)}$そして

${\displaystyle GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\}.}$

p ≡ 2 mod 3であることを考慮すると、指数を3で割った余りを約分して、

${\displaystyle GF(p^{2})\cong \{y_{1}\alpha +y_{2}\alpha ^{2}:\alpha ^{2}+\alpha +1=0,y_{1},y_{2}\in GF(p)\}。$

算術演算のコストは、「XTR公開鍵システムの概要」の補題2.21として次の補題で与えられています。^{[ 1 ]}

補題

• x ^pの計算は乗算を使用せずに行われます
• x ²を計算するには、2 つの乗算が必要です。${\displaystyle GF(p)}$
• xyを計算するには3回の乗算が必要です${\displaystyle GF(p)}$
• xz-yz ^pを計算するには4 つの乗算が必要です${\displaystyle GF(p)}$。

XTR のトレースは常に次の点に留意する必要があります${\displaystyle GF(p^{2})}$言い換えれば、共役は${\displaystyle h\in GF(p^{6})}$以上${\displaystyle GF(p^{2})}$は${\displaystyle h,h^{p^{2}}}$そして${\displaystyle h^{p^{4}}}$そして痕跡${\displaystyle h}$それらの合計は次のとおりです。

${\displaystyle Tr(h)=h+h^{p^{2}}+h^{p^{4}}.}$

ご了承ください$\displaystyle Tr(h)\in GF(p^{2})$以来

${\displaystyle {\begin{aligned}Tr(h)^{p^{2}}&=h^{p^{2}}+h^{p^{4}}+h^{p^{6}}\\&=h+h^{p^{2}}+h^{p^{4}}\\&=Tr(h)\end{aligned}}}$

次に、発電機について考えてみましょう。${\displaystyle g}$素数の位数の XTR 部分群の${\displaystyle q}$覚えておいてください${\displaystyle \langle g\rangle }$位数が の XTR スーパーグループの部分群である。${\displaystyle p^{2}-p+1}$、 それで${\displaystyle q\mid p^{2}-p+1}$次のセクションでは、選択方法を見ていきます。${\displaystyle p}$そして${\displaystyle q}$しかし今のところは、${\displaystyle q>3}$トレースを計算するには${\displaystyle g}$モジュロに注意${\displaystyle p^{2}-p+1}$我々は持っています

${\displaystyle p^{2}=p-1}$そして

${\displaystyle p^{4}=(p-1)^{2}=p^{2}-2p+1=-p}$

そしてこうして

${\displaystyle {\begin{aligned}Tr(g)&=g+g^{p^{2}}+g^{p^{4}}\\&=g+g^{p-1}+g^{-p}.\end{aligned}}}$

共役体の生成物${\displaystyle g}$等しい${\displaystyle 1}$つまり、${\displaystyle g}$ノルムは1です。

XTR の重要な観察は、最小多項式が${\displaystyle g}$以上${\displaystyle GF(p^{2})}$

${\displaystyle (xg)\!\ (xg^{p-1})(xg^{-p})}$

簡略化すると

${\displaystyle x^{3}-Tr(g)\!\ x^{2}+Tr(g)^{p}x-1}$

これは完全に決定されます${\displaystyle Tr(g)}$結果として、共役体は${\displaystyle g}$最小多項式の根として${\displaystyle g}$以上${\displaystyle GF(p^{2})}$は、完全にトレースによって決定されます${\displaystyle g}$。これは、任意のべき乗についても同様です。${\displaystyle g}$:共役${\displaystyle g^{n}}$多項式の根である

${\displaystyle x^{3}-Tr(g^{n})\!\ x^{2}+Tr(g^{n})^{p}x-1}$

そしてこの多項式は完全に決定されます${\displaystyle Tr(g^{n})}$。

トレースを使用する背後にある考え方は、${\displaystyle g^{n}\in GF(p^{6})}$暗号プロトコル、例えばディフィー・ヘルマン鍵交換では$\displaystyle Tr(g^{n})\in GF(p^{2})$これにより、表現サイズを3分の1に削減できます。ただし、これは、迅速に取得する方法がある場合にのみ役立ちます。${\displaystyle Tr(g^{n})}$与えられた${\displaystyle Tr(g)}$次の段落では、効率的な計算のためのアルゴリズムを示します。${\displaystyle Tr(g^{n})}$さらに、コンピューティング${\displaystyle Tr(g^{n})}$与えられた${\displaystyle Tr(g)}$計算よりも速いことが判明${\displaystyle g^{n}}$与えられた${\displaystyle g}$[ ^{1 ]​}

A. LenstraとE. Verheulは、彼らの論文「The XTR public key system in ^{[ 2 ]} 」の中でこのアルゴリズムを提示しています。ここで提示するアルゴリズムに必要なすべての定義と補題、およびアルゴリズム自体は、その論文から引用されています。

定義c について${\displaystyle GF(p^{2})}$定義する

${\displaystyle F(c,X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X].}$

定義​${\displaystyle h_{0},\!\ h_{1},h_{2}}$は、必ずしも異なるとは限らない、の根を表す。${\displaystyle F(c,X)}$で${\displaystyle GF(p^{6})}$そして${\displaystyle n}$いる${\displaystyle \mathbb {Z} }$。 定義する

${\displaystyle c_{n}=h_{0}^{n}+h_{1}^{n}+h_{2}^{n}.}$

特性${\displaystyle c_{n}}$そして${\displaystyle F(c,X)}$

1. ${\displaystyle c=c_{1}}$
2. ${\displaystyle c_{-n}=c_{np}=c_{n}^{p}}$
3. ${\displaystyle c_{n}\in GF(p^{2}){\text{ for }}n\in \mathbb {Z} }$
4. ${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{uv}+c_{u-2v}{\text{ for }}u,v\in \mathbb {Z} }$
5. すべて${\displaystyle h_{j}}$分割する順序を持つ${\displaystyle p^{2}-p+1}$そして${\displaystyle >3}$またはすべて${\displaystyle h_{j}}$は${\displaystyle GF(p^{2})}$。 特に、${\displaystyle F(c,X)}$根が位数ダイバーを持つ場合に限り、既約である。${\displaystyle p^{2}-p+1}$そして${\displaystyle >3}$。
6. ${\displaystyle F(c,X)}$は還元可能である${\displaystyle GF(p^{2})}$かつその場合に限り${\displaystyle c_{p+1}\in GF(p)}$

補題 レット${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1}}$与えられる。

1. コンピューティング${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p}}$2 倍して${\displaystyle GF(p)}$。
2. コンピューティング${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$4 倍数で${\displaystyle GF(p)}$。
3. コンピューティング${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}}$4 倍数で${\displaystyle GF(p)}$。
4. コンピューティング${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}}$4 倍数で${\displaystyle GF(p)}$。

定義​${\displaystyle S_{n}(c)=(c_{n-1},c_{n},c_{n+1})\in GF(p^{2})^{3}}$。

アルゴリズム1による計算${\displaystyle S_{n}(c)}$与えられた${\displaystyle n}$そして${\displaystyle c}$

• もし${\displaystyle n<0}$このアルゴリズムを適用する${\displaystyle -n}$そして${\displaystyle c}$そして、結果の値に特性2を適用します。
• もし${\displaystyle n=0}$、 それから${\displaystyle S_{0}(c)\!\ =(c^{p},3,c)}$。
• もし${\displaystyle n=1}$、 それから${\displaystyle S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})}$。
• もし${\displaystyle n=2}$計算を使用する${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$そして${\displaystyle S_{1}(c)}$見つける${\displaystyle c_{3}}$それによって${\displaystyle S_{2}(c)}$。
• もし${\displaystyle n>2}$計算するために${\displaystyle S_{n}(c)}$定義する

${\displaystyle {\bar {S}}_{i}(c)=S_{2i+1}(c)}$

そして${\displaystyle {\bar {m}}=n}$nが奇数で${\displaystyle {\bar {m}}=n-1}$そうでなければ。${\displaystyle {\bar {m}}=2m+1,k=1}$計算${\displaystyle {\bar {S}}_{k}(c)=S_{3}(c)}$上記の補題を用いて${\displaystyle S_{2}(c)}$さらに

${\displaystyle m=\sum _{j=0}^{r}m_{j}2^{j}}$

と${\displaystyle m_{j}\in {0,1}}$そして${\displaystyle m_{r}=1}$。 のために${\displaystyle j=r-1,r-2,...,0}$次の手順を順番に実行してください。

• もし${\displaystyle m_{j}=0}$、 使用${\displaystyle {\bar {S}}_{k}(c)}$計算する${\displaystyle {\bar {S}}_{2k}(c)}$。
• もし${\displaystyle m_{j}=1}$、 使用${\displaystyle {\bar {S}}_{k}(c)}$計算する${\displaystyle {\bar {S}}_{2k+1}(c)}$。
• 交換する${\displaystyle k}$による${\displaystyle 2k+m_{j}}$。

これらの反復処理が終了すると、${\displaystyle k=m}$そして${\displaystyle S_{\bar {m}}(c)={\bar {S}}_{m}(c)}$nが偶数の場合は、${\displaystyle S_{\bar {m}}(c)}$計算する${\displaystyle {\bar {S}}_{m+1}(c)}$。

要素のトレースの上記の表現を活用し、さらに十分なセキュリティを確保するためには、以下で説明するように、素数を見つける必要があります。${\displaystyle p}$そして${\displaystyle q}$、 どこ${\displaystyle p}$場の特性を表す${\displaystyle GF(p^{6})}$と${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$そして${\displaystyle q}$は部分群のサイズであり、${\displaystyle q}$分ける${\displaystyle p^{2}-p+1}$。

と表記する${\displaystyle P}$そして${\displaystyle Q}$サイズ${\displaystyle p}$そして${\displaystyle q}$ビット単位で。1024ビットRSAと同等のセキュリティを実現するには、${\displaystyle 6P}$約1024、つまり${\displaystyle P\approx 170}$そして${\displaystyle Q}$約160になる可能性がある。

このような素数を計算する最初の簡単なアルゴリズム${\displaystyle p}$そして${\displaystyle q}$次のアルゴリズムAは次のとおりです。

アルゴリズムA

1. 探す${\displaystyle r\in \mathbb {Z} }$そのため${\displaystyle q=r^{2}-r+1}$は${\displaystyle Q}$-ビット素数。
2. 探す${\displaystyle k\in \mathbb {Z} }$そのため${\displaystyle p=r+k\cdot q}$は${\displaystyle P}$-ビット素数${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$。

アルゴリズムAの正当性：

確認すべきことは${\displaystyle q\mid p^{2}-p+1}$他の必要な特性はすべて定義により明らかに満たされているため${\displaystyle p}$そして${\displaystyle q}$我々は容易に次のことがわかる${\displaystyle p^{2}-p+1=r^{2}+2rkq+k^{2}q^{2}-r-kq+1=r^{2}-r+1+q(2rk+k^{2}q-k)=q(1+2rk+k^{2}q-k)}$これはつまり${\displaystyle q\mid p^{2}-p+1}$。

アルゴリズムAは非常に高速で、素数を見つけるのに使用できます。${\displaystyle p}$係数が小さい2次多項式を満たすもの。${\displaystyle p}$高速な算術演算につながる${\displaystyle GF(p)}$特に検索が${\displaystyle k}$制限されている${\displaystyle k=1}$つまり、${\displaystyle r}$両方とも${\displaystyle r^{2}-r+1{\text{ and }}r^{2}+1}$素数であり、${\displaystyle r^{2}+1\equiv 2{\text{ mod }}3}$素数${\displaystyle p}$この素敵なフォームを持っています。この場合、${\displaystyle r}$均等でなければならない${\displaystyle r\equiv 1{\text{ mod }}4}$。

一方、そのような${\displaystyle p}$セキュリティの観点からは望ましくないかもしれない。なぜなら、数値体篩の離散対数変種を用いた攻撃を容易にする可能性があるからである。

以下のアルゴリズムBにはこの欠点はありませんが、高速な剰余演算もありません。${\displaystyle p}$その場合、アルゴリズムAは次のようになります。

アルゴリズムB

1. 選択してください${\displaystyle Q}$-ビットプライム${\displaystyle q}$となることによって${\displaystyle q\equiv 7\ {\text{mod}}\ 12}$。
2. ルーツを探る${\displaystyle r_{1}}$そして${\displaystyle r_{2}}$の${\displaystyle X^{2}-X+1\ {\text{mod}}\ q}$。
3. 見つける ${\displaystyle k\in \mathbb {Z} }$そのため${\displaystyle p=r_{i}+k\cdot q}$は${\displaystyle P}$-ビット素数${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$のために${\displaystyle i\in \{1,2\}}$

アルゴリズムBの正当性：

私たちが選んだので ${\displaystyle q\equiv 7\ {\text{mod}}\ 12}$直ちに次のことが導かれる ${\displaystyle q\equiv 1\ {\text{mod}}\ 3}$（なぜなら ${\displaystyle 7\equiv 1\ {\text{mod}}\ 3}$そして ${\displaystyle 3\mid 12}$) と二次相互法則から、次のことが推測できます 。${\displaystyle r_{1}}$そして${\displaystyle r_{2}}$存在する。

それを確認するために${\displaystyle q\mid p^{2}-p+1}$もう一度検討します${\displaystyle p^{2}-p+1}$のために${\displaystyle r_{i}\in \{1,2\}}$そしてそれを手に入れる${\displaystyle p^{2}-p+1=r_{i}^{2}+2r_{i}kq+k^{2}q^{2}-r_{i}-kq+1=r_{i}^{2}-r_{i}+1+q(2rk+k^{2}q-k)=q(2rk+k^{2}q-k)}$、 以来${\displaystyle r_{1}}$そして${\displaystyle r_{2}}$は根です${\displaystyle X^{2}-X+1}$そしてそれゆえに${\displaystyle q\mid p^{2}-p+1}$。

最後の段落ではサイズを選択しました${\displaystyle p}$そして${\displaystyle q}$有限体の${\displaystyle GF(p^{6})}$そして乗法部分群${\displaystyle GF(p^{6})^{*}}$さあ、今度は部分群を見つけよう${\displaystyle \langle g\rangle }$の${\displaystyle GF\!\ (p^{6})^{*}}$一部の人にとって${\displaystyle g\in GF(p^{6})}$そのため${\displaystyle \mid \!\!\langle g\rangle \!\!\mid =q}$。

しかし、明示的な${\displaystyle g\in GF(p^{6})}$要素を見つけるだけで十分です${\displaystyle c\in GF(p^{2})}$そのため${\displaystyle c=Tr(g)}$要素の場合${\displaystyle g\in GF(p^{6})}$順序${\displaystyle q}$しかし、${\displaystyle Tr(g)}$発電機${\displaystyle g}$XTR（サブ）グループのルートは、${\displaystyle F(Tr(g),\ X)}$これは上記で定義されています。そのような${\displaystyle c}$5番目の物件を見てみましょう${\displaystyle F(c,\ X)}$ここで、${\displaystyle F(c,\ X)}$分割する順序を持つ${\displaystyle p^{2}-p+1}$かつその場合に限り${\displaystyle F(c,\ X)}$既約である。そのようなものを見つけた後${\displaystyle c}$それが本当に秩序にかなっているかどうかを確認する必要がある${\displaystyle q}$しかし、まずは選択方法に焦点を当てます${\displaystyle c\in GF(p^{2})}$そのため${\displaystyle F(c,\ X)}$還元不可能である。

最初のアプローチは、${\displaystyle c\in GF(p^{2})\backslash GF(p)}$これはランダムであり、次の補題によって正当化される。

補題:ランダムに選択された${\displaystyle c\in GF(p^{2})}$確率${\displaystyle F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]}$還元不可能な値は約3分の1です。

適切なものを見つけるための基本的なアルゴリズム${\displaystyle Tr(g)}$内容は以下のとおりです。

アルゴリズムの概要

1. ランダムに選択${\displaystyle c\in GF(p^{2})\backslash GF(p)}$。
2. もし${\displaystyle F(c,\ X)}$還元可能であれば、ステップ1に戻ります。
3. アルゴリズム1を使用して計算します${\displaystyle d=c_{(p^{2}-p+1)/q}}$。
4. もし${\displaystyle d}$秩序がない${\displaystyle q}$ステップ1に戻ります。
5. させて${\displaystyle Tr(g)=d}$。

このアルゴリズムは実際に要素を計算することが判明しました${\displaystyle GF(p^{2})}$それは等しい${\displaystyle Tr(g)}$一部の人にとって${\displaystyle g\in GF(p^{6})}$順序${\displaystyle q}$。

アルゴリズムの詳細、その正当性、実行時間、および補題の証明については、^{[ 1 ]}の「XTR公開鍵システムの概要」を参照してください。

アリスとボブの両方がXTR公開鍵データにアクセスできると仮定します。${\displaystyle \left(p,q,Tr(g)\right)}$そして、共通の秘密鍵に合意するつもりである${\displaystyle K}$これは、Diffie–Hellman鍵交換の次のXTRバージョンを使用することで実現できます。

1. アリスは${\displaystyle a\in \mathbb {Z} }$ランダムに${\displaystyle 1<a<q-2}$アルゴリズム1を用いて計算する${\displaystyle S_{a}(Tr(g))=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right)\in GF(p^{2})^{3}}$そして送信する${\displaystyle Tr(g^{a})\in GF(p^{2})}$ボブへ。
2. ボブは受け取る${\displaystyle Tr(g^{a})}$アリスからランダムに選択${\displaystyle b\in \mathbb {Z} }$と${\displaystyle 1<b<q-2}$アルゴリズム1を適用して計算します${\displaystyle S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$そして送信する ${\displaystyle Tr(g^{b})\in GF(p^{2})}$アリスへ。
3. アリスは${\displaystyle Tr(g^{b})}$ボブから、アルゴリズム1で計算します。${\displaystyle S_{a}(Tr(g^{b}))=\left(Tr(g^{(a-1)b}),Tr(g^{ab}),Tr(g^{(a+1)b})\right)\in GF(p^{2})^{3}}$そして決定する${\displaystyle K}$に基づく${\displaystyle Tr(g^{ab})\in GF(p^{2})}$。
4. ボブは同様にアルゴリズム1を適用して計算する${\displaystyle S_{b}(Tr(g^{a}))=\left(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a(b+1)})\right)\in GF(p^{2})^{3}}$また決定する${\displaystyle K}$に基づく${\displaystyle Tr(g^{ab})\in GF(p^{2})}$。

ElGamal暗号化の場合、アリスがXTR公開鍵データの所有者であると仮定します。${\displaystyle (p,q,Tr(g))}$そして彼女が秘密の整数を選んだ${\displaystyle k}$計算された${\displaystyle Tr(g^{k})}$そして結果を公表した。アリスのXTR公開鍵データ${\displaystyle \left(p,q,Tr(g),Tr(g^{k})\right)}$ボブはメッセージを暗号化できます${\displaystyle M}$アリス向けに、以下のElGamal暗号化のXTRバージョンを使用して作成されます。

1. ボブはランダムに${\displaystyle b\in \mathbb {Z} }$と${\displaystyle 1<b<q-2}$アルゴリズム1を用いて計算する${\displaystyle S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$。
2. ボブは次にアルゴリズム1を適用して計算します${\displaystyle S_{b}(Tr(g^{k}))=\left(Tr(g^{(b-1)k}),Tr(g^{bk}),Tr(g^{(b+1)k})\right)\in GF(p^{2})^{3}}$。
3. ボブは対称暗号鍵を決定する${\displaystyle K}$に基づく${\displaystyle Tr(g^{bk})\in GF(p^{2})}$。
4. ボブは合意された鍵を用いた対称暗号化方式を使用する${\displaystyle K}$メッセージを暗号化する${\displaystyle M}$暗号化の結果${\displaystyle E}$。
5. ボブが送る${\displaystyle (Tr(g^{b}),\ E)}$アリスへ。

受領時に${\displaystyle (Tr(g^{b}),\ E)}$アリスは次のようにメッセージを復号します。

1. アリスは計算する${\displaystyle S_{k}(Tr(g^{b}))=\left(Tr(g^{b(k-1)}),Tr(g^{bk}),Tr(g^{b(k+1)})\right)\in GF(p^{2})^{3}}$。
2. アリスは対称鍵を決定する${\displaystyle K}$に基づく${\displaystyle Tr(g^{bk})\in GF(p^{2})}$。
3. アリスは合意された鍵を用いた対称暗号化方式を使用する${\displaystyle K}$復号化する${\displaystyle E}$結果として元のメッセージが表示される${\displaystyle M}$。

ここで説明する暗号化方式は、エルガマル暗号化の一般的なハイブリッドバージョンに基づいており、秘密鍵は${\displaystyle K}$非対称公開鍵システムによって取得され、その後、アリスとボブが合意した対称鍵暗号化方式でメッセージが暗号化されます。

より伝統的なエルガマル暗号化では、メッセージは鍵空間に制限されます。ここでは、${\displaystyle GF(p^{2})}$、 なぜなら${\displaystyle Tr(g)\in GF(p^{2})\ \forall p\in GF(p^{6})^{*}}$この場合の暗号化は、メッセージと鍵の乗算であり、これは鍵空間において可逆な演算である。${\displaystyle GF(p^{2})}$。

具体的に言うと、ボブがメッセージを暗号化したい場合${\displaystyle M\!\ '}$まず、それを要素に変換する必要があります${\displaystyle M}$の${\displaystyle GF(p^{2})}$そして暗号化されたメッセージを計算します${\displaystyle E}$として${\displaystyle E=K\cdot M\in GF(p^{2})}$暗号化されたメッセージを受信したら${\displaystyle E}$アリスは元のメッセージを復元できる${\displaystyle M}$計算によって${\displaystyle M=E\cdot K^{-1}}$、 どこ${\displaystyle K^{-1}}$は逆です${\displaystyle K}$で${\displaystyle GF(p^{2})}$。

さあ${\displaystyle \langle \gamma \rangle }$位数が の乗法群である${\displaystyle \omega }$Diffie–Hellmanプロトコルのセキュリティは${\displaystyle \langle \gamma \rangle }$計算のディフィー・ヘルマン（DH）問題に依存している${\displaystyle \gamma ^{xy}{\text{ given }}\gamma ,\gamma ^{x}{\text{ and }}\gamma ^{y}}$私たちは書く${\displaystyle DH(\gamma ^{x},\ \gamma ^{y})=\gamma ^{xy}}$DH問題に関連する他の2つの問題があります。1つ目は、Diffie–Hellman決定（DHD）問題で、${\displaystyle c=DH(a,b)}$与えられた${\displaystyle a,b,c\in \langle \gamma \rangle }$そして2つ目は離散対数（DL）問題で、${\displaystyle x=DL(a)}$特定の${\displaystyle a=\gamma ^{x}\in \langle \gamma \rangle {\text{ with }}0\leq x<\omega }$。

DL問題は少なくともDH問題と同じくらい難しく、一般的にDL問題が${\displaystyle \langle \gamma \rangle }$が解決不可能であれば、他の２つも同様に解決不可能である。

素因数分解を考慮すると${\displaystyle \omega }$DLの問題${\displaystyle \langle \gamma \rangle }$すべてのサブグループにおいてDL問題に還元できる${\displaystyle \langle \gamma \rangle }$ポーリグ・ヘルマンアルゴリズムにより素数位数となる。したがって${\displaystyle \omega }$素数であると安全に仮定できる。

サブグループの場合${\displaystyle \langle \gamma \rangle }$素数の${\displaystyle \omega }$乗法群の${\displaystyle GF\left(p^{t}\right)^{*}}$拡張フィールドの${\displaystyle GF(p^{t})}$の${\displaystyle GF(p)}$一部の人にとって${\displaystyle t}$現在、このシステムを攻撃する方法は2つあります。乗法群全体に焦点を当てるか、部分群に焦点を当てるかのどちらかです。乗法群を攻撃する場合、最もよく知られている方法は、数体篩の離散対数変種です。あるいは、部分群では、いくつかの方法のいずれかを使用できます。${\displaystyle {\mathcal {O}}({\sqrt {\omega }})}$の業務${\displaystyle \langle \gamma \rangle }$例えば、ポラードのロー法など。

どちらのアプローチでも、DL問題の難しさは${\displaystyle \langle \gamma \rangle }$最小周辺部分体のサイズに依存します${\displaystyle \langle \gamma \rangle }$そしてその素数の大きさについて${\displaystyle \omega }$。 もし${\displaystyle GF\left(p^{t}\right)}$それ自体は、${\displaystyle \langle \gamma \rangle }$そして${\displaystyle \omega }$が十分に大きい場合、DL の問題は${\displaystyle \langle \gamma \rangle }$は、一般的なDL問題と同じくらい難しい。${\displaystyle GF\left(p^{t}\right)}$。

XTRパラメータは、次のように選択されます。${\displaystyle p}$小さくはない、${\displaystyle q}$十分に大きく、${\displaystyle \langle g\rangle }$真のサブフィールドに埋め込むことはできません${\displaystyle GF(p^{6})}$、 以来${\displaystyle q\mid p^{2}-p+1}$そして${\displaystyle p^{2}-p+1}$はの約数です${\displaystyle \mid \!GF(p^{6})^{*}\!\mid =p^{6}-1}$しかし、分割はしない${\displaystyle p^{s}-1{\text{ for }}s\in \{1,2,3\}}$そしてこうして${\displaystyle \langle g\rangle }$サブグループにはなれません${\displaystyle GF\!\ (p^{s})^{*}}$のために${\displaystyle s\in \{1,2,3\}}$したがって、XTR グループの DL 問題は、DL 問題と同じくらい難しいと想定できます。${\displaystyle GF(p^{6})}$。

離散対数に基づく暗号プロトコルでは、楕円曲線の点群や有限体の乗法群の部分群（XTR群など）といった、さまざまな種類の部分群を使用できます。上で述べたように、Diffie-HellmanおよびElGamal暗号プロトコルのXTRバージョンでは、XTR群の要素を使用する代わりに、そのトレースを使用します。これは、これらの暗号方式のXTRバージョンのセキュリティが、元のDH、DHD、またはDL問題に基づかなくなったことを意味します。したがって、これらの問題のXTRバージョンを定義する必要があり、次の定義の意味で、それらは元の問題と等価であることがわかります。

定義:

• XTR-DH問題を、計算問題として定義する。${\displaystyle Tr(g^{xy})}$与えられた${\displaystyle Tr(g^{x})}$そして${\displaystyle Tr(g^{y})}$そして私たちは書く${\displaystyle XDH(g^{x},\ g^{y})=g^{xy}}$。
• XTR -DHD の問題は、${\displaystyle XDH(a,b)=c}$のために${\displaystyle a,b,c\in Tr(\langle g\rangle )}$。
• 与えられた${\displaystyle a\in Tr(\langle g\rangle )}$XTR-DL問題は、${\displaystyle x=XDL(a)}$つまり${\displaystyle 0\leq x<q}$そのため${\displaystyle a=Tr(g^{x})}$。
• 私たちはその問題を言う${\displaystyle {\mathcal {A}}}$問題(a,b)と同等である${\displaystyle {\mathcal {B}}}$問題が発生した場合${\displaystyle {\mathcal {A}}}$（または${\displaystyle {\mathcal {B}}}$）は、問題を解くアルゴリズムを最大で a（または b）回呼び出すことで解決できます。${\displaystyle {\mathcal {B}}}$（または${\displaystyle {\mathcal {A}}}$)

これらの問題のXTR版を紹介した後、次の定理は、XTR問題と非XTR問題（実際には同等）との関連性を示す重要な結果です。これは、上記のように、要素とそのトレースのXTR表現は、セキュリティを損なうことなく、通常の表現よりも3倍高速であることを意味します。

定理 以下の同値関係が成り立つ。

i. XTR-DL問題は、 DL問題と(1,1)-等価である。${\displaystyle \langle g\rangle }$。

ii. XTR-DH問題は、 DH問題と(1,2)等価である。${\displaystyle \langle g\rangle }$。

iii. XTR-DHD問題は、 DHD問題と(3,2)等価である。${\displaystyle \langle g\rangle }$。

これは、XTR-DL、XTR-DH、またはXTR-DHDを非無視できる確率で解くアルゴリズムを、対応する非XTR問題DL、DH、またはDHDを非無視できる確率で解くアルゴリズムに変換できることを意味し、その逆も同様です。特に、パートii.は、小さなXTR-DHキー（要素）を決定することを意味します。${\displaystyle GF(p^{2})}$) は、DH キー全体 (の要素) を決定するのと同じくらい難しいです。${\displaystyle GF(p^{6})}$代表グループにおいて${\displaystyle \langle g\rangle }$。