WB43とHalevi-Micali string commitment scheme

crypt

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
  • パラメータ
    • n:メッセージ長
    • k:セキュリティパラメータ
    • L = 4k+2n+4
    • h:{0,1}^{L}→{0,1}^{k}
    • F = {f:{0,1}^{L}→{0,1}^{n}} (ユニバーサルハッシュ関数の族)
  • Commitment Phase
    1. nビットのメッセージmについて
    2. f(r) = mとなるようなrを{0,1}^LからとfをFから選ぶ
    3. y = h(r)を計算
    4. (f,y)をコミットメントとして送る
  • Reveal Phase
    1. 送信者はmとrを送る
    2. 受信者はy=h(r)かつm=f(r)であることを確認
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
    1. nビットのメッセージmについて
    2. Lビットの乱数rを選ぶ
    3. fをFからランダムに選ぶ
    4. y=h(r)を計算する
    5. c=m XOR f(r)を計算する
    6. (f,y,c)をコミットメントとして送る
  • Reveal Phase
    1. 送信者はmとrを送る
    2. 受信者はy=h(r)かつc=m XOR f(r)であることを確認