Memo_Pairing

Memo_Pairing

Basics

位数は素数pとしておく.

G,G'を位数pの群とする. 計算は積で (DLPも一緒に扱いたいので, そっちの方が良いかなぁと).

群が1つ.

DLP
Given (g,g^x), find x.
CDHP
Given (g,g^x,g^y), compute g^{xy}.
DDHP
Given (g,g^x,g^y,g^z), decide g^{xy}=g^z or not.
q-CDHIP
Given (g,g^x,g^{x^2},...,g^{x^q}), compute g^{1/x}.
q-DDHIP
Given (g,g^x,g^{x^2},...,g^{x^q},g^z), decide g^{1/x}=g^z or not.
q-sCDHIP
Given (g,g^x,g^{x^2},...,g^{x^q}), compute (c,g^{1/(x+c)}).
q-sDDHIP
Given (g,g^x,g^{x^2},...,g^{x^q},c,g^z), decide g^{1/(x+c)}=g^z or not. (こんな問題あるの?).
Linear Problem
Given (g_1,g_2,g_3,g_1^a,g_2^b,g_3^z), decide g_3^{a+b}=g^{z} or not.

q-s*DHIP ≦ q-*DHIPは簡単. q-*DHIP ≦ *DHPはまぁ出来る.

q-sDDHIP ≦ q-DDHIP の帰着.

  1. g,g^x,g^{x^2},...g^{x^q},c,g^zが入力
  2. g,g^{x+c},g^{(x+c)^2},...,g^{(x+c)^q},g^zをq-DDHIPオラクルに入力. (g^{1/(x+c)}=g^zかどうか分かる.)
  3. q-DDHIPオラクルの出力をそのまま返す.
  4. メモ:インスタンスの生成は出来る. g^z側を変形するのは無理か?

1-DDHIP ≦ DDHP の帰着.

  1. g,g^x,g^zが入力.
  2. g,g^x,g^z,gをDDHPオラクルに入力. (g^{xz}=gかどうか分かる.)
  3. DDHPオラクルの出力をそのまま返す.

g,g^x,g^{x^2},...,g^{x^q}からa^{x^{q+1}} or a^{x^{1/x}}を求める問題はインスタンスの並びをひっくり返せば良いので帰着がタイト.

ランダム自己帰着性

DLPにはRandom Self-Reducibilityがある. 従って, 最悪時の困難性を仮定すると, 自動的に平均時の困難性が導かれる. (疑問:CDHP, DDHPにはあるか?)

KEA系

ちょっと適当なので後で調べる.

KEA1 (Knowledge-of-Exponent Assumption)

Damgård “Towards practical public key systems secure against chosen ciphertext attacks”(CRYPTO 1991)?

(g, g^a)が与えられたときにaの情報が無い場合, (x,x^a)というペアを構成したTMは, 内部にr (x=g^r) という情報を持っている筈だ, という仮定.

正しく書くと以下になる.

任意のPPTM Aに対して, (x,y)<-A(G,g,g^a)のとき, 必ずPPTM Eが存在して, (x,y,r)<-E(G,g,g^a)で, Pr[y=x^a and g^r≠x]は無視できる確率である.

KEA2

Hada and Tanakaが提唱するも, ダメだった奴.

KEA3

Bellare and Palaciaかな. 色々やってる.

GKEA (Generalized KEA)

J. Wu, D. R. Stinson. “Efficient Identification Protocols and the Knowledge-of-Exponent Assumption”(ePrint 2007/479)

AI-KEA (Auxiliary-Input KEA)

J. Wu, D. R. Stinson. “Efficient Identification Protocols and the Knowledge-of-Exponent Assumption”(ePrint 2007/479)


群が2つ

非退化な双線形写像 e:G \times G \to G' が存在する場合

DLP on G, G'
same as the above.
CDHP on G, G'
same as the above.
DDHP on G
same as the above. We can decide g^{xy}=g^z or not, since e(g^x,g^y)=e(g^{xy},g).
DDHP on G'
same as the above.
BDHP
Given (g,g^x,g^y,g^z), compute e(g,g)^{xyz}.
  • DDHP_G ≦ CDHP_G ≦ DLP_G
  • DDHP_{G'} ≦ CDHP_{G'} ≦ DLP_{G'}
(2006/05/22追加)

Boneh, BoyenのHIBE辺りから拾ったものだと思う.

q-BDHIP
Given (g,g^x,g^{x^2},...,g^{x^q}), compute e(g,g)^{1/x}
q-wBDHIP
Given (g,h,g^x,g^{x^2},...,g^{x^q}), compute e(g,h)^{1/x}
q-wBDHIP*
Given (g,h,g^x,g^{x^2},...,g^{x^q}), compute e(g,h)^{x+1}
q-BDHEP
Given (g,h,g^x,g{x^2},...,g^{x^{q-1}},g^{x^{q+1}},...,g^{x^{2q}}, compute e(g,h)^{x+1}
  • q-wBDHIP ≦ BDHP
  • q-wBDHIP ⇔ q-wBDHIP*
  • (q+1)-BDHEP ≦ q-wBDHIP*
  • q-BDHIP ≦ q-wBDHIP

(2006/07/13追加)

C. Gentry "Practical Identity-Based Encryption without Random Oracles"から.

q-BDHEP
Given (g',g,g^x,g^{x^2},...,g^{x^q},g^{x^{q+2}},...,g^{x^{2q}})\in G^{2q+1}, compute e(g,g')^{x^{q+1}}
q-ABDHEP
Given (g',g'^{x^{q+2}},g,g^x,g^{x^2},...,g^{x^q},g^{x^{q+2}},...,g^{x^{2q}})\in G^{2q+2}, compute e(g,g')^{x^{q+1}}
(2006/05/27追加)

ここかな. V. K. Wei "More Compact E-Cash with Efficient Coin Tracing"から.

co-CDHP
Given (g,g^x \in G, h \in G'), compute h^x.
co-DDHP
Given (g,g^x \in G ,h,h^y \in G'), decide h^x=h^y or not. or decide g^x=g^y or not.
co-GDHP
Compute co-CDHP with the oracle of co-DDHP.

双線形写像e:G \times G \to G'があると, *DHVPと呼ぶらしい. *1

双線形写像e:G \times G' \to G''の場合は, e(g,h^y)=e(g^x,h)を確かめれば良いので, co-DDHPが解ける.

q-DHIP
Given (g,g^x,g^{x^{2}},...,g^{x^{q}} \in G, h \in G'), compute h^{1/x}.
q-DDHIP
Given (g,g^x,g^{x^{2}},...,g^{x^{q}} \in G, h, h^z \in G'), decide h^z=h^{1/x} or not.

双線形写像e:G \times G \to G'があると, q-DHIV, q-DDHIVと呼ぶ.

q-sDHP
Given (g \in G, h, h^{x}, h^{x^2},...,h^{x^q} \in G'), compute (c,g^{\frac{1}{x+c}}).

DHTDHPはV. K. Weiが導入.

DLTDHP
Given (g,g^x \in G, h, h^y \in G', c, z \in N), decide h^y=h^{cx+z} or not.
DITDHP
Given (g,g^x \in G, h, h^y \in G', c, z \in N), decide h^y=h^{\frac{c}{x}+z} or not.
DHTDHP
Given (g,g^x \in G, h, h^y \in G', c, z \in N), decide h^y=h^{\frac{1}{c\frac{1}{x}+z}} or not.

LTとかはLinearly-Tipped, Inversely-Tipped, Harmonically-Tippedの略.

双線形写像e:G \times G' \to G''の場合は, 全滅. 双線形写像e:G \times G \to G'の場合は残る(かも).

非退化な双線形写像 e:G_1 \times G_2 \to G' が存在する場合

XDH assumption
G_2からG_1の同型写像\psiは計算出来るけれど, 逆写像\psi^{-1} : G_1 \to G_2が計算出来ない. この場合, G_2上のDDHは計算出来るけど, G_1上のDDHは計算出来ない.

XDH 仮定を置かない場合は, 逆写像が存在してG_1G_2を同一視可能.

co-BDHP
Given (g_1,g_1^x,g_1^y \in G_1, g_2 \in G_2), compute e(g_1,g_2)^{xy}.
DLDHP
Given (g_1,g_1^x \in G_1,g_2,g_2^y \in G_2, h, h^z \in G_3), decide h^{x+y}=h^z or not.
DIDHP
Given (g_1,g_1^x \in G_1,g_2,g_2^y \in G_2, h, h^z \in G_3), decide h^{x+\frac{1}{y}}=h^z or not.
DHDHP
Given (g_1,g_1^x \in G_1,g_2,g_2^y \in G_2, h, h^z \in G_3), decide h^{\frac{1}{x}+\frac{1}{y}}=h^z or not.

双線形写像 e:G_1 \times G_2 \to G'があった場合は, D*DHVPになる

その他

k+1-SRP (k+1 Square Roots Problem)

ePrint Arhicve 2005/386 - Fangguo Zhang, Xiaofeng Chen, Willy Susilo and Yi Mu. A New Short Signature Scheme Without Random Oracles from Bilinear Pairingsから.

For an integer k, and  x \in_R Z_q, g \in G, given (g,g^x, (h_1,...,h_k), g^{(x+h_1)^{1/2}},...,g^{(x+h_k)^{1/2}}), compute g^{(x+h)^{1/2} for some h \not\in \{h_1,...,h_k\}.

SXDH仮定 (Symmetric External Diffie-Hellman仮定)

M. H. Au, Q. Wu, W. Susilo, Y. Mu "Compact E-Cash from Bounded Accumulator" (CT-RSA 2007)から.

G_1, G_2, G3e:G_1 \times G_2 \to G'を考える. G_1, G_2の両方でDDHが解けないという仮定. XDHよりも強い.

DDHが解けないけども色々出来るらしい.

GDDH?

Hashed Gap Decisional Diffie-Hellman Problem.

Kiltzが何かやってた気がする. (PKC 2007辺りで).

ODH問題 (oracle Diffie-Hellman problem)

Abdalla, Bellare, and Rogaway (CT-RSA 01) らしい.

ePrint 2007/468で知る.

H:\{0,1\}^*\to\{\}^{h}暗号学的ハッシュ関数とする.

という二つの試行を考える. (ただしAはH_vにUをクエリしてはいけない.)

敵のAdvは二つの試行が1を出力する確率の差とする.

q-DHSDH [FPV09]

Given G,H,K,X=G^x \in \mathbb{G} and q-1 tuples

\left(A_i=(KG^{v_i})^{1/(x+c_i)}, C_i=G^{c_i}, D_i=H^{c_i}, V_i=G^{v_i}, W_i=H^{v_i}\right) for random c_i and v_i,

it is hard to output a new tuple (A^*,C^*,D^*,V^*,W^*) that satisfies

e(A^*,X C^*)=e(K V^*,G), e(C^*,H)=e(G,D^*), e(V^*,H)=e(G,W^*)

q-DAHSDH

Fuchsbauer (ePrint 2009/320)より.

Given G,F,H,K,X=G^x,Y=H^x \in \mathbb{G} and q-1 tuples

\left(A_i=(KG^{v_i})^{1/(x+c_i)}, C_i=G^{c_i}, D_i=F^{c_i}, V_i=G^{v_i}, W_i=H^{v_i}\right) for random c_i and v_i,

it is hard to output a new tuple (A^*,C^*,D^*,V^*,W^*) that satisfies

e(A^*,X C^*)=e(K V^*,G), e(C^*,F)=e(G,D^*), e(V^*,H)=e(G,W^*)

メモ

まだ紹介しきれていないという罠.

*1:L. Nguyen, R. Safavi-Naini. "Efficient and provably secure trapdoor-free group signature schemes from bilinear pairings" ASIACRYPT2004 に載っているそうな.