決定線形仮定

決定線形（DLIN）仮定は、楕円曲線暗号で使用される計算困難性仮定です。特に、DLIN仮定は、決定的ディフィー・ヘルマン仮定が成り立たない設定（ペアリングベースの暗号でよくあるケース）で役立ちます。決定線形仮定は、Boneh、Boyen、Shachamによって導入されました。^[1]

非公式には、DLIN 仮定は、ランダムな群要素とランダムな指数を持つ が与えられた場合、独立したランダムな群要素 と区別することが困難であると述べています。 ${\displaystyle (u,\,v,\,h,\,u^{x},\,v^{y})}$${\displaystyle u,\,v,\,h}$${\displaystyle x,\,y}$${\displaystyle h^{x+y}}$${\displaystyle \eta}$

対称ペアリングベースの暗号では、グループには双線型であるペアリングが備えられている。このマップは、決定的ディフィー・ヘルマン問題を解く効率的なアルゴリズムを提供する。 ^[2]入力 が与えられた場合、が に等しいかどうかを簡単に確認できる。これは、ペアリングを使用して次のように示される。 ${\displaystyle G}$${\displaystyle e:G\times G\to T}$${\displaystyle (g,\,g^{a},\,g^{b},\,h)}$${\displaystyle h}$${\displaystyle g^{ab}}$

${\displaystyle e(g^{a},g^{b})=e(g,g)^{ab}=e(g,g^{ab}).}$

したがって、 の場合、値と は等しくなります。 ${\displaystyle h=g^{ab}}$${\displaystyle e(g^{a},g^{b})}$${\displaystyle e(g,h)}$

ElGamal 暗号化と署名の構築に不可欠なこの暗号化仮定は、この場合には当てはまらないため、対称双線形群で暗号化を構築するには新しい仮定が必要です。DLIN 仮定は、上記の攻撃を阻止するために Diffie-Hellman タイプの仮定を修正したものです。

を素数位数の巡回群とする。、、を の一様乱数生成子とする。を の一様乱数元とする。分布を定義する。 ${\displaystyle G}$ ${\displaystyle p}$${\displaystyle u}$${\displaystyle v}$${\displaystyle h}$${\displaystyle G}$${\displaystyle a,b}$${\displaystyle \{1,\,2,\,\dots ,\,p-1\}}$

${\displaystyle D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b}).}$

を の別の一様ランダム要素とします。別の分布を定義します。 ${\displaystyle \eta}$${\displaystyle G}$

${\displaystyle D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta ).}$

決定線形仮定は、とが計算上区別できないことを述べています。 ${\displaystyle D_{1}}$${\displaystyle D_{2}}$

ボネ、ボイエン、シャチャムはエルガマル暗号に類似した公開鍵暗号方式を定義している。 ^[1]この方式では、公開鍵は生成子である。秘密鍵は2つの指数であり、 となる。暗号化は、メッセージと公開鍵を組み合わせて暗号文を作成する。 ${\displaystyle u,v,h}$${\displaystyle u^{x}=v^{y}=h}$${\displaystyle m\in G}$

${\displaystyle c:=(c_{1},\,c_{2},\,c_{3})=(u^{a},\,v^{b},\,m\cdot h^{a+b})}$。

暗号文を復号するには、秘密鍵を使って計算します。

${\displaystyle m':=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}.}$

この暗号化方式が正しいか、つまり両者がプロトコルに従っているかを確認するには、次の点に注意してください。 ${\displaystyle m'=m}$

${\displaystyle m'=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{a})^{x}\cdot (v^{b})^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{x})^{a}\cdot (v^{y})^{b})^{-1}.}$

そして、次 の事実を利用して${\displaystyle u^{x}=v^{y}=h}$

${\displaystyle m'=m\cdot h^{a+b}\cdot (h^{a}\cdot h^{b})^{-1}=m\cdot (h^{a+b}\cdot h^{-a-b})=m.}$

さらに、この方式は、DLIN 仮定が成り立つと仮定すると、 IND-CPA 安全です。

Boneh、Boyen、Shachamもグループ署名のスキームにDLINを使用しています。^[1]署名は、標準のセキュリティレベルではわずか250バイトで表現できるため、「短いグループ署名」と呼ばれています。

彼らのプロトコルは、まず線形暗号化を使用して、特別なタイプのゼロ知識証明を定義します。次に、フィアット・シャミールのヒューリスティックを適用して、証明システムをデジタル署名に変換します。彼らは、この署名が、グループ署名に必要な偽造不可能性、匿名性、追跡可能性という追加要件を満たしていることを証明します。

彼らの証明は、DLIN仮定だけでなく、 q {\displaystyle q} -強いDiffie-Hellman仮定と呼ばれる別の仮定にも依存しています。これはランダムオラクルモデルで証明されています。

2004年に定義されて以来、決定線形仮定はさまざまな応用が見られてきました。これには、Naor-Reingold構築を一般化する疑似乱数関数の構築、^{[3] 、}属性ベースの暗号化スキーム、^{[4] 、}非対話型ゼロ知識証明の特別なクラス^{[5]が含まれます}。