修正Elgamal暗号はElgamal暗号を加法に対して準同型性を持つように修正を加えたものです。修正Elgamal暗号について以下のサイトがとても参考になりました！

これに更に修正を加えることで、2-ouf-of-2のしきい値 Elgamal暗号を構成することができます。

鍵生成ここで $tsk=tsk _ 1 + tsk _ 2,tpk=tpk _ 1 \cdot tpk _ 2$ とする。

$P _ 1$ は次のように鍵を生成する。

$tpk _ 1 = g ^ {tsk _ 1}$

$P _ 2$ は次のように鍵を生成する。

$tpk _ 2 = g ^ {tsk _ 2}$

暗号化

$m\in Z _ q$ について暗号文は $ct=(g ^ r ,tpk ^ r \cdot g ^m)=(u,e)$ とする。

復号

$P _ 1$ が、 $ct'=(u,e'=\frac{e}{u ^ {tpk _ 1}})$ を半分復号する。 $P _ 2$ が、 $m=log _ g \frac{e'}{u ^ {tpk _ 2}}$ で復号を完了する。

$log _ g \frac{e'}{u ^ {tpk _ 2}}=log _ g \frac{\frac{e}{u ^ {tpk _ 1}}}{u ^ {tpk _ 2}}=log _ g \frac{e}{u ^ {tpk _ 1 \cdot tpk _ 2}}=log _ g \frac{tpk ^ r \cdot g ^ m}{g ^ {r \cdot (tsk _ 1 + tsk _ 2)}}=log _ g \frac{g ^ {r \cdot tsk} \cdot g ^ m}{g ^ {r \cdot tsk}}=log _ g g ^m = m$