Paillierの話

適当に調べ物をしていたら, Partial Discrete Logarithm Problemってものを見つけたのでメモ.

N=pqをsafe primeの積とします (p=2p'+1, q=2q'+1). GをQR(N^2)とします. N^2を法とした平方剰余が成す巡回群. するとGの位数はpp'qq'. また, 位数Nの元はちょうど1+kNの剰余類になっている. さて, gをg^{2p'q'} mod N^2 = 1+N mod N^2となる元だとする. すると, gとh (=g^a mod N^2) を与えられたときにaを求めるのは難しそうである. これがPartial DL問題.
で, 実はNの素因数分解を知っていると, PDLが解けてしまうことがPaillierによって示されている.

ASIACRYPT 2003のEmmanuel Bresson, Dario Catalano and David Pointcheval “A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and its Applications”から引くと, アルゴリズムは以下.

  1. C=h^{2p'q'} mod N^2 = (1+N)^a mod N^2 = (1+aN) mod N^2を計算する.
  2. (C-1 mod N^2)/Nが求める値.

なんと, 解けるじゃないか. 昼間は難しそうな気がしたのにな.