Rosen and Segevの新しいの

Cryptology ePrint Archive: Report 2008/134 - A. Rosen and G. Segev “Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption”

Peikert and Waters (STOC '08, Cryptology ePrint Archive: Report 2007/279)で新しく提唱されたプリミティブとしてLossy TDFがある. これは鍵生成の時にモードが2つある. Injectiveモードだと普通のTDFの記述 (公開鍵) が生成される. Lossyモードだと情報が失われるような関数の記述 (公開鍵モドキ) を生成する. (具体的には値域が平文空間より狭いという定義. 当然, 情報が失われる.) また, 公開鍵と公開鍵モドキは計算量的に区別が付かない. というプリミティブ.
これにより簡単にIND-CPAな暗号系が作れる. これをもう少し弄ってABOTDFを構成できる. また, 安全な使い捨て署名があれば, TDF, ABOTDF, 使い捨て署名を組み合わせてIND-CCAな暗号系が構成できる.

さて, Peikert and WatersではDDH仮定とLWE仮定からIND-CCA PKE w/o ROを構成している. 悲しいかな, 平文空間がnビットの時にn次元の暗号文を要素とした正方行列を使うため効率が悪くなってしまう.

Rosen and Segevの偉い点は, Damgaard-Jurik暗号を上手く使うとLossy TDFになっていると見抜いたところ. しかもPaillier暗号のままではダメという話までついている. たった5ページの論文だがこの着眼点には参った.

具体的な構成は以下.

  • KeyGen
    • nビットのRSAモジュールNとパラメータs
  • Enc
    • メッセージm \in \mathbb{Z}_{N^s}と乱数r \in \mathbb{Z}_{N}^{*}に対して暗号文はE_s(m,r) = (1+N)^m r^{N^s} \bmod{N^{s+1}}.

さて, 1の暗号文を考える. E_s(1,r) = (1+N) r^{N^s} \bmod{N^{s+1}}である. これをm乗するとどうなるか? E_s(1,r)^m = (1+N)^m (r^m)^{N^s} \bmod{N^{s+1}} = E_s(m,r^m)になる.
また, 0の暗号文を考える. すると, E_s(0,r) = r^{N^s}\bmod{N^{s+1}}である. こちらをm乗した場合は, E_s(0,r)^m = (r^m)^{N^s} \bmod{N^{s+1}}=E_s(0,r^m \bmod{N})となる.

従って, Injectiveモードでは(N,s,E_s(1,r))を公開鍵とし, Lossyモードでは(N,s,E_s(0,r))を公開鍵モドキとすれば良い. 二つの見分けが付かないことはDCR仮定から簡単に言える. Lossyモードでの情報の損失量を量る必要があるが, それは簡単. sを3以上にすれば結構な量が失われているのでOK. あとは平文空間やABOTDFを上手く構成すれば宜しい.