利用者:Roget/試訳/Goldwasser-Micali暗号

http://en-two.iwiki.icu/w/index.php?title=Goldwasser-Micali_cryptosystem&oldid=274489440
- en:Goldwasser-Micali Cryptosystem (18:48, 2 March 2009)

Goldwasser-Micali暗号はen:Shafi Goldwasserとen:Silvio Micaliによって1982年に提案された公開鍵暗号方式である。この暗号方式は標準的な仮定の下安全性が示された初の確率的公開鍵暗号方式である。しかし、効率は悪く、暗号文のサイズは平文のサイズの数百倍になる。暗号方式の安全性を示すために彼女らは、現在では広く使われることになった強秘匿性を定義した。

The Goldwasser-Micali cryptosystem (GM) is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as ciphertexts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely-used definition of semantic security.

　

N=pq型の平方剰余判定問題の不可能性を仮定するとGM暗号は強秘匿性を持つ. pとqを大きな素数とし, N=pqとする. この仮定は, xの法Nでのヤコビ記号が+1であるとき, (x, N)を与えられ, xが法Nでの平方剰余かどうか決定することが難しいという仮定である (すなわち, x= $y^{2}{\bmod {N}}$ なるyが存在するかどうか). Nの素因数分解を知っていれば, 平方剰余判定問題は簡単である. 一方, 平方剰余自体はNの素因数分解を知らなくても誰でも生成できる. GM暗号はこの非対称性を用いて, 暗号化を行っている. すなわち, 平文の各ビットをランダムなヤコビ記号が+1の法Nでの平方剰余か平方非剰余として暗号化する. 受信者はNの素因数を秘密鍵とし, 受け取った暗号文の平方剰余性を確かめることで元の平文に復号する.

GM暗号の暗号文のサイズは, 平文のビット数の|N|倍になる. よって, ciphertext expansionは相当大きい. 素因数分解を用いた攻撃を防ぐためには, |N|は数百ビット以上が推奨される. したがって, この暗号方式は安全性の証明を提供したが, ElGamal暗号のように安全性が証明可能かつ効率のよい暗号方式が提案されている.

暗号化で確率的アルゴリズムを用いるため, 1つの平文に対し非常に沢山の暗号文が生成されうる. これは, たとえば攻撃者が既知の暗号文と比べて平文を推測することを防ぐといったような重要な利点を持つ.

The GM cryptosystem is semantically secure based on the assumed intractability of the quadratic residuosity problem modulo a composite N = pq where p, q are large primes. This assumption states that given (x, N) it is difficult to determine whether x is a quadratic residue modulo N (i.e., x = y² mod N for some y), when the Jacobi symbol for x is +1. The quadratic residue problem is easily solved given the factorization of N, while new quadratic residues may be generated by any party, even without knowledge of this factorization. The GM cryptosystem leverages this asymmetry by encrypting individual plaintext bits as either random quadratic residues or non-residues modulo N, all with quadratic residue symbol +1. Recipients use the factorization of N as a secret key, and decrypt the message by testing the quadratic residuosity of the received ciphertext values.

Because Goldwasser-Micali produces a value of size approximately |N| to encrypt every single bit of a plaintext, GM encryption results in substantial ciphertext expansion. To prevent factorization attacks, it is recommended that |N| be several hundred bits or more. Thus, the scheme serves mainly as a proof of concept, and more efficient provably-secure schemes such as Elgamal have been developed since.

Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different ciphertexts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts.

方式

Goldwasser-Micali暗号は3つのアルゴリズムからなる. 確率的な鍵生成アルゴリズム, 確率的な暗号化アルゴリズム, 決定性の復号アルゴリズムである.

この方式は, Nの素因数分解 (p, q) からxが法Nの元で平方かどうかを決定できることに拠っている. 具体的には以下の手順で決定できる.

$x_{p}=x{\bmod {p}}\,\!$ と $x_{q}=x{\bmod {q}}\,\!$ を計算する.
$x_{p}^{(p-1)/2}\equiv 1{\pmod {p}}$ かつ $x_{q}^{(q-1)/2}\equiv 1{\pmod {q}}$ ならば, xは法Nの下, 平方剰余である.

Goldwasser-Micali consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.

The scheme relies on deciding whether a given value x is a square mod N, given the factorization (p, q) of N. This can be accomplished using the following procedure:

Compute x_p = x mod p, x_q = x mod q.
If $x_{p}^{(p-1)/2}\equiv 1{\pmod {p}}$ and $x_{q}^{(q-1)/2}\equiv 1{\pmod {q}}$ , then x is a quadratic residue mod N.

鍵生成

GM暗号が用いる法は, RSA暗号と同じ方法で構成される.

アリスは2つの大きな素数 p, qを独立にランダムに選ぶ.
アリスはN=p qを計算する.
アリスはルジャンドル記号が $\left({\frac {x}{p}}\right)=\left({\frac {x}{q}}\right)=-1$ となる平方非剰余 x を計算する. このときヤコビ記号 $\left({\frac {x}{N}}\right)=+1$ である. このxはランダムな値を選び2つのルジャンドル記号をテストすることで得られる. もしpもqも4を法として3と合同ならば (すなわちNがブラム数ならば), N-1はこの性質を満たしている.

公開鍵は(x,N)である. 秘密鍵は(p,q)である.

The modulus used in GM encryption is generated in the same manner as in the RSA cryptosystem. (See RSA, key generation for details.)

Alice generates two distinct large prime numbers p and q, randomly and independently of each other.
Alice computes N = p q.
She then finds some non-residue x such that the Legendre symbols satisfy $\left({\frac {x}{p}}\right)=\left({\frac {x}{q}}\right)=-1$ and hence the Jacobi symbol $\left({\frac {x}{N}}\right)$ is +1. The value x can for example be found by selecting random values and testing the two Legendre symbols. If (p, q) = 3 mod 4 (i.e., N is a Blum integer), then the value N-1 is guaranteed to have the required property.

The public key consists of (x, N). The secret key is the factorization (p, q).

暗号化

ボブがmをアリスに送るとする.

ボブはmをビット列 $(m_{1},\ldots ,m_{n})$ に符号化する.
各ビット $m_{i}$ について, ランダムな値yを $(\mathbb {Z} /N)^{\times }$ から生成し, $c_{i}=y^{2}x^{m_{i}}{\bmod {N}}$ を計算する.

暗号文は $(c_{1},\ldots ,c_{n})$ である.

Suppose Bob wishes to send a message m to Alice:

Bob first encodes m as a string of bits (m₁, ..., m_n).
For every bit m_i, Bob generates a random value y less than N. He outputs the value $c_{i}=y^{2}x^{m_{i}}$ mod N.

Bob sends the ciphertext (c₁, ... , c_n).

復号

アリスが $(c_{1},\ldots ,c_{n})$ を受け取ったとする.

各iについて, 素因数(p,q)を用いて, $c_{i}$ が平方剰余かどうかを決定する. もし平方剰余ならば, $m_{i}=0$ とし, そうでないならば, $m_{i}=1$ とする.

復号された平文は $m=(m_{1},\ldots ,m_{n})$ である.

Alice receives (c₁, ... , c_n). She can recover m using the following procedure:

For each i, using the prime factorization (p, q), Alice determines whether the value c_i is a quadratic residue; if so, m_i = 0, otherwise m_i = 1.

Alice outputs the message m = (m₁, ... , m_n).

安全性

帰着はシンプルである. 暗号方式を破る敵が存在するならば法Nの下でヤコビ記号が+1のランダムな整数を平方剰余かどうか判定できる. アルゴリズムAが0の暗号文と1の暗号文を識別できるとする. 与えられたxが法Nの下で平方剰余かどうか判定するには, Aが公開鍵(x,N)を用いた暗号方式を破れるかどうかを調べる. もし, xが平方非剰余ならば, Aは正しく動作し, 暗号方式を破る. しかし, xが平方剰余ならば, 任意の"暗号文"はランダムな平方剰余になる. したがって, Aは確率1/2でのみ正しく動作する (?). さらに, ランダム自己帰着性から, 与えられたNについて...

GM暗号は準同型性を持つ. もし $c_{0},c_{1}$ が $m_{0},m_{1}$ の暗号文ならば, $c_{0}c_{1}\,{\bmod {N}}$ は, $m_{0}\oplus m_{1}$ の暗号文である. この性質により, GM暗号は他の複雑な暗号方式を構成するのに用いられる.

There is a simple reduction from breaking this cryptosystem to the problem of determining whether a random value modulo N with Jacobi symbol +1 is a quadratic residue. If an algorithm A breaks the cryptosystem, then to determine if a given value x is a quadratic residue modulo N, we test A to see if it can break the cryptosystem using (x,N) as a public key. If x is a non-residue, then A should work properly. However, if x is a residue, then every "ciphertext" will simply be a random quadratic residue, so A cannot be correct more than half of the time. Furthermore, this problem is random self-reducible, which ensures that for a given N, every public key is just as secure as every other public key.

The GM cryptosystem has homomorphic properties, in the sense that if c₀, c₁ are the encryptions of bits m₀, m₁, then c₀c₁ mod N will be an encryption of $m_{0}\oplus m_{1}$ . For this reason, the GM cryptosystem is sometimes used in more complex cryptographic primitives.

参考文献

Shafi Goldwasser and Silvio Micali. Probabilistic Encryption. Journal of Computer and System Sciences (JCSS), 28(2):270-299, April 1984. Preliminary version in: 14th Annual ACM Symposium on Theory of Computing (STOC)

方式

鍵生成

暗号化

復号

安全性

参考文献

関連