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

18:59, 2 March 2009版から

Blum-Goldwasser (BG) 暗号は, Manuel BlumとShafi Goldwasserによって1984年に提案された公開鍵暗号方式である. BG暗号は確率的暗号であり, ...安全である. また, 暗号文と平文の比は定数である. ?BBS擬似乱数生成器を用いて鍵ストリームを生成し, その鍵ストリームと平文のXORを取ることで暗号化される. 復号は, BBS擬似乱数生成器の最終状態を秘密鍵を用いて操作することで行われる. これにより, 初期状態が計算でき鍵ストリームを再構成できる.

The Blum-Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum-Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum Blum Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the secret key, in order to find the initial seed and reconstruct the keystream.

BG暗号は, 素因数分解の不可能性を仮定することで強秘匿性および識別不可能性を証明できる. 具体的には, $p,q$が十分大きな素数であるような合成数$N=pq$の素因数分解である. BG暗号には, Goldwasser-Micali暗号のような初期の確立的暗号に比べいくつかの利点がある. 第一にその安全性は素因数分解にのみ帰着され, 他の仮定 (QR仮定やRSA仮定) を必要としない. 第二に, BG暗号は効率が良い... また, BG暗号は計算の効率もRSA暗号と比較可能であるほど良い (ただしBG暗号のメッセージの長さおよびRSAの指数の長さによる). 以上の利点はあるが, BG暗号は適応的選択暗号文攻撃に非常に弱い (下記を参照のこと).

The BG cryptosystem is semantically secure based on the assumed intractability of integer factorization; specifically, factoring a composite value $N=pq$ where $p,q$ are large primes. BG has multiple advantages over earlier probabilistic encryption schemes such as the Goldwasser-Micali cryptosystem. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e.g., hardness of the quadratic residuosity problem or the RSA problem). Secondly, BG is efficient in terms of storage, inducing a constant-size ciphertext expansion regardless of message length. BG is also relatively efficient in terms of computation, and fairs well even in comparison with cryptosystems such as RSA (depending on message length and exponent choices). However, BG is highly vulnerable to adaptive chosen ciphertext attacks (see below).

暗号化が確率的に行われるため, 入力である平文を固定しても暗号化の度に異なった暗号文が生成される. これは, 敵が辞書攻撃を行うこと (すなわち既知の暗号文と平文のペアと比べることによって盗聴した暗号文を解読すること) を防ぐという点で, 非常に重要である.

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.

暗号方式

おっとダメなのか. Note that the following description is a draft, and may contain errors!

Blum-Goldwasser暗号は3つ組のアルゴリズムからなる. 公開鍵と秘密鍵のペアを確率的に生成する鍵生成アルゴリズム, 確率的な暗号化アルゴリズム, および決定性の復号アルゴリズムである.

Blum-Goldwasser 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.

鍵生成

Blum-Goldwasser暗号では, Blum数が用いられる. これは復号のためである. Blum数はRSAモジュールと同様に生成されるが, 素数$p,q$は法4の下で3と合同でなければならない.

1. アリスは2つの大きな素数$p$と$q$を独立にランダムに選ぶ. ただし, $p\neq q$かつ$(p,q)\equiv 3{\bmod {4}}$でなければならない.
2. アリスは$N=pq$を計算する.

公開鍵は$N$, 秘密鍵はその素因数分解$(p,q)$である.

To allow for decryption, the modulus used in Blum-Goldwasser encryption should be a Blum integer. This value is generated in the same manner as an RSA modulus, except that the prime factors $(p,q)$ must be congruent to 3 mod 4. (See RSA, key generation for details.)

1. Alice generates two large prime numbers $p\,$ and $q\,$ such that $p\neq q$, randomly and independently of each other, where $(p,q)\equiv 3$ mod $4$.
2. Alice computes $N=pq$.

The public key is $N$. The secret key is the factorization $(p,q)$.

暗号化

ボブが$L$ビットの平文$(m_{0},\dots ,m_{L-1})$を暗号化してアリスに送りたいとする. Suppose Bob wishes to send a message m to Alice:

1. ボブは$r$をランダムに$1<r<N$の範囲から選び, $x_{0}=r^{2}{\bmod {N}}$とする.
2. ボブはBBS擬似乱数生成器を用い, $L$ビットの鍵ストリーム$(b_{0},\dots ,b_{L-1})$を得る.
   1. $i=0,\dots ,L-1$について以下を繰り返す.
   2. $b_{i}$を$x_{i}$の最下位ビットとする.
   3. $i$を1増やす.
   4. $x_{i}=(x_{i-1})^{2}{\bmod {N}}$を計算する.
3. 鍵ストリームと平文のXORを取ることで暗号分を得る. すなわち, ${\vec {c}}={\vec {m}}\oplus {\vec {b}}$を計算する.
4. さらに, $y=x_{0}^{2^{L}}=x_{L-1}^{2}{\bmod {N}}$を計算する.

1. Bob first encodes $m$ as a string of $L$ bits $(m_{0},\dots ,m_{L-1})$.
2. Bob selects a random element $r$, where $1<r<N$, and computes $x_{0}=r^{2}~mod~N$.
3. Bob uses the BBS pseudo-random number generator to generate $L$ random bits $(b_{0},\dots ,b_{L-1})$ (the keystream), as follows:
   1. For $i=0$ to $L-1$:
   2. Set $b_{i}$ equal to the least-significant bit of $x_{i}$.
   3. Increment $i$.
   4. Compute $x_{i}=(x_{i-1})^{2}~mod~N$.
4. Compute the ciphertext by XORing the plaintext bits with the keystream: ${\vec {c}}={\vec {m}}\oplus {\vec {b}},y=x_{0}^{2^{L}}~mod~N$.

ボブは暗号文として$(c_{0},\dots ,c_{L-1})$と$y$を送信する.

Bob sends the ciphertext $(c_{0},\dots ,c_{L-1}),y$.

To improve performance, the BBS generator can securely output up to $O(loglogN)$ of the least-significant bits of $x_{i}$ during each round. See Blum Blum Shub for details.

復号

アリスが暗号文$(c_{0},\dots ,c_{L-1}),y$を受け取ったとする. 以下の手続きによりアリスは$m$を復元する.

Alice receives $(c_{0},\dots ,c_{L-1}),y$. She can recover $m$ using the following procedure:

1. アリスは$y$の法$N$の下での$2^{L}$乗根$r$を求める.
   1. $r_{p}=y^{(2^{L})^{-1}}=y^{((p+1)/4)^{L}}{\bmod {p}}$と$r_{q}=y^{((q+1)/4)^{L}}{\bmod {q}}$を計算する.
   2. 中国式剰余定理より$r$を求める.
      1. ...?
2. $x_{0}$から${\vec {b}}$をBBS擬似乱数生成器を用いて求める.
3. 暗号文${\vec {c}}$と鍵ストリームのXORを取ることで平文を求める. すなわち, ${\vec {m}}={\vec {c}}\oplus {\vec {b}}$.

1. Using the prime factorization $(p,q)$, Alice computes $r_{p}=y^{((p+1)/4)^{L}}~mod~p$ and $r_{q}=y^{((q+1)/4)^{L}}~mod~q$.
2. Compute the initial seed $x_{0}=q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q}~{mod}~N$
3. From $x_{0}$, recompute the bit-vector ${\vec {b}}$ using the BBS generator, as in the encryption algorithm.
4. Compute the plaintext by XORing the keystream with the ciphertext: ${\vec {m}}={\vec {c}}\oplus {\vec {b}}$.

Alice recovers the plaintext $m=(m_{0},\dots ,m_{L-1})$.

安全性および効率

BG暗号の強秘匿性は, BBS擬似乱数生成器の最終状態$y$と公開鍵$N$を用いたとしても鍵ストリームと一様乱数の区別がつかないことにもとづく. しかし, $({\vec {c}},y)$という暗号文は適応的選択暗号文攻撃に弱い. 適応的選択暗号文攻撃では, 敵は復号オラクルにクエリすることで$({\vec {a}},y)$という暗号文の平文${\vec {m}}'$を求めることが出来る. この場合, 元々の暗号文の平文${\vec {m}}$は${\vec {a}}\oplus {\vec {m}}'\oplus {\vec {c}}$として求められる.

The Blum-Goldwasser scheme is semantically-secure based on the hardness of predicting the keystream bits given only the final BBS state $y$ and the public key $N$. However, ciphertexts of the form ${\vec {c}},y$ are vulnerable to an adaptive chosen ciphertext attack in which the adversary requests the decryption $m^{\prime }$ of a chosen ciphertext ${\vec {a}},y$. The decryption $m$ of the original ciphertext can be computed as ${\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}$.

BG暗号は平文のサイズによって効率が変化する. RSA暗号では, ...

Depending on plaintext size, BG may be more or less computationally expensive than RSA. Because most RSA deployments use a fixed encryption exponent optimized to minimize encryption time, RSA encryption will typically outperform BG for all but the shortest messages. However, as the RSA decryption exponent is randomly distributed, modular exponentiation may require a comparable number of squarings/multiplications to BG decryption for a ciphertext of the same length. BG has the advantage of scaling more efficiently to longer ciphertexts, where RSA requires multiple separate encryptions. In these cases, BG may be significantly more efficient.

References

1. M. Blum, S. Goldwasser, "An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information", Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.
2. Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7

External links

• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8