準同型性を持つ1ビット暗号があるとする (例:Goldwasser-Micali暗号). k個繋げたもの全体を1つの暗号方式と捉えると, 平文空間は{Z_2}^kに拡張されている. k個繋げても, ({Z_2}^k, +) (+はビット毎の足し算) の上で準同型性が成り立つ. さて, (Z_{2^k},+)と(…