公鑰密碼安全強度刻畫概述*

林 申，陳 潔，王陸平

1.華東師范大學 軟件工程學院 上海高可信計算重點實驗室，上海200062

2.蘇州科技大學 電子與信息工程學院，蘇州215009

3.江蘇省電梯智能安全重點建設實驗室，常熟215500

1 引言

現代公鑰密碼方案的安全性是建立在困難性問題假設上的，具有可證明安全性(provable security)，即: 若求解該問題假設是困難的，則稱該公鑰密碼方案是安全的.這也是公鑰密碼學與對稱密碼學在本質上的一大不同.公鑰密碼方案的安全性與困難問題假設的種類緊密相關，按困難問題對公鑰密碼方案進行分類也是一類常見的分類標準.

如圖1 所示，現存的公鑰密碼方案可大致分為兩類: 基于經典數論問題的方案和基于抗量子攻擊困難問題的方案.經典數論體系下公開的公鑰密碼方案以1976 年提出的Diffie-Hellman 密鑰交換算法[1]為開端，可根據嵌入困難問題的不同分為三類: 即基于大整數分解問題、基于離散對數問題和基于橢圓曲線問題的方案.然而，隨著量子計算機的出現，經典公鑰密碼體制的安全性受到了極大的挑戰.Shor 算法的提出，使得破解RSA、DSA、ECDSA 算法成為了可能[2].因此，抗量子攻擊的新密碼方案在近些年應運而生，被稱為后量子密碼.相似地，根據困難問題的不同，可將常見的后量子密碼分為五類:基于格問題、基于編碼問題、基于哈希函數問題、基于超奇異橢圓曲線同源問題和基于多變量二次方程組問題的方案.由于方案安全性的內核和攻擊者的能力都有本質不同，經……