聖杯を求めて

暗号業界では環準同型性を持つ公開鍵暗号があるかどうかが長年の疑問. RSA暗号だとかElGamal暗号だとかは積の準同型性を持つ. 暗号加法的準同型性を持つものはOkamoto-Uchiyama暗号やPaillier暗号などがあり, どちらも適当な仮定を置くことで安全性が言える. あと格子暗号は平文空間が狭いという難点があるものの擬似的な加法的準同型性を持つ (何回も足すと平文が入れ替わる現象がおき得る).
加法的準同型性を持ちつつ1回掛け算出来るのが, Boneh-Goh-Nissim暗号 (TCC 2005). 位数がpqの群とペアリングを使っている点がポイント.

ここまでが前置き.
Cryptology ePrint Archive: Report 2008/378 - C. Aguilar Melchor, P. Gaborit, J. Herranz “Additive Homomorphic Encryption with t-Operand Multiplications”
Cryptology ePrint Archiveに出た論文.
BGN暗号とは別の手法で2回以上掛け算する方法を提案している (らしい). 元となる暗号系としては, Paillier暗号とBGN暗号, あと格子暗号 (Regev04とAjtai05).
Peikert, Vaikuntanathan, Waters (CRYPTO 2008) の方法でRegev05暗号を複数ビット化するのはダメで, Kawachi, Tanaka, Xagawa (PKC 2007) の方法でRegev04とAjtai05を複数ビット化していないとダメらしい.
相当強引な方法を使っているようなので, あとでちゃんと読む.

なぜかRegev05はダメらしい. するとPVW08の複数ビット化のほうもダメだろうねぇ. 中に出ているのだと, 複数ビット化されたRegev04とPaillierを組み合わせている, って仮定増えとるやん(;´Д｀)

昔の記憶を引っ張り出して考えるに, 複数ビット化したRegev05も暗号化関数が(Z_p,+)→(Z_q,+)^{n+1}で, 線形性があるのでいける筈だね. L-pseudo-homomorphismのLはKTX07の方法で見積もれる. PVW08の方法で暗号化関数を(Z_p,+)^l→(Z_q,+)^{n+l}に変えたものも線形性は保たれる. まぁ, L-pseudo-homomorphismのLの見積もりはKTX07の計算に一手間掛けるだけでいけるだろう.
掛け算の方は成分毎に掛け算するのを考えればうまくいくかね?