弱隨機源之亂度萃取及其應用(I)

Abstract

本計劃為期三年， 主要目的為建造. 雙弱隨機源的萃取器 (two-sources-extractors)，多弱隨機源的萃取器 (multi-sources-extractors)，以及實作可用 於生物認證上的模糊萃取器 (fuzzy extractors for biometric authentication)。弱隨機源 (Weak random sources)所能保證的事只有不會有某一個特定字串出現的機率非常高。 如果我們說一個弱隨機源的min-entropy 為b 則表示每個字串出現的機率都不會超過 2.b ，直觀地，我們認為這樣的弱隨機源 」包含」 b 個隨機元。而萃取器(extractor)是 一個函數，它可以從弱隨機源中，萃取出相當靠近均等分佈(uniform distribution)的 隨機元。過去幾十年來，國內外的理論學家都致力於發展需要額外的真實隨機元才能萃 取弱隨機源中隨機性 (randomness)的種子萃取器 (seeded extractors)。經過多年的 努力後，種子萃取器的發展已幾進完美，且在資訊科學的許多領域有重要的應用。可是 由於真實的隨機元在自然界中並不存在，因此，學者們慢慢的把目標放在如何從兩個或 多個弱隨機源中萃取出隨機性以及考慮限制更強的固定某些位元的決定性萃取器 (deterministic extractors for bit-fixing sources)。 本計劃將改進先前固定某些位元萃取器當來源隨機性太低時，所輸出的隨機元 與均等分佈誤差過大的缺點，且經由固定某些位元萃取器的建造方式來改進多個弱隨機 源萃取器只萃取出元來源隨機性極少部分的缺點。最後，我們將改進模糊萃取器利用編 碼理論(coding theory)來增加其錯誤更正能力卻反而容易洩露資訊的危機，並實作一 個應用於生物認證方面的模糊萃取器。