公鑰密碼方案的可證明安全性注記

摘要：長期以來，人們對于可證明安全的認識存在著一些誤區：可證明安全的方案一定是安全的，歸約證明緊的一定比歸約松的更安全。總結了與方案安全性有關的幾個要素，分析了公鑰密碼方案可證明安全的實質，糾正了以往的一些錯誤認識，指出可證明安全的方案不一定是安全的，歸約緊的方案不一定比歸約松的更安全。方案的安全性要綜合四個要素一起考慮，總的來說，攻擊模型越難，攻擊目標越容易，困難問題越難，而歸約證明最緊的方案越安全。

關鍵詞：可證明安全; 攻擊模型; 攻擊目標; 歸約松緊度

中圖分類號：TP393．17文獻標志碼：A

文章編號：1001－3695(2008)04－1130－04

0引言

公鑰密碼學是現代密碼學的重要組成部分。每個參與者都有兩個密鑰，即公鑰與私鑰。其中，公鑰是公開的，私鑰是保密的。根據Kerckhoff假設[1]，密碼體制是公開的，方案的安全性只依賴于密鑰的安全性，攻擊者不能從方案本身得到任何對它有用的信息。在這種情況下，如何設計安全方案是擺在國內外專家學者面前的一道難題。

20 世紀80年代初，Goldwasser等人首先比較系統地闡述了可證明安全性這一思想，并給出了具有可證明安全性的加密和簽名方案[2，3]。然而，以上方案的可證明安全性是以嚴重犧牲效率為代價的，這種情況嚴重制約了這一領域的發展。直到1993年，Bellare等人提出了random oracle 模型[4]，過去僅作為純理論研究的可證明安全性理論，迅速在實際應用領域取得了重大進展。一般而言，可證明安全性是指這樣一種歸約方法[5]：首先確定安全方案的攻擊目標；然后根據敵手的能力構建一個形式的敵手模型，對某個基于極微本原的特定方案，基于以上形式化的模型去分析它；最后指出，挫敗方案的惟一方法就是破譯或解決極微本原。實際上，可證明安全性理論是在一定的敵手模型下證明了安全方案能夠達到特定的攻擊目標。

近年來，可證明安全是密碼學的一個研究熱點。許多學者提出了各種各樣的可證明安全的方案。其中，有很多被時間檢驗的很安全的方案，也有聲稱可證明但不是歸約證明的方案[6]，還有可證明安全但不安全的方案[7，8]。事實上，這些證明模型是有問題的，證明的結果也不能說明方案與原困難問題的安全性等價，而是有著一定的差距。這些結果說明在證明過程中，歸約松緊度起著至關重要的作用。所謂松緊度，就是衡量原困難問題與方案安全性差距的一個量。松緊度越小，說明攻破方案的難度越接近困難問題的難度；松緊度越大，說明攻破方案的難度與困難問題的難度差距越大。

最近，Koblitz和 Menezes在文獻[8，9]中提出了不同的觀點，認為可證明安全是一門藝術，而不是科學，它的有些結果與實際矛盾，不能精確地證明方案的安全性。可證明安全是方案安全性的一種衡量標準，沒有可證明安全的方案不一定是不安全的，可證明安全并且歸約緊的方案在證明的攻擊目標和安全模型下是安全的。它體現的是方案的安全性和困難問題難度之間的關系，是很有意義的。

現在可證明安全的方案很多。許多人認為它們一定是安全的，而且歸約緊的一定比歸約松的更安全，這種認識比較片面，是不準確的。可證明安全，本質上來說是一種歸約安全，即把方案的安全性歸約為解決困難問題的難度。而歸約的本質就是盡量減小松緊度。它主要與以攻擊目標、攻擊模型、基于數學問題或陷門單項函數問題、構造方法有關。比較兩個方案的精確安全性需要在相同的攻擊模型與攻擊目標下才有意義。

c)問題更難而歸約更緊

與前面情況類似，如果歸約更緊而不是最緊，問題難的方案也不一定是更安全的。只有歸約最緊，問題難的方案才是更安全的，因為它的安全性等價于更困難問題的難度。

還舉前面兩個例子，PSS方案基于RSA求逆問題，定理4給出了PSS方案的一個緊證明，說明它的安全性近似等價于RSA求逆問題的難度。GHR方案基于強RSA問題，定理5給出了GHR方案的一個不太緊的證明，說明它的安全性距離RSA求逆問題的難度還有一定差距。比較這兩個方案，PSS基于的問題更難，而歸約更緊，所以到目前為止，筆者認為PSS方案比GHR方案更安全。

綜上所述，歸約證明緊的方案不一定比證明松的方案更安全。方案的安全性與它基于的問題困難性和歸約松緊度有關。如果是基于同一問題的同一方案，歸約證明越緊越好；如果是基于同一問題的不同方案，歸約緊的不一定比歸約松的更安全，除非歸約是最緊的，也就是說，近似等價于困難問題的難度；如果是基于不同問題的不同方案，基于的問題更難而歸約是最緊的方案是更安全的。

3結束語

近年來，可證明安全是密碼學的研究熱點之一。它是衡量方案安全性的一種有效方法，得到了國內外許多專家學者的認同，提出了很多有效的方案，并把它們的安全性歸約為解決困難問題的難度。現在大部分方案都聲稱可證明安全，且認為歸約越緊的方案越安全，但是事實并非如此。方案的安全性要綜合四個要素一起考慮。總的來說，攻擊模型越難，攻擊目標越簡單，困難問題越難，而歸約最緊的方案越安全。

參考文獻：

［1］STINSON D R. 密碼學原理與實踐[M]. 馮登國，譯.北京：電子工業出版社， 2003.

［2］GOLDWASSER S， MICALI S.Probabilistic encryption[J]. Journal of Computer and System Science， 1984，37(2): 270－299.

［3］GOLDWASSER S， MICALI S， RIVEST R. A digital signature sche－me secure against adaptive chosen－message attacks[J]. SIAM Journal of Computing， 1988， 17(2):281－308.

［4］BELLARE M， ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocols: conference on computer and communications security[C]//Proc of the 1st ACM Conference on Computer and Communications Security.1993: 62－73.

［5］馮登國.可證明安全性理論與方法研究[J]. 軟件學報， 2005， 16(10): 1743－1756.

［6］吳晨煌，黃振杰.代理不可否認簽名[J]. 計算機應用， 2006， 26(11):2592－2595.

［7］CANETTI R， GOLDREICH O， HALEVI S. The random oracle model revisited[C]//Proc of the 30th Annual Symp Theory of Computing.[S.l.]: ACM， 1998:209－218.

［8］KOBLITZ N， MENEZES A J. Another look at “provable security” Ⅱ[J/OL]. （2006）. http://eprint.iacr.org/.

［9］KOBLITZ N， MENEZES A J. Another look at“provable security”[J/OL]. （2004）. http://eprint.iacr.org/.

［10］RABIN M. Digitalized signatures and public－key functions as intractable as factorization，LCS/TR－212[R].[S.l.]:MIT Lab，1979.

［11］BELLARE M， ROGAWAY P. The exact security of digital signatures—how to sign with RSA and Rabin[C]//Proc of Advances in Cryptology—Eurocrypt ’96. Berlin:Springer－Verlag， 1996:399－416.

［12］CORON J S. On the exact security of full domain hash[C]//Proc of Advances in Cryptology－CRYPTO’00.2000: 229－235.

［13］CORON J S. Optimal security proofs for PSS and other signature schemes[C]//Advances in Cryptology－Eurocrypt 2002， LNCS 2332. 2002.

［14］GENNARO R， HALEVI S， RABIN T. Secure hash－and－sign signatures without the random oracle[C]//Proc of Advances in Cryptology－EUROCRYPT’99， LNCS 1592. Berlin:Springer－Verlag，1999:123－139.

［15］BARIC N， PFITZMANN B. Collision－free accumulators and fail－stop signature schemes without trees[C]//Proc of Advances in Cryptology－Eurocrypt’97， LNCS 1233.Berlin:Springer－Verlag，1997:480－494.

［16］JONATHAN K， NAN W. Efficiency improvements for signature schemes with tight security reductions[C]//Proc of ACM Conference on Computer and Communications Security.2003:155－164.

［17］EU－JIN G， STANISLAW J.A signature scheme as secure as the DH problem[C]//Proc of Advances in Cryptology－EUROCRPYT 2003: International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 2656. Berlin:Springer－Verlag，2003:401－415.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”