PI-SCA関連知識メモ - 暗号勉強会

Computional q-DHI 問題
Re-randomize
Camenish-Shoup（CS）暗号
exponential Elgamal
Fiat-shamir ヒューリスティック
Range proof

以下の記事のPI-SCAで使用されている知識に関して紹介する

tenn.hateblo.jp

Computional q-DHI 問題

$(g,g ^ \alpha,\dots,g ^ {\alpha ^ q})$ が与えられた時に $g ^ {1/\alpha}$ を計算する問題。ここで $\alpha \in \mathbb{Z _ p ^ *}$ かつ、 $g$ を位数 $p$ の群 $\mathbb{G}$ の生成元とする。

Re-randomize

暗号文を平文を変えずに変更する手法。暗号の内部では乱数が用いられているが、これを変換することで別の暗号文を作り出す。シャッフルと合わせることで平文と暗号文の対応関係がわからないようにする。

例実際に論文でも使われているElgamal暗号での例を紹介する。Elgamal暗号文 $ct = (c _ 1, c _ 2)$ は $ct’=(c _ 1\cdot g ^ r,c _ 2 \cdot h ^ r)$ のようにre-randomizeできる。式を調べると $ct’=(c _ 1,c _ 2)=(g ^ t \cdot g ^ r,h ^ t \cdot m \cdot h ^ r)$ なので、 $\mathbb{Z} _ q$ の乱数 $t$ と $r$ から新しい乱数を作り出し、re-randomizeできる。

Camenish-Shoup（CS）暗号

加法準同型性を持ち、paillier暗号と同様の仮定に基づいておりVerifiable EncryptionとVerifiable Encryptionができるスキームである。Verifiable EncryptionとVerifiable Decryptionは、平文の情報を漏らさずに平文の知識を証明できる暗号方式である。Proover が暗号化する場合を、Verifiable Encryptionといい、復号する場合はVerifiable Decryptionという。DCR仮定とハッシュ関数の衝突困難性のもと、適応的選択暗号文攻撃に対して安全である。

原論文 Practical Verifiable Encryption and Decryption of Discrete Logarithms

exponential Elgamal

2-out-of-2のしきい値暗号方式として利用する加法準同型性を持った暗号である。ローカルで鍵のシェアを生成し、秘密鍵がそれらの和となるように設定する。なお、乗法準同型性を持つ通常のElgamal暗号もシャッフルプロトコルで使用する。

Fiat-shamir ヒューリスティック

honest-verifier zero-knowledge プロトコルをnon-interactiveプロトコルに変換する手法である。Fiat-shamir ヒューリスティックはΣプロトコルをnon-interactiveにできる。具体的には、ハッシュ関数を使うことでmove2のチャレンジ生成をverifierなしで行う。これによってチャレンジの到着を待つ必要がなくなりnon-interactiveになる。得られたnon-interactiveなプロトコルはROMのもとMalicious Securityが保証される。

Range proof

あるコミットメントに対し、コミットメントがある値の範囲にはいっていることが証明できる。