Σ Hash = Cameleon Hash

Cryptology ePrint Archive: Report 2008/379 - M. Bellare, T. Ristov “Hash Functions from Sigma Protocols and Improvements to VSH”
今度のASIACRYPT 2008に出る論文.
(a,c,z)をΣプロトコルの通信履歴とする. Damgård (CRYPTO '89) とCramer, Damgård, Mckenzie (PKC 2002) でΣプロトコルから落とし戸付きコミットメントができることが分かっている. 直観的にはskがあると, aを一致させたまま, (c,z)を変えることが出来る. なのでコミットメントとしてa, コミットメントを明かすときには(c,z)を送る. コミットメントの検証はΣプロトコルの検証者を用いて行う. skを持たずに2通りに開けられるならΣプロトコルの健全性に反する. 一方, コミットメントの秘匿性はΣプロトコルのHVZK性によると.
これは非常にカメレオンハッシュに近い.
そこで, これをちゃんとしたハッシュにするために, この論文ではΣプロトコルの性質を1つ定義している. このプロトコルがStrongHVZKであるとは, (1) cをランダムに選んで, (2) zをランダムに選んで, (3) aを決定性アルゴリズムStSim(pk,c,z)で計算したときに, (a,c,z)が正しい通信履歴と完全に一致するということ. (たぶん統計的でも良い.)
すると検証がStSim(pk,c,z)=aかどうかで行えると. これにより, StSim(pk,c,z)がpkを鍵とした鍵付きハッシュになるという寸法.
これを適当なプロトコルに適用して, 数論的な仮定から衝突耐性を持つハッシュ関数を構成している.
最後に, Contini, Lenstra, Steinfeldが提案しているVSH (VSSR仮定というのを使うらしい) の改良 VSH* が得られましたという纏め. これらは小さい素数を使うハッシュなので, 他の数論的なハッシュに比べて速いという点が嬉しい様子.