模糊提取器：Fuzzy Extractor and Secure Sketch

原文已經丟失，以下由archive獲取。

密碼機制中的祕密值通常是隨機串，要求是均勻分佈，而且需要時可以 精確再生。而在現實世界中祕密值很難滿足這一點，例如，對於類似指紋等的生物特徵，並不是均勻分佈的隨機值，而且每次需要時，也無法精確的再現（指紋都存在一定誤差）。使用者進行認證最常見的方式是基於Password，短的Password使用者容易記憶，但是熵值很低，安全性差；而一些長的密碼短語，使用者不容易記憶，而且也無法使用均勻分佈的亂數。要跨越這種障礙，需要一種方法能將現實中的這些祕密值轉換為真正密碼系統需要的均勻分佈的亂數。這篇介紹的模糊提取器可以達到這一點要求。

模糊提取器?Fuzzy Extractor（FE），允許輸入擁有一定的噪聲（或者錯誤），只要輸入相近能提取出相同的一個均勻的隨機字串，大體構造如下：

Gen過程：輸入w，輸出輔助資料P（公開）和均勻隨機值R（l位元）。

Rep過程：給定P，輸入w’，重新生成均勻隨機值R 。

正確性：如果dis(w,w’)<=t，可以重構出精確的R；如果dis(w,w’)>t，對Rec的輸出不提供任何保證

安全性：輔助資料P不會洩露R的太多資訊；R的分佈接近均勻分佈。

應用：從w中提取的R可以用作金鑰，不過不需要儲存，下次使用從w’恢復即可 ?W可以是生物指紋、物理指紋PUF、或者其他密碼材料（如使用者記得不太清楚的密碼短語）等。

安全概略Secure Sketch (SS) ?允許對噪聲輸入進行精確的重構， ?與FE不同的是，SS是重構出原始輸入本身，並不解決非均勻分佈問題，SS大體構造如下：

SS過程：輸入w，輸出s，s可以公開；。

Rec過程：給定s和輸入w’（與w接近），可以恢復出w ?。

正確性：如果dis(w,w’)<=t，可以恢復出精確的w；如果dis(w,w’)>t，對Rec的輸出不提供任何保證 。

安全性：s不會洩露w的太多資訊。

SS過程實際上是暗含一個FE的，通過如下圖所示的方式，通過增加一個強亂數提起前Ext，可以從SS構造FE：

從前面可知，SS和FE都可以重構出之前的一個精確值，但是SS重構的是原始輸入本身，不具有均勻隨機性，通過增加一個強隨機提取器Ext可以從SS構造出FE。 ?這裡，x是Ext的隨機種子，x和SS(w)可以作為FE的輔助資料。通過可以使用HMAC或者KDF來實現一個Ext功能。

一個簡單的例子：使用FE將生物特徵等資料用於加解密應用

w、w’對於使用者的生物特徵輸入（如指紋），FE最後生成的均勻亂數種子R可以作為金鑰，用於加解密。這樣做的一個好處是，不需要儲存任何金鑰，需要時就可以基於生物特徵重構出R。

另一個例子：使用物理不可克隆函數PUF（相當於物理指紋）來生成金鑰

參考：

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM Journal on Computing, 38(1):97–139, 2008.