GGH 暗号方式のソースを表示

{{翻訳直後|[[:en:Special:Permalink/696083391|en:GGH_encryption_scheme]]|date=2016年8月}}
'''Goldreich–Goldwasser–Halevi (GGH)''' [[格子暗号]]方式とは、[[格子 (数学)|格子]]に基づく[[公開鍵暗号|非対称]]方式のひとつである。{{仮リンク|GGH 署名方式|en|GGH signature scheme}}も存在する。

Goldreich–Goldwasser–Halevi (GGH) 暗号方式では、{{仮リンク|格子問題|label=最近ベクトル問題|en|Lattice problems}}の困難性を利用している。格子基底縮小の難しさに依存する落とし戸付き一方向関数を用いており、1997年に {{仮リンク|オデ・ゴールドライヒ|en|Oded Goldreich|label=Oded Goldreich}}, [[シャフィ・ゴールドワッサー|Shafi Goldwasser]], {{仮リンク|シャイ・ハレヴィ|en|Shai Halevi|label=Shai Halevi}} により発表された。この一方向性関数は、格子の基底が与えられたときに格子点の近くのベクトルを生成するのは簡単だが（例えば格子点を選んで小さな誤差ベクトルを足せばよい）、この誤差を含んだベクトルから元の格子点を得るには特別な基底が必要である、というアイデアに基づいている。

GGH 暗号は Phong Q. Nguyen により1999年に暗号解読された。

== 暗号方式 ==
=== 鍵生成 === 
GGH 暗号では、次の秘密鍵と公開鍵を用いる。

秘密鍵は，格子  <math>L</math> の"良い性質を持つ"基底 <math>B</math> と、[[ユニモジュラ行列]]  <math>U</math> である。"良い性質"とは、基底が短く、{{仮リンク|格子簡約#ほとんど直交|label=ほとんど直交|en|Lattice reduction#Nearly Orthogonal}}しているなどの性質である。

公開鍵は、格子 {{Mvar|L}} の別の基底 <math>B' = UB</math> である。

=== 暗号化 ===
平文空間は一定の {{Mvar|M}} に対して {{Math|&minus;''M'' < ''λ<sub>i</sub>'' < ''M''}} を満たす整数ベクトル {{Math|(''λ''<sub>1</sub>, ..., ''λ<sub>n</sub>'')}} である。

平文が {{Math|1=''m'' = (''λ''<sub>1</sub>, ..., ''λ<sub>n</sub>'')}} 、公開鍵が <math>B' =(b'_1,\ldots,b'_n)</math> であるとき、まず次のように計算する。
: <math>v = \sum \lambda_i b_i'</math>
これは行列記法を使えば以下のように書ける。
: <math>v=m\cdot B'</math>
<math>m</math> が整数値からなり、各 <math>b'_i</math> が格子点であるから、 <math>v</math> も格子点となる。次に、小さな誤差ベクトル  <math>e</math> を選び、暗号文は次のように計算される。
: <math>c=v+e=m \cdot B' + e</math>

=== 復号 ===
暗号文を復号するには、次のように計算する。
: <math> c \cdot B^{-1} = (m\cdot B^\prime +e)B^{-1} = m\cdot U\cdot B\cdot B^{-1} + e\cdot B^{-1} = m\cdot U + e\cdot B^{-1}</math>
<math>e \cdot B^{-1}</math> が十分に小さいならば、Babai 丸め法を用いることでこの項を除去することができる。最終的に次のように平文を計算できる。
: <math> m = m \cdot U \cdot U^{-1} </math>

== 例 ==
{{Math|''L'' &sub; &#x211d;<sup>2</sup>}} を、以下のような基底 {{Mvar|B}} とその逆 {{Math|''B''{{sup|&minus;1}}}} をもつ格子とする。
: <math> B=  \begin{pmatrix}
 7 & 0 \\ 0 & 3 \\      
     \end{pmatrix}</math>, <math>B^{-1}=  \begin{pmatrix}
 \frac{1}{7} & 0 \\ 0 & \frac{1}{3} \\      
     \end{pmatrix}</math>
くわえて、
: <math>U = \begin{pmatrix}
         2 & 3 \\ 3 &5\\
        \end{pmatrix}</math> および
: <math>U^{-1} = \begin{pmatrix}
         5 & -3 \\ -3 &2\\
        \end{pmatrix}</math>
とすると、以下を得る。
: <math>B' = U B = \begin{pmatrix}
            14 & 9 \\ 21 & 15 \\
           \end{pmatrix}</math>
平文を {{Math|1=''m'' = (3, &minus;7)}} とし、誤差を {{Math|1=''e'' = (1, &minus;1)}} とすると、以下のように暗号文を得る。
: <math>c = m B'+e=(-104, -79)</math>
これを復号するには、次の計算を行う。
: <math>c B^{-1} = \left( \frac{-104}{7}, \frac{-79}{3}\right)</math>
これを丸めると {{Math|(&minus;15, &minus;26)}} が得られ、次のように平文を得ることができる。
: <math>m= (-15, -26) U^{-1} = (3, -7)</math>

== 方式の安全性 ==
1999年、Nguyen は国際会議 Crypto にて GGH 暗号方式には方式設計上の欠陥があることを示した。暗号文から平文の一部が漏れること、および、GGH暗号の復号問題が、一般の最近ベクトル問題よりも格段に容易な特別の最近ベクトル問題に帰着できることが示された。

== 参照文献 ==
* Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
* Phong Q. Nguyen. [http://www.di.ens.fr/~pnguyen/pub_Ng99.htm Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97]. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.

{{デフォルトソート:GGH あんこうほうしき}}
[[Category:格子暗号]]