Signed QR

まぁ詳しくはR. Ficshlin and C.-P. Schnorr (JoC 200)を見ていただくとして, Hofheinz and KiltzがCRYPTO 2009で発表する論文がDennis Hofheinzのサイトから読めるようになったのでメモですよ.

とりあえず, Nをnビットのブラム数とします. N=PQで, PとQはそれぞれn/2ビットの奇素数で, 特にP = Q = 3 mod 4です. Z_N^*は位数がφ(N) = (P-1)(Q-1)です.
J_Nでヤコビ記号が1になるような部分群を表します. するとJ_Nの位数は(P-1)(Q-1)/2です. なんでかって, -1がJ_Nに入るので.
次にQR_Nで平方剰余がなす群を表します. 今度はQR_NがJ_Nの部分群になって, さらに位数は(P-1)(Q-1)/4です.
さて, x∈Z_Nについて, |x|でxの絶対値を表します. x∈{-(N-1)/2,...,(N-1)/2}と表わされているとして, 符号を無視したものを絶対値とします.
で, Z_N^*の部分群Gについて, G⁺を{|x|:x∈G}として定義します.
ここに積をg*h = |g h mod N|で入れます. するとこれはちゃんと部分群になっています.
Nがブラム数なので, -1はQR_Nに入りません. これに注意すると,

1. (QR_N⁺, *)は位数(P-1)(Q-1)/4の群
2. QR_N⁺ = J_N⁺.
   • したがって, x∈Z_NがQR_N⁺に入るかどうか簡単に判定可能.
3. QR_Nが巡回群ならQR_N⁺も巡回群

が言えます.
すると定理2にある通り, 素因数分解が困難と仮定すると, ほとんど帰着のロス無しに, この群でSDH仮定が成立します. びっくりですね.

あー, ただSDHの仮定がちょっと違う点がポイントで, DDHオラクルは, (g,X,Y,Z)を受け取るのでも(X,Y,Z)を受け取るのでもなく, (g,X)固定で(Y,Z)だけ受取ります. これがうまくDDHオラクルをシミュレーションするためのミソになってます.