Multi-Collisionに関するバースデイパラドックスについて
スポンサーリンク
概要
- 論文の詳細を見る
ハッシュ関数H:D→R(|R|=n)のmulti-collision(多重衝突)について、従来はQ=n^<(s-1)/s>回のハッシュ計算で確率的に1個のs-collision、すなわちハッシュ値が等しいs個の入力メッセージが見つかるだろうと信じられていた。本論文では、その確率が高々1/s!であり、大きなsに対しては上記の主張が成り立たないことを示す。一方、十分大きなnに対して、(s!)^<1/s>×Q回のハッシュ計算ならばs-collisionが確立1/2で起きることを示す。この確率は、s=2とするとよく知られたバースデイパラドックスとなっているため、本論文はバースデイパラドックスのmulti-collisionへの一般化となっている。
- 社団法人電子情報通信学会の論文
- 2007-05-11
著者
関連論文
- クラウド化するインターネットの倫理について : アクセス制御の視点から(知的財産関係)
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- 検索システムに組込むセキュリティモデルに関して(セキュリティ関係,一般)
- 多様な価値を映し出すクラウドの論理構造 : 自己言及的な社会システムのエージェントの視点から(セキュリティ関係,一般)
- Small secret key attack on Takagi's variant of RSA (part 1) (オフィスインフォメーションシステム)
- Small secret key attack on Takagi's variant of RSA (part 1) (情報セキュリティ)
- 情報流を制御するマルチエージェント・システムの意味論について (技術と社会・倫理)
- 情報流制御によりcovert channelを阻止する倫理的意義について (技術と社会・倫理)
- プッシュ型Webシステムに於ける情報フロー制御の提案 : アプリケーションサーバにおける情報フィルタの実装(知的財産関係)
- 情報流を制御するマルチエージェント・システムの意味論について(システム理論,インターネットと情報倫理教育,一般)
- 情報流制御によりcovert channelを阻止する倫理的意義について(知的財産,一般)
- 情報流を制御するマルチエージェント・システムの意味論について(システム理論,インターネットと情報倫理教育,一般)
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- 情報流を制御する複雑系のエージェント・システム
- 多様な価値を映し出すクラウドの論理構造 : 自己言及的な社会システムのエージェントの視点から(セキュリティ関係,一般)
- 多様な価値を映し出すクラウドの論理構造 : 自己言及的な社会システムのエージェントの視点から(セキュリティ関係,一般)
- クラウドの変動的秩序概念について : コミュニティプロビジョニングの提案(セキュリティと倫理,一般)
- 情報流を制御する複雑系のエージェント・システム
- ソフトウェアによるストリーム暗号の高速実装
- Modular LFSR 型 Filter Generator に対する Fast Correlation Attack
- 検索システムに組込むセキュリティモデルに関して(セキュリティ関係,一般)
- 検索システムに組込むセキュリティモデルに関して(セキュリティ関係,一般)
- ハッシュ関数(HAVAL)に対する衝突攻撃
- Multi-Collisionに関するバースデイパラドックスについて
- 高次SACのベクトル出力ブール関数への拡張
- Lower Bound on the Size of Shares of Nonperfect Secret Sharing Schemes
- Security of the Center in Key Distribution Schemes
- マルチエージェントに基づく遺伝的なアクセス行列制御(知的財産,及び一般)