読者です 読者をやめる 読者になる 読者になる

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です. ZN*は位数がφ(N) = (P-1)(Q-1)です.
JNでヤコビ記号が1になるような部分群を表します. するとJNの位数は(P-1)(Q-1)/2です. なんでかって, -1がJNに入るので.
次にQRNで平方剰余がなす群を表します. 今度はQRNがJNの部分群になって, さらに位数は(P-1)(Q-1)/4です.
さて, x∈ZNについて, |x|でxの絶対値を表します. x∈{-(N-1)/2,...,(N-1)/2}と表わされているとして, 符号を無視したものを絶対値とします.
で, ZN*の部分群Gについて, G+を{|x|:x∈G}として定義します.
ここに積をg*h = |g h mod N|で入れます. するとこれはちゃんと部分群になっています.
Nがブラム数なので, -1はQRNに入りません. これに注意すると,

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

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

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