公開鍵暗号 - 暗号理論教室

---

公開鍵暗号とその安全性定義

公開鍵暗号とは効率的な確率的アルゴリズムの3つ組(Gen, Enc, Dec)である：

• (pk, sk) ← Gen(1ⁿ)
• c ← Enc(pk, m)
• m ← Dec(sk, c).

完全性(completeness)条件として、メッセージ空間Mに含まれる全てのメッセージmについて

• Pr[ (pk, sk) ← Gen(1ⁿ), c ← Enc(pk, m), m'← Dec(sk, c) : m = m' ] = 1

を要求する。

識別不可能性

選択平文攻撃に対する識別不可能性

暗号文がメッセージのどのような部分情報も漏らさないとき、その暗号は識別不可能であるという。
より正確に定義するために、公開鍵暗号Π=(Gen,Enc,Dec)とそれに対する攻撃者Aについて以下の試行を定義する：

試行 CPA_Π,A(n):

• (pk, sk) ← Gen(1ⁿ)
• pkを入力として攻撃者Aを起動する。
  • Aから同じ長さの2つのメッセージからなるチャレンジクエリ(m₀,m₁)を受け取ったら（チャレンジクエリは一度のみ許される）、
    • 0または1をランダムに選択し、bとする。
    • m_bをpkで暗号化し、c*をえる： c* ← Enc(pk, m_b)。
    • c*をチャレンジクエリに対する応答として返す。
• Aが出力b'で終了したら、b =^? b' の１ビットを出力とする。

定義(IND-CPA)
公開鍵暗号Πが選択平文攻撃に対し識別不可能（IND-CPA）であるとは、
任意の効率的な撃者Aについて、その識別利得

• ｜ Pr[ CPA_Π,A(n) = 1 ] - 1/2 ｜

がネグリジブルであることをいう。
（確率Pr[ CPA_Π,A(n) = 1 ]をAの成功確率と呼ぶ。）

もしも、暗号文c*からもとのメッセージの情報が漏れていれば、それを用いて攻撃者Aはもとのメッセージがm₀なのかm₁なのか、
推測できるはずである。

選択暗号文攻撃に対する識別不可能性

公開鍵暗号を通信環境におけるアプリケーションで利用するためには、
「復号オラクル」を用いることができる、より強力な攻撃者を想定する必要がある。
公開鍵暗号Π=(Gen,Enc,Dec)とそれに対する攻撃者Aについて以下の試行を定義する。

試行 CCA_Π,A(n):

• (pk, sk) ← Gen(1ⁿ)
• pkを入力として攻撃者Aを起動する。
  • Aから同じ長さの2つのメッセージからなるチャレンジクエリ(m₀,m₁)を受け取ったら（チャレンジクエリは一度のみ許される）、
    • 0または1をランダムに選択し、bとする。
    • m_bをpkで暗号化し、c*をえる： c* ← Enc(pk, m_b)。
    • c*をチャレンジクエリに対する応答として返す。
  • Aから復号クエリcを受け取ったら（復号クエリは何度でも許される）、
    • (c*がすでに定義されていて) c = c* なら⊥を応答する。
    • c = c* でないならば、その復号結果m ← Dec(sk, c)を応答する。
• Aが出力b'で終了したら、b =^? b' の１ビットを出力とする。

定義(IND-CCA2)
公開鍵暗号Πが適応的選択暗号文攻撃に対し識別不可能（IND-CCA2）であるとは、
任意のPPT攻撃者Aについて、その識別利得

• ｜ Pr[ CCA_Π,A(n) = 1 ] - 1/2 ｜

がネグリジブルであることをいう。
（確率Pr[ CPA_Π,A(n) = 1 ]をAの成功確率と呼ぶ。）

適応的選択暗号文攻撃では、

1. 攻撃者Aは、チャレンジャーから受け取った暗号文c*に関連付けて、別の暗号文c'を生成する。
2. 復号オラクルを用いてその復号文m'を得る。
3. m'からもとの暗号文c*の復号文m_bを推測する

といった攻撃が典型的である。

上の定義で、攻撃者Aの復号クエリがチャレンジクエリ以前に限定されるとき、
公開鍵暗号Πは非適応的選択暗号文攻撃に対し識別不可能（IND-CCA1）であるという。

頑健性

定義(BR93)
公開鍵暗号Πが頑健であるとは、任意のPPT関係ρ, PPT攻撃者(F,A)に対し、あるシミュレータA*が存在し、
以下のε(k) - ε*(k)がネグリジブルであることをいう：

• ε(k) = Pr[ (pk,sk) ← Gen(1ⁿ), π← F(pk), x ← π, α ← Enc(pk,x), α' ← A(pk,π,α) : ρ(x, Dec(sk,α'))=1 ]
• ε*(k) = Pr[ (pk,sk) ← Gen(1ⁿ), π← F(pk), x ← π, α' ← A*(pk,π) : ρ(x, Dec(sk,α'))=1 ]

ただし、関係ρは任意のxについて ρ(x,x) = ρ(x,⊥) = 0 であるものとする。

安全な公開鍵暗号の構成

選択平文攻撃に対し識別不可能な公開鍵暗号の構成

トラップドア置換にもとづく構成

定義
(G, {f_i}_i)がトラップドア置換であるとは、任意の (i, t_i) ← G(1ⁿ) について、

• f_i : {0,1}ⁿ → {0,1}ⁿ は一方向置換である。
• t_iを知っていたら、f_i^-1(・) は効率的に計算可能である。

ことをいう。t_iを（f_iの）トラップドアという。

RSA仮定のもとで、RSA関数 f_e,N(x) = x^e mod N は（dをトラップドアとする）トラップドア置換である。

構成(CPA暗号)
(G, {f_i}_i) : トラップドア置換
hc_i : f_iのハードコア述語

• Gen(1ⁿ):
  • (pk, sk) = (i, t_i) ← G(1ⁿ).
• Enc(pk = i, m):      // m∈{0,1}^l
  • r ← {0,1}ⁿ
  • f_i(r), f_i²(r), ..., f_i^l(r) を計算。
  • p = ( hc_i(f_i^l-1(r)), hc_i(f_i^l-2(r)), ..., hc(r) )
  • return c = (m + p, f_i^l(r)).
• Dec(sk = t_i, c = (m', w)):
  • t_iを用いて w=f_i^l(r) から r を求める。
  • p = ( hc_i(f_i^l-1(r)), hc_i(f_i^l-2(r)), ..., hc(r) )
  • return m' - p.

定理(CPA暗号)
{f_i}_iが、ハードコア述語{hc_i}_iをもつ、トラップドア置換ならば、
構成(CPA暗号)の公開鍵暗号は選択平文攻撃に対し識別不可能（IND-CPA）である。

証明

エルガマル暗号

(g^a,g^b)が与えられて、g^abを求める問題を計算DH問題と呼ぶ。
計算DH問題は困難であるとの仮定を計算DH仮定という。より正確には、

仮定(CDH仮定)
群生成アルゴリズムGenGに対して計算DH仮定が成り立つとは、
任意の効率的なアルゴリズムAについて、その成功確率

• Pr[s=(q,g) ← GenG(1ⁿ), a,b ← Z_q ： A(s, g^a,g^b) = g^ab]

がネグリジブルであることをいう。

離散対数問題が解ければ計算DH問題も解けるので、
（すなわち、計算DH問題は離散対数問題ほどには難しくないので、）
計算DH仮定は離散対数仮定より強い仮定である。

計算DH問題は、その答えが与えられてもそれとはわからい（ほどに難しい）、という仮定を判定DH仮定という。
より正確には、

仮定(DDH仮定)
群生成アルゴリズムGenGに対して判定DH仮定が成り立つとは、
任意の効率的なアルゴリズムDについて、その識別利得

• ｜ Pr[s=(q,g) ← GenG(1ⁿ), a,b ← Z_q ： D(s, g^a,g^b,g^ab)) = 1] -
  • Pr[s=(q,g) ← GenG(1ⁿ), a,b,c ← Z_q ： D(s, g^a,g^b,g^c)) = 1] ｜

がネグリジブルであることをいう。

• (g^a,g^b,g^ab)の形の3つ組をDHタプルと呼ぶ。

注意
判定DH仮定のもとで、

• G_g,g^a(x) =^def (g^x, g^ax)

は疑似乱数生成器。

構成(エルガマル暗号)
GenG(1ⁿ) : 群生成アルゴリズム

• Gen(1ⁿ):
  • (q, g) ← GenG(1ⁿ), x ← Z_q, y = g^x
  • pk=(q,g,y), sk = (q,g,x).
• Enc(pk=(q,g,y), m):      // m∈<g>
  • r ← {0,q-1}, c₁ = g^r, c₂ = m y^r
  • return c = (c₁, c₂).
• Dec(sk=(q,g,x), c=(c₁, c₂)):
  • return c₂/c₁^x.

定理(エルガマル暗号)
群生成アルゴリズムGenGが判定DH仮定を満たすならば、エルガマル暗号は選択平文攻撃に対し識別不可能（IND-CPA）である。

証明

ランダムオラクルモデルにもとづく構成

ハッシュ関数G : {0,1}* → {0,1}^l への呼び出しをランダムオラクルO_G(・)への呼び出しに
置き換えてしまう（アルゴリズムの実行）モデルを（Gについての）ランダムオラクルモデルと呼ぶ。

構成(ランダムオラクル)
O_G :

• 初期化： lビット出力の関数Gをランダムに選択する。
  • ※ 値xごとに独立なlビット乱数G(x)を選択することと同じ。
• 問い合わせ x を受け取ったら、
  • G(x) を返す。

構成(CPAinRO)
(Genf, {f_i}_i) : トラップドア置換

• Gen(1ⁿ):
  • (i,t_i) ← Genf(1ⁿ)
  • ハッシュ関数 G : {0,1}* → {0,1}^l を選択
  • return pk=(i,G), sk = (t_i,G).
• Enc(pk=(i,G), m):      // m∈{0,1}^l
  • r ← {0,1}ⁿ
  • return c = (f_i(r), G(r)+m).
• Dec(sk=(t_i,G), c=(y, s)):
  • t_iを用いて、r ← f_i^-1(y)
  • return s - G(r).

定理(CPAinRO)
ハッシュ関数Gについてのランダムオラクルモデルにおいて、
{f_i}_iがトラップドア置換ならば、構成(CPAinRO)は選択平文攻撃に対し識別不可能（IND-CPA）である。

証明

適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号の構成

ジェネリックな構成

構成(DDN)
(Gen,Enc,Dec) : 選択平文攻撃に対し識別不可能な公開鍵暗号
(P, V) : 言語Lに対する非対話零知識証明システム　：

• L = {(c₁,...,c_n) | ∃m,(w₁,...,w_n) s.t. c_i = Enc(pk_i, m; w_i)}
  • ※ 簡単のため、pk_iはc_iに含まれているとする。

(SigGen, Sign, Verify) : ワンタイム署名

公開鍵暗号(Gen', Enc', Dec') :

• Gen'(1ⁿ):
  • r ← {0,1}^poly(n)
  • i ∈ [1..n] : (pk_i,0,sk_i,0) ← Gen(1ⁿ), (pk_i,1,sk_i,1) ← Gen(1ⁿ)
  • pk = (r, (pk_1,0,...,pk_n,0 | pk_1,1,...,pk_n,1)), sk = (sk_1,0,...,sk_n,0 | sk_1,1,...,sk_n,1).
• Enc'(pk, m):
  • (vk,sk) ← SigGen(1ⁿ), (v₁,...,v_n) = vk
  • i ∈ [1..n] : w_i ← {0,1}*, c_i = Enc(pk_{i,v_i}, m; w_i)
  • C = (c₁,...,c_n)
  • Π ← P(r, C, (m,(w₁,...,w_n))), σ ← Sign(sk, (C,Π))
  • return (vk,C,Π,σ).
• Dec'(sk,(vk,C,Π,σ)):
  • Verify(vk,(C,Π),σ) =^? 0 : return ⊥
  • else V(r,C,Π) =^? 0 : return ⊥
  • else return Dec(sk_{1,vk_1},c₁).

定理(DDN)
(Gen,Enc,Dec)が選択平文攻撃に対し識別不可能な公開鍵暗号で、
(P,V)が上記の言語Lに対する適応的安全な非対話零知識証明システムで、
(SigGen, Sign, Verify)がストロングワンタイム署名ならば、
(Gen',Enc',Dec')は適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号である。

ランダムオラクルモデルにもとづく構成

CCAinRO

構成(CCAinRO) [BR 93]
[部品]

• トラップドア置換 : (Genf, {f_i}_i)
• ハッシュ関数 G : {0,1}* → {0,1}^l
• ハッシュ関数 H : {0,1}* → {0,1}ⁿ

[スキーム]

• Gen(1ⁿ):
  • (i,t_i) ← Genf(1ⁿ)
  • return pk=(i,G,H), sk = (t_i,G,H)
• Enc(pk=(i,G,H), m): 　※ m∈B^l.
  • r ← {0,1}ⁿ
  • return c = (f_i(r), G(r)+m, H(r,m))
• Dec(sk=(t_i,G,H), c=(a,w,b)):
  • t_iを用いて、r ← f_i^-1(a)
  • m = w - G(r)
  • H(r,m) =^? b: return m else return ⊥

定理(CCAinRO) [BR 93]
ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、
{f_i}_iがトラップドア置換ならば、
構成(CCAinRO)は適応的選択暗号文攻撃に対し識別不可能である。

証明

定理(NMinRO) [BR 93]
ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、
{f_i}_iがトラップドア置換ならば、構成(CCAinRO)は(BR93の意味で)頑健である。

証明

• この構成はトラップドア置換を用いているので、たとえばエルガマル暗号には適用できない。

平文検査攻撃における一方向性

平文と暗号文の対(c,m)を受け取ると、暗号文cの復号結果が平文mと一致するか否かの1ビットだけを
教えてくれるオラクルを平文検査オラクル(PCO)と呼ぶ。
平文検査オラクルを用いることができても、一方向性をたもつ公開鍵暗号を平文検査攻撃に対し一方向であるという。
より正確には：

定義(OW-PCA)
公開鍵暗号(Gen,Enc,Dec)が平文検査攻撃に対し一方向（OW-PCA）であるとは、
任意の効率的な撃者Aについて、その成功確率

• Pr[ (pk,sk) ← Gen, m ← M, y ← Enc(pk,m), m' ← A^PCO(sk,・)(y) ： m' = m ]

がネグリジブルであることをいう。

• Gap仮定（判定DH問題を解くオラクルが与えられても、計算DH問題は難しい）のもとで、

エルガマル暗号は平文検査攻撃に対し一方向である。

REACT

構成(REACT) [OP01]
(Gen,Enc,Dec) : 平文検査攻撃に対し一方向である公開鍵暗号
G : {0,1}* → {0,1}^l : ハッシュ関数
H : {0,1}* → {0,1}^k : ハッシュ関数

REACT = (Gen', Enc', Dec'):

• Gen'():
  • (pk, sk) ← Gen().
• Enc'(pk, m):      // m ∈ {0,1}^l
  • r ← M, a ← Enc(pk, r)      // Mは(Gen,Enc,Dec)のメッセージ空間
  • b = m + G(r), c = H(r, m, a, b)
  • return C = (a, b, c).
• Dec'(sk, C=(a,b,c)):
  • r ← Dec(sk, a), m = b - G(r)
  • c =^? H(r, m, a, b) : return m
  • else return ⊥.

定理(REACT) [OP 01]
ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、
(Gen,Enc,Dec)が平文検査攻撃に対し一方向ならば、
構成(REACT)は適応的選択暗号文攻撃に対し識別不可能である。

証明

双子エルガマル暗号

G=<g> について、

• DHタプル： (g, g^x, g^y, g^xy)
• 双子DHタプル： (g, g^x₁, g^x₂, g^y, g^x₁y, g^x₂y).

仮定(双子計算DH仮定)
双子DHタプルを判定してくれるオラクルが与えられても、
双子DHタプルの計算は困難であるという仮定を双子計算仮定という。

より正確には、
群生成アルゴリズムGenGに対して双子計算DH仮定が成り立つとは、
任意の効率的なアルゴリズムAについて、その成功確率

• Pr[s=(q,g) ← GenG(1ⁿ), X₁,X₂,Y ← <g> ：
  • A^{2dhp_g(X1,X2,・,・,・)}(X₁,X₂,Y) = 2dh_g(X₁, X₂, Y)]

がネグリジブルであることをいう。ここで、

• 2dh_g(X₁, X₂, Y) =^def (g^{x1 y}, g^{x2 y}),
• 2dhp_g(X₁, X₂, Y, Z₁, Z₂) =^def 『 2dh_g(X₁, X₂, Y) =^? (Z₁, Z₂) 』.

命題(双子計算DH仮定)
計算DH仮定のもとで、双子計算DH仮定は真である。

証明

構成(双子エルガマル暗号)
(E, D): 鍵空間Kをもつ共通鍵暗号
H : {0,1}* → K : ハッシュ関数

• Gen(1ⁿ):
  • (q, g) ← GenG(1ⁿ)
  • x₁, x₂ ← Z_q, X₁ = g^x1, X₂ = g^x2
  • pk=(q,g,X₁,X₂), sk = (q,g,x₁,x₂).
• Enc(pk, m) :
  • y ← Z_q
  • Y = g^y, Z₁ = X₁^y, Z₂ = X₂^y, k = H(Y,Z₁,Z₂)
  • return (Y, c = E(k, m)).
• Enc(sk, (Y,c)) :
  • Z₁ = Y^x1, Z₂ = Y^x2, k = H(Y,Z₁,Z₂)
  • return m = D(k, c).

定理(双子エルガマル暗号)
ハッシュ関数Hに対するランダムオラクルモデルにおいて、
GenGが計算DH仮定を満たし、共通鍵暗号(E,D)が適応的選択暗号文攻撃に対し識別不可能であるならば、
双子エルガマル暗号は適応的選択暗号文攻撃に対し識別不可能である。

ランダムオラクルモデルを必要としない構成

Cramer-Shoup暗号

構成(CS暗号)

• Gen(1ⁿ) :
  • ハッシュ関数 H : {0,1}* → Z_q を選択。
  • (q, g₁, g₂) ← GenG(1ⁿ)
  • x, y, a, b, a', b' ← Z_q
  • h = g₁^x g₂^y, c = g₁^a g₂^b, d = g₁^a' g₂^b'
  • pk = (g₁,g₂,h,c,d,H), sk = (x,y,a,b,a',b').
• Enc(pk, m) :      // m ∈ <g₁>
  • r ← Z_q, α = H(g₁^r, g₂^r, h^rm)
  • return C = (g₁^r, g₂^r, h^rm, (cd^α)^r).
• Dec(sk, C=(u,v,w,e)) :
  • α = H(u, v, w)
  • u^a+αa'v^b+αb' ≠ e : return ⊥
  • else return w / (u^xv^y).

定理(CS暗号)
ハッシュ関数Hが衝突困難で、GenGが決定DH仮定を満たすならば、
CS暗号は適応的選択暗号文攻撃に対し識別不可能である。

証明

Camenish-Shoup暗号

仮定(DCR仮定)
整数 n (=pq) を与えられて、
Zn2* のランダム要素と(Zn2*)nのランダム要素を識別できない
とき、 Decision Composite Residuosity (DCR) 仮定が成り立つという。

• abs : Z_n²* → Z_n²*
  • abs(a) = (n² - a) mod n²　　( if a > n² / 2 )
  • abs(a) = a mod n² 　　otherwise

構成(Camenish-Shoup暗号)

• Gen(1^l) :
  • ハッシュ関数 H : {0,1}* → [2^l]
  • p', q' : lビットの異なる Sophie-Germain 素数
  • p = 2p' + 1, q = 2q' + 1, n = pq, n' = p'q'
  • x₁, x₂, x₃　←　[n²/4],　g' ← Z_n²*
  • g = (g')²ⁿ, y₁ = g^x₁, y₂ = g^x₂, y₃ = g^x₃
  • pk = (H, n, g, y₁, y₂, y₃),　sk = (H, n, x₁, x₂, x₃).
• Enc(pk, m, L) :      // m ∈ [n], Lはラベル
  • r ← [n/4]
  • u = g^r, e = y₁^r h^m, v = abs( (y₂y₃^H(u,e,L))^r )
  • return (u, e, v).
• Dec(sk, (u,e,v), L) :
  • abs(v) =^? v
  • u^{2(x₂ + H(u,e,L)x₃)} =^? v²
  • t = 2^-1 mod n
  • m' = (e / u^x1)^2t
  • m ' が h^m (∃m ∈ [n]) の形ならば、m を出力。
  • そうでないならば、reject.

定理(Camenish-Shoup暗号)
ハッシュ関数Hが衝突困難で、DCR仮定が成り立つならば、
Camenish-Shoup暗号は適応的選択暗号文攻撃に対し識別不可能である。

タグベース暗号

タグベース暗号とは、
効率的な確率的アルゴリズムの3つ組(Gen_tbe, Enc_tbe, Dec_tbe)である：

• (pk, sk) ← Gen_tbe(1ⁿ)
• c ← Enc_tbe(pk, t, m)
• m ← Dec_tbe(sk, t, c).

完全性(completeness)条件として、
全てのメッセージm(∈M)とすべてのタグt(∈T)について

• Pr[ (pk, sk) ← Gen_tbe(1ⁿ), c ← Enc_tbe(pk, t, m), m'← Dec_tbe(sk, t, c) : m = m' ] = 1

を要求する。

タグ選択暗号文攻撃に対する識別不可能性

タグベース暗号TBE=(Gen_tbe,Enc_tbe,Dec_tbe)とそれに対する攻撃者Aについて：

試行 StagCCA_TBE,A(n):

• (t*, st₀) ← A(1ⁿ)
• (pk, sk) ← Gen_tbe(1ⁿ)
• (M₀, M₁, st) ← A^{Dec_tbe(・,・)}(pk, st₀)
• b ← {0,1}, c* ← Enc_tbe(pk, t*, M_b)
• b' ← A^{Dec_tbe(・,・)}(c*, st)
• return b =^? b'.
  • ただし、Aは復号オラクルDec_tbe(・,・)にタグt*について問い合わせることは許されない。

定義(IND-STAG-CCA)
タグベース暗号TBEがタグ選択暗号文攻撃に対し識別不可能(IND-STAG-CCA)であるとは、
任意の効率的な攻撃者Aについて、その識別利得　

• ｜ Pr[ StagCCA_TBE,A(n) = 1 ] - 1/2 ｜

がネグリジブルであることをいう。

タグベース暗号から公開鍵暗号への変換

構成(TBE2PKE)
TBE = (Gen_tbe, Enc_tbe, Dec_tbe) : タグ空間Tのタグベース暗号
OTS = (SKG, SIGN, VFY) : ワンタイム署名 (s.t. vk ∈ T)

PKE = (Gen_pke, Enc_pke, Dec_pke) : 公開鍵暗号 :

• Gen_pke = Gen_tbe.
• Enc_pke(pk, m):
  • (vk, sigk) ← SKG(1ⁿ)
  • c_tbe ← Enc_tbe(pk, vk, m)
  • σ ← SIGN(sigk, c_tbe)
  • return c = (c_tbe, vk, σ).
• Dec_pke(sk, c):
  • (c_tbe, vk, σ) = c
  • VFY(vk, c_tbe, σ) =^? reject:　 return ⊥
  • else return m = Dec_tbe(sk, vk, c_tbe).

定理(TBE2PKE) [Kiltz 06]
TBEがタグ選択暗号文攻撃に対し識別不可能なタグベース暗号で、
OTSがストロングワンタイム署名ならば、
PKE = TBE2PKE(TBE, OTS) は適応的選択暗号文攻撃に対し識別不可能である。

証明

タグ選択暗号文攻撃に対し識別不可能なタグベース暗号の構成

判定線形仮定

群G=<g>について、

• 線形タプル: (g₁, g₂, z, g₁^r1, g₂^r2, z^r1+r2).

定義(判定線形仮定)
群Gについて、与えられた6要素からなるタプル

• (g₁, g₂, z, g₁^r1, g₂^r2, w)

が線形タプルかランダムタプルかを判定する問題を判定線形問題という：

• w =^? z^r1+r2.

判定線形問題が困難であるとの仮定を判定線形仮定という。

命題(DLinear) 判定線形仮定は判定DH仮定よりも弱い仮定である（より妥当な仮定である）。
すなわち、判定線形問題が解けるときは判定DH問題も解ける。
証明

命題(DLinear)は、判定DH問題が解けても判定線形問題は解けない、という可能性は除外しない。
実際、双線形群にはそのような可能性を期待できる。

ある群Gについて、判定DH問題は易しいのに判定線形問題はむずかしいとき、
群Gは判定線形ギャップ仮定をみたすという。

注意
(g, g^x₁, g^x₂, g^y, g^x₁y, g^x₂y)：双子DHタプル
⇒ (g^y-1, g^y-1, g, g^x₁, g^x₂, g^x₁y+x₂y) : 線形タプル

判定線形仮定にもとづくタグ選択暗号文攻撃に対し識別不可能なタグベース暗号

構成(LinearTBE) [Kiltz 06]

• Gen_tbe(1ⁿ):
  • G: 位数q の群
  • g₁ ← G, (x₁,x₂,y₁,y₂) ← Z_q
  • g₂, z を g₁^x1 = g₂^x2 = z となるようにとる。
  • u₁ = g₁^y1, u₂ = g₂^y2
  • pk = (q, g₁, g₂, z, u₁, u₂), sk = (x₁, x₂, y₁, y₂).
  • ※ (g₁, g₂, z, -, -, -)は判定線形問題の問題文の一部。
  • ※ 秘密鍵skを知っていれば、この問題文（の一部）に関する判定線形問題は容易：
    • ※ (g₁, g₂, z, c₁, c₂, w)は線形タプル ⇔ c₁^x1 c₂^x2 = w.
• Enc_tbe(pk, t, m):
  • r₁,r₂ ← Z_q*, c₁ = g₁^r1, c₂ = g₂^r2
  • d₁ = z^tr1 u₁^r1, d₂ = z^tr2 u₂^r2, e = m z^r1+r2
  • return c_tbe = (c₁, c₂, d₁, d₂, e).
  • ※ (g₁, g₂, z, c₁, c₂, z^r1+r2)は線形タプル。
    • ※ 実際、c₁^x1 c₂^x2 = z^r1+r2.
  • ※ d₁, d₂はc₁, c₂の正当性を示す：
    • ※ c₁^tx1+y1 = d₁, c₂^tx2+y2 = d₂.
• Dec_tbe(pk, t, c_tbe):
  • s₁,s₂ ← Z_q*
  • k = (c₁^{x1+s1(tx1+y1)} c₂^{x2+s2(tx2+y2)}) / (d₁^s1d₂^s2)
  • ※ 正当な暗号文、すなわち　c_i^tx_i+y_i = d_i 　(i=1,2)　のときだけ、まともに復号される。
    • ※ k = c₁^x1 c₂^x2 = z^r1+r2.
  • return m = e / k.
• (パブリック検証) Pv_tbe(pk, t, c_tbe):　暗号文の正当性は公開情報だけで確認できる
  • return DH(g₁, z^t u₁, c₁, d₁) ∧ DH(g₂, z^t u₂, c₂, d₂).
  • ※ ⇔　d_i = c_i^txi+yi　 (for i=1,2).

定理(LinearTBE) [Kiltz 06]
群Gに対する判定線形ギャップ仮定のもとで、
構成(LinearTBE)はタグ選択暗号文攻撃に対し識別不可能なタグベース暗号である。

証明

上へ

---