基于格的偽隨機函數研究綜述*

李一鳴, 劉勝利

1.上海交通大學 計算機科學與工程系, 上海 200240

2.密碼科學技術全國重點實驗室, 北京 100878

1 前言

偽隨機函數(pseudorandom function,PRF)的概念是由Goldreich、Goldwasser 和Micali 在文獻[1]中首次提出的.偽隨機函數F:K×X →Y是多項式時間可計算且具有偽隨機特性的確定性函數, 其偽隨機性要求: 對于均勻隨機選取的密鑰k$←?K, 函數F(k,·) 的計算結果與真隨機函數的計算結果之間計算不可區分.我們稱描述偽隨機函數F的集合K、X和Y分別為偽隨機函數的密鑰空間、消息空間和輸出空間, 本文中, 考慮X={0,1}?是長度為?的比特串集合.部分偽隨機函數在計算時還需使用到公開參數及相應的公開參數生成算法.

作為密碼學領域的基礎原語之一, 偽隨機函數有著非常廣泛的應用.偽隨機函數結合Feistel 結構可以構造偽隨機置換.基本的對稱密碼機制, 如對稱加密、消息認證和身份識別, 都可以基于偽隨機函數簡潔地實現[1,2].進一步地, 偽隨機函數也可作為組件構造對稱版本的代理重加密和可更新加密[3,4]等高級對稱密碼方案.在公鑰密碼領域, 偽隨機函數被創造性地應用于構造基于身份的加密、基于屬性的加密、支持任意電路的功能加密以及數字簽名方案[5–9].在協議設計中, 偽隨機函數常用作密鑰導出函數, 從相對短的密鑰中方便地派生出足夠數量的高質量密鑰.具有擴展功能(如可驗證、水印) 的偽隨機函數還可用于設計區塊鏈協議、設計電子貨幣系統、提供版權保護和盜版追蹤等[10–14].除應用于密碼方案的設計……