トレースゼロ暗号

1998年にゲルハルト・フライによって初めて提唱されたトレースゼロ暗号は、暗号目的にトレースゼロ多様体（TZV）を用いることを指します。トレースゼロ多様体は、有限体上に定義された低種数超楕円曲線上の因子類群の部分群です。これらの群は、離散対数問題を暗号プリミティブとして用いる非対称暗号を確立するために用いられます。

トレースゼロ多様体は、楕円曲線よりも優れたスカラー乗算性能を備えています。これにより、これらの群では高速演算が可能になり、楕円曲線と比較して計算速度が3倍になり、暗号システムの速度が向上します。

もう一つの利点は、暗号的に重要なサイズの群の場合、群の位数はフロベニウス準同型の特性多項式を用いて簡単に計算できることです。これは、例えば楕円曲線暗号において素体上の楕円曲線の点群を暗号目的に用いる場合には 当てはまりません。

しかし、トレースゼロ多様体の元を表現するには、楕円曲線や超楕円曲線の元に比べて多くのビット数が必要です。また、カバー攻撃によってTZVのセキュリティがビット長の1/6まで低下する可能性があることも欠点です。

数学的背景

奇標数の素体上の種数gの超楕円曲線 Cは、 q = p n ( pは素数)で、次のように定義されます Fq{\displaystyle \mathbb {F}_{q}}

C： y2＋h（x）y＝f（x）,{\displaystyle C:~y^{2}+h(x)y=f(x),}

ここで、 fはモニック、deg( f ) = 2 g  + 1、deg( h ) ≤ gである。曲線には少なくとも1つの有理ワイエルシュトラス点が存在する。 Fq{\displaystyle \mathbb {F}_{q}}

Cのヤコビ多様体 は、すべての有限拡大に対してイデアル類群 と同型である。マンフォード表現を用いると、 の元を 一対の多項式[u, v]（ただしu , v ∈ ）で表すことができる 。 JC（Fqn）{\displaystyle J_{C}(\mathbb{F}_{q^{n}})}Fqn{\displaystyle \mathbb{F}_{q^{n}}}Cl⁡（C/Fqn）{\displaystyle \operatorname {Cl} (C/\mathbb {F} _{q^{n}})}JC（Fqn）{\displaystyle J_{C}(\mathbb{F}_{q^{n}})}Fqn[x]{\displaystyle \mathbb {F}_{q^{n}}[x]}

フロベニウス準同型σ は、 の元[u, v]において、その元の各係数のべき乗をq乗するために使用されます。σ( [u, v] ) = [ u q (x), v q (x)]。この準同型の特性多項式は次のようになります。 JC（Fqn）{\displaystyle J_{C}(\mathbb{F}_{q^{n}})}

χ（T）＝T2g＋a1T2g−1＋⋯＋agTg＋⋯＋a1qg−1T＋qg,{\displaystyle \chi (T)=T^{2g}+a_{1}T^{2g-1}+\cdots +a_{g}T^{g}+\cdots +a_{1}q^{g-1}T+q^{g},}

iが​Z{\displaystyle \mathbb {Z} }

ハッセ・ヴェイユの定理を用いると、χ( T )の複素根τiを用いて任意の拡大体の群順序を得ることができる。 Fqn{\displaystyle \mathbb {F} _{q^{n}}}

|JC(Fqn)|=∏i=12g(1−τin){\displaystyle |J_{C}(\mathbb {F} _{q^{n}})|=\prod _{i=1}^{2g}(1-\tau _{i}^{n})}

D をCのの要素とすると、の準同型、いわゆるD のトレースを定義することができます。 JC(Fqn){\displaystyle J_{C}(\mathbb {F} _{q^{n}})}JC(Fqn){\displaystyle J_{C}(\mathbb {F} _{q^{n}})}

Tr⁡(D)=∑i=0n−1σi(D)=D+σ(D)+⋯+σn−1(D){\displaystyle \operatorname {Tr} (D)=\sum _{i=0}^{n-1}\sigma ^{i}(D)=D+\sigma (D)+\cdots +\sigma ^{n-1}(D)}

この自己準同型に基づいて、ヤコビ多様体を、すべての要素がトレースゼロであるという性質を持つ 部分群Gに還元することができます。

G={D∈JC(Fqn) | Tr(D)=0},   (0 neutral element in JC(Fqn){\displaystyle G=\{D\in J_{C}(\mathbb {F} _{q^{n}})~|~{\text{Tr}}(D)={\textbf {0}}\},~~~({\textbf {0}}{\text{ neutral element in }}J_{C}(\mathbb {F} _{q^{n}})}

Gはトレース自己準同型の核であり、したがってGは のトレース零(部分)多様体(TZV)と呼ばれる群です。 JC(Fqn){\displaystyle J_{C}(\mathbb {F} _{q^{n}})}

Gとの交差はのn -ねじれ元によって生成される。 が最大公約数であれば、交差は空であり、 Gの群位数を計算できる。 JC(Fq){\displaystyle J_{C}(\mathbb {F} _{q})}JC(Fq){\displaystyle J_{C}(\mathbb {F} _{q})}gcd(n,|JC(Fq)|)=1{\displaystyle \gcd(n,|J_{C}(\mathbb {F} _{q})|)=1}

|G|=|JC(Fqn)||JC(Fq)|=∏i=12g(1−τin)∏i=12g(1−τi){\displaystyle |G|={\dfrac {|J_{C}(\mathbb {F} _{q^{n}})|}{|J_{C}(\mathbb {F} _{q})|}}={\dfrac {\prod _{i=1}^{2g}(1-\tau _{i}^{n})}{\prod _{i=1}^{2g}(1-\tau _{i})}}}

暗号アプリケーションで実際に用いられる群は、大きな素数位数lのGの部分群G 0である。この群はG自身である場合もある。[ 1 ] [ 2 ]

TZVの暗号関連には3つの異なるケースがある: [ 3 ]

  • g = 1、n = 3
  • g = 1、n = 5
  • g = 2、n = 3

算術

TZV群G 0で使用される演算は、群全体の演算に基づいています。しかし、フロベニウス自己準同型σ を用いてスカラー乗算を高速化することも可能です。これは、 G 0がl位のDによって生成される場合、 σ(D) = sD（ある整数sに対して）が成立することを意味します。TZV sの与えられたケースでは、a iはフロベニウス自己準同型 の特性多項式から得られる ため、以下のように計算できます。JC(Fqn){\displaystyle J_{C}(\mathbb {F} _{q^{n}})}

  • g = 1、n = 3の 場合:s=q−11−a1modℓ{\displaystyle s={\dfrac {q-1}{1-a_{1}}}{\bmod {\ell }}}
  • g = 1、n = 5の 場合:s=q2−q−a12q+a1q+1q−2a1q+a13−a12+a1−1modℓ{\displaystyle s={\dfrac {q^{2}-q-a_{1}^{2}q+a_{1}q+1}{q-2a_{1}q+a_{1}^{3}-a_{1}^{2}+a_{1}-1}}{\bmod {\ell }}}
  • g = 2、n = 3の 場合:s=−q2−a2+a1a1q−a2+1modℓ{\displaystyle s=-{\dfrac {q^{2}-a_{2}+a_{1}}{a_{1}q-a_{2}+1}}{\bmod {\ell }}}

これを知っていれば、任意のスカラー乗算mD (|m| ≤ l/2) を次のように置き換えることができます 。

m0D+m1σ(D)+⋯+mn−1σn−1(D),    where mi=O(ℓ1/(n−1))=O(qg){\displaystyle m_{0}D+m_{1}\sigma (D)+\cdots +m_{n-1}\sigma ^{n-1}(D),~~~~{\text{where }}m_{i}=O(\ell ^{1/(n-1)})=O(q^{g})}

このトリックを使うと、暗黙の定数が十分に小さければ、多重スカラー積はmDを計算するのに必要な倍加の約1/( n  −1)倍に減らすことができます。 [ 3 ] [ 2 ]

安全性

論文[ 2 ] [ 3 ]の結果によると、トレース零部分多様体に基づく暗号システムの安全性は、 |G|が約128ビット の場合、 p' ~ ( n  − 1)( g/g' )となる、低種数g'の超楕円曲線の安全性に匹敵しますFp′{\displaystyle \mathbb {F} _{p'}}

n = 3、g = 2 およびn = 5、g = 1の場合、Gが種数 6 の曲線のヤコビアンに含まれているかどうかは確実ではないため、セキュリティを最大 6 ビット ( |G| ~ 2 256)まで削減することが可能です。同様の体に対する種数 4 の曲線のセキュリティは、はるかに低くなります。

トレースゼロ暗号システムへのカバー攻撃

[ 4 ]で発表された攻撃法 は、標数が2または3より多様である有限体上の種数2のトレース零群と3次体拡大におけるDLPが、基底体上の種数が最大6である次数0の類群におけるDLPに変換できることを示している。この新しい類群では、 DLPは指数計算法を用いて攻撃可能である。これにより、ビット長が1/6に短縮される。

注記

  1. ^ Frey, Gerhard ; Lange, Tanja (2005). 「公開鍵暗号の数学的背景」(PDF) . Seminares & Congres . 11 : 41–73 .
  2. ^ a b cランゲ、タニャ(2003). 「暗号システムのためのトレースゼロ亜種」 .暗号学eプリントアーカイブ.
  3. ^ a b c Avanzi, Roberto M.; Cesena, Emanuele (2008). 「暗号応用のための特性2の体上のトレース零多様体」(PDF) .代数幾何学とその応用: 188– 215. doi : 10.1142/9789812793430_0010 . ISBN 978-981-279-342-3。
  4. ^ディエム、クラウス、ショルテン、ヤスパー。トレースゼロ暗号システムへの攻撃。CiteSeerX 10.1.1.295.9027 

参考文献

「 https://en.wikipedia.org/w/index.php?title=Trace_zero_cryptography&oldid=1322867073」から取得