数学とコンピュータサイエンスの暗号学の分野では、3つの数値（ x、y、z ）のグループが2つの順列f 0とf 1のクローであると言われるのは、
- f 0 ( x ) = f 1 ( y ) = z です。
クローを計算するための効率的なアルゴリズムが存在しない場合、 順列f 0とf 1のペアはクローフリーであると言われます。
クローフリーという用語は、ゴールドワッサー、ミカリ、リベストが1984年の論文「署名問題に対する逆説的解決」（後に、より完成度の高いジャーナル論文でも発表）で導入した。彼らは、クローフリーのトラップドア順列のペアが存在するということは、適応型選択メッセージ攻撃に対して安全なデジタル署名方式が存在することを意味することを示した。[1] [2]この構成は後に、任意の一方向トラップドア順列からデジタル署名を構成することに取って代わられた。[3]トラップドア順列 の存在は、それ自体ではクローフリー順列が存在することを意味するわけではない。[4]しかし、因数分解が困難な場合にはクローフリー順列が存在することが示されている。[5]
クローフリー順列（必ずしもトラップドアではない）の一般的な概念は、イヴァン・ダムゴードによって博士論文「クローフリー関数の暗号への応用」 （オーフス大学、1988年）でさらに研究され、クローフリー順列から衝突耐性ハッシュ関数を構築する方法を示しました 。[5] クローフリーの概念は、ハッシュ関数における衝突耐性の概念と密接に関連しています。違いは、クローフリー順列は、それらの間で衝突を起こすのが難しい関数のペアであるのに対し、衝突耐性ハッシュ関数は、衝突を見つけることが難しい単一の関数であるということです。つまり、関数Hは、異なる値x、yのペアを見つけるのが困難で、
- H ( x ) = H ( y ) です。
ハッシュ関数の文献では、これは一般的にハッシュ衝突と呼ばれます。衝突を見つけるのが難しいハッシュ関数は、衝突耐性があると言われます。
ビットコミットメント
クローフリー順列のペアf 0とf 1が与えられれば、コミットメントスキームを作成するのは簡単です。ビットbにコミットするために、送信者はランダムなxを選択し、f b ( x ) を計算します。f 0とf 1 はどちらも同じドメイン（および値域）を共有するため、ビットbは受信者から統計的に隠されています。コミットメントを開くには、送信者はランダム性x を受信者に送信するだけです。1 − bへのコミットメントを開くことはクローを見つけることとまったく同じであるため、送信者は自分のビットに拘束されます 。衝突耐性ハッシュ関数の構築と同様に、この構築ではクローフリー関数にトラップドアが必要ないことに注意してください。
参考文献
- ^ Goldwasser, Shafi ; Micali, Silvio ; Rivest, Ronald L. (1984). 「署名問題に対する逆説的な解決法」. Proceedings of FOCS (PDF) . pp. 441– 448.
- ^ Goldwasser, Shafi ; Micali, Silvio ; Rivest, Ronald L. (1988年4月). 「適応型選択メッセージ攻撃に対する安全なデジタル署名方式」. SIAM J. Comput . 17 (2): 281– 308. CiteSeerX 10.1.1.20.8353 . doi :10.1137/0217017.
- ^ Bellare, Mihir ; Micali, Silvio (1992). 「任意のトラップドア順列が与えられた場合の署名方法」. Journal of the ACM . 39 : 214–233 . doi : 10.1145/147508.147537 . hdl : 1721.1/149163 . S2CID 628275.
- ^ Dodis, Yevgeniy; Reyzin, Leonid (2002). 「Claw-Free Permutations の力について」: 55–73 . CiteSeerX 10.1.1.19.6331 .
{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です - ^ ab Damgård, Ivan Bjerre (1988). 「衝突のないハッシュ関数と公開鍵署名方式」. Advances in Cryptology – EUROCRYPT' 87 . Lecture Notes in Computer Science. Vol. 304. Springer. pp. 203– 216. doi : 10.1007/3-540-39118-5_19 .
さらに読む
- 小柴健 (1996). 「自己定義可能なクローフリー関数」
