WB43とHalevi-Micali string commitment scheme
WB43
日記で書くのは2回目か. 今回はRabin暗号→Rabin/Williams暗号へ向けての布石として平方剰余とルジャンドル記号らしい.
この定理により、ラグランジュ記号の分子を分母で割った余りに置き換えても
これをラグランジュ記号を使えば、次のように表記できる。
次に、ラグランジュ記号の乗法性について見てみる。
と一部に誤記が見られました.
なぜここで書いているかというと, プロクシ規制で掲示板に書けないからです.
Halevi-Micali string commitment scheme
Statistically-hiding computationally-bindingなストリングコミットメントについての話.
Halevi-Micaliコミットメントとほとんど同じものが1993年にDamgård, Pedersen, Phitzmann (CRYPTO 1993, IEEE Trans. on IT 1997, J. Crypt. 1998) によって提案されています. (1997版で知った.)
Halevi-Micaliのscheme 1
Damgård-Pedersen-Phitzmann
CRYPTO 1993版の4章にNaor-YungのCRHFsからのビットコミットメントの改良として載っている.
- パラメータ
- n:メッセージ長
- k:セキュリティパラメータ
- L = 2k+t
- H = {h:{0,1}^{L}→{0,1}^{k}}
- F = {f:{0,1}^{L}→{0,1}^{n}} (ユニバーサルハッシュ関数の族)
- Initialization Phase
- 受信者はhをHからランダムに選んでAに送る
- Commitment Phase
- nビットのメッセージmについて
- Lビットの乱数rを選ぶ
- fをFからランダムに選ぶ
- y=h(r)を計算する
- c=m XOR f(r)を計算する
- (f,y,c)をコミットメントとして送る
- Reveal Phase
- 送信者はmとrを送る
- 受信者はy=h(r)かつc=m XOR f(r)であることを確認