双線形写像を用いた暗号方式

双線形写像を用いて暗号方式を構成することを考えてみます。以下の説明ではG₁, G_Tを可換な乗法群としています。簡単のために演算子＊を省略して、f＊gをfgなどと略記することにします。

双線形DH問題

暗号理論で用いられる双線形写像の代表例としては、楕円曲線上で定義されるWeilペアリングやTateペアリングがあります。実際の計算方法は私の手に余りますので省略します。

双線形群（G₁,G_T,e）において、群G₁,G_Tにおいて離散対数問題は難しいものとします。
双線形写像を用いると、g,g^a,g^bからe(g,g)^abが求まります。
双線形群（G₁,G_T,e）において、g,g^a,g^b,g^cからe(g,g)^abcを求める問題を双線形DH問題といいます。
例にあげた双線形写像に対する双線形DH問題は効率的には解けないと考えられています。双線形DH問題が効率的には解けないと考えられている双線形写像eをもつ双線形群（G₁,G_T,e）を用いて暗号方式を構築することを考えていきます。

ElGamal暗号

まず参考のためにDH問題に基づいたElGamal暗号を整理して再度記述します。

【公開鍵】: g,g^a
【受信者の秘密鍵】: a
【暗号化】: 送信者がbを選び、 (g^a)^b = g^ab を求め、平文mに対する暗号文をg^bとmg^abの組 (g^b,mg^ab) とします(mg^abはm＊g^abですが、以下＊はすべて省略することにします)。
【復号化】: 暗号文(g^b,mg^ab)のg^bと秘密鍵aより、 (g^b)^a = g^ab を求め、 mg^ab/g^ab = m と平文mを求めます。

g^aは公開鍵、g^bは暗号文から盗聴者にも手に入りますが、g^abは求められません(DH問題)。
送信者はbを知っており、受信者はaを知っているので、送信者と受信者のみg^abを計算でき、平文mが得られます。

双線形写像を用いた簡易暗号方式1

Elgamal暗号と同様のことを双線形写像を用いて行った場合、

【公開鍵】: e(g,g),e(g,g)^a
【受信者の秘密鍵】: a
【暗号化】: 送信者がbを選び、 (e(g,g)^a)^b = e(g,g)^ab を求め、平文mをG_Tの要素とし、m ∈ G_Tに対する暗号文をe(g,g)^bとme(g,g)^abの組 (e(g,g)^b,me(g,g)^ab) とします。
【復号化】: 暗号文(e(g,g)^b,me(g,g)^ab)のe(g,g)^bと秘密鍵aより、 (e(g,g)^b)^a = e(g,g)^ab を求め、 me(g,g)^ab/ e(g,g)^ab = m と平文mを求めます。

e(g,g)^aは公開鍵、e(g,g)^bは暗号文から盗聴者にも手に入りますが、e(g,g)^abは求められません(DH問題)。
送信者はbを知っており、受信者はaを知っているので、送信者と受信者のみe(g,g)^abを計算でき、平文mが得られるということになります。
しかし、これは双線形写像の性質を利用してはいません。

双線形写像を用いた簡易暗号方式2(失敗例)

双線形写像の性質を利用するため、双線形写像の値ではなく、双線形写像に代入する値を鍵にした形を考えてみます。

【公開鍵】: g,g^a
【受信者の秘密鍵】: a
【暗号化】: 送信者は公開鍵のg,g^aと自分で選んだbを用いて (e(g,g^a))^b = e(g,g)^ab を求め、平文m ∈ G_Tに対する暗号文をe(g,g)^bとme(g,g)^abの組 (g^b,me(g,g)^ab) とします。
【復号化】: 暗号文(g^b,me(g,g)^ab)のg^b、公開鍵gと秘密鍵aより、 (e(g,g^b))^a = e(g,g)^ab を求め、 me(g,g)^ab/ e(g,g)^ab = m と平文mを求めます。

暗号化、復号化のためにe(g,g)^abを双線形写像を用いて計算することにしています。しかし、この場合、g^a,g^bは公開鍵、暗号文から盗聴者にも手に入るため、e(g^a,g^b)=e(g,g)^abが求められてしまい、平文mを盗聴者に知られてしまいます。

双線形写像を用いた簡易暗号方式3

そこで、公開鍵を一つ増やすことにします。

【公開鍵】: g,g^a,g^c
【受信者の秘密鍵】: a
【暗号化】: 送信者は公開鍵のg^a,g^cと自分で選んだbを用いて (e(g^a,g^c))^b = e(g,g)^abc を求め、平文m∈G_Tに対する暗号文をg^bとme(g,g)^abの組 (g^b,me(g,g)^abc) とします。
【復号化】: 暗号文(g^b,me(g,g)^abc)のg^b、公開鍵g^cと秘密鍵aより、 (e(g^c,g^b))^a = e(g,g)^abc を求め、 me(g,g)^abc/ e(g,g)^abc = m と平文mを求めます。

g,g^a,g^cは公開鍵、g^bは暗号文から盗聴者にも手に入りますが、e(g,g)^abcは求められません(双線形DH問題)。
送信者はbを知っており、受信者はaを知っているので、送信者と受信者のみe(g,g)^abcを計算でき、平文mが得られるということになります。
公開鍵を一つ増やしましたが、増やした公開鍵をユーザごとに設定することにより、様々な付加的な機能を追加できる様になります。

双線形写像を用いた簡易暗号方式3の安全性

ElGamal暗号方式の安全性と同じ様に証明してみます。
攻撃者は公開鍵暗号と暗号文を得ることができるとします。
秘密鍵を知らずに簡易暗号方式３を復号することのできる攻撃者がいるとすると双線形DH問題が解けることを示します。
双線形DH問題は効率的には解けない問題であるとしていますので、背理法により、簡易暗号方式３を復号できる攻撃者がいるとすると矛盾が生じることより、このような攻撃者はいないことになります。
双線形DH問題を解こうとしている人をA君とし、簡易暗号方式３を復号することのできる攻撃者をB君とします。

A君には双線形DH問題として、双線形群（G₁,G_T,e）において、原始元g∈G₁とg^a, g^b, g^c (a,b,cは正の整数)が与えられますが、a,b,cは教えてもらえません。A君の目的はe(g,g)^abcを求めることです。
B君は簡易暗号方式３の公開鍵として、双線形群（G₁,G_T,e）におけるG₁の生成元g、g^a,g^c, (a,cは正の整数)を与えられますが、a,cは教えてもらえません。B君は暗号文(g^b,me(g,g)^abc) (bは乱数、m∈G_Tは平文)を与えられますが、乱数bと平文mは教えてもらえません。B君は秘密鍵を知らなくても簡易暗号方式３を復号できるので、mを計算することができてしまいます。
A君はB君に簡易暗号方式３の公開鍵として、双線形DH問題の双線形群（G₁,G_T,e）における原始元g∈Gとg^a, g^cを渡します。このときA君も知らない正の整数aが簡易暗号方式３の秘密鍵aになります。
A君はu = g^bとし、G_Tからランダムに要素vを選び、(u,v)を簡易暗号方式３の暗号文としてB君に渡します。このときA君も知らない正の整数bが簡易暗号方式３の送信者が選んだbと置かれたことになります。
B君はA君に渡された暗号文(u,v)から平文mを求めてA君に渡します。復号の式からmは m = v/ e(g^c,u)^aを満たしていますので、 e(g^c,u)^a = v/m が成り立ちます。
A君はvを知っており、mもB君から渡されているのでe(g^c,u)^a = v/mを計算することができます。このとき e(g^c,u)^a = e(g^c,g^b)^a = g^abc となりますので、A君はv/mを計算することにより双線形DH問題を解いたことになります。