ランダム性抽出器の動機づけ

私は数学のマスターの学生で、有限体Kickyaの推測のような有限体の幾何学の結果が無作為抽出器にどのように適用されるかを調べています。私はコンピュータ科学者ではなく、私は自分の深みから多少外れていることを認めなければなりません。

私が読んだことから、ランダム性エクストラクタは関数です:

$ E: {0,1 } ^ n times {0,1 } ^ d rightarrow {0,1 } ^
m $

最小のエントロピー$ k $と$ Y $( “真のランダムシード”)を持つ$ {0,1 } ^ n
$の分布すべてに対して、$ {0,1 } ^ $ {0,1 } ^ m $の一様分布に対して$ E(X、Y)$を$
ε$とする。

私は真にランダムなビットを生成する動機づけを理解していますが、既に本当にランダムなシードが必要な場合は、抽出子の概念がどのように役立つのか理解していません。確かに、本当にランダムな種を作り出すことができれば、本当にランダムなビットを生成するという問題をすでに解決していますか?

また、暗号やコーディング理論などの領域でエクストラクタを明示的に使用する例はありますか?

ベストアンサー

ここでは$ d ll m
$があります。つまり、少しばかりのランダム性から始めます。だから、それは「種」と呼ばれています。あなたが始めるには小さいものが必要ですが、あなたは巨大で美しい無秩序の樹木で終わります。

もう1つのことは、均等に分散されたビットが高品質のランダム性であるのに対し、最小エントロピー$ k
$のビットは低品質のランダム性であるということです。そのため、抽出者は次のように述べています。少し高品質のものから始め、低品質のものをたくさん作成すると、多くの高品質なものを生成できます。それは、少なくとも理論的には、潜在的に有用と思われる。

暗号技術者は実際にそれらを使用しますか?まあ、彼らは正直言って、開業医は通常そうではありません。代わりに、彼らはしばしばハッシュ関数を使用します(暗黙的に何らかのランダムなOracleの仮定を適用します)。それは原理的なものではない

抽出器を使用することは、より強力で証明可能な保証につながるだろうが、それはいくぶん類似している。あなたは抽出器をこのような事柄のための堅実な理論的基礎を提供するものとして見ることができます。彼らはまた、ここで要約しようとはしない複雑さ
– 理論的結果の様々な重要な意味を持っているので、抜粋は確かに興味深いです。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です