1976年，Diffie和Hellman在《密碼學(xué)的新方向》（Neu，Directions in Crypto-graphy）一文中首次提出了公鑰密碼體制的思想，開創(chuàng)了密碼學(xué)的新紀(jì)元。公鑰密碼體制中，每個(gè)用戶擁有公開的公鑰和私有的私鑰，且由公鑰無法導(dǎo)出私鑰。這不僅避免了對稱密碼體制固有的密鑰分發(fā)問題，也催生了數(shù)字簽名體制，而公鑰密碼體制所提供的可認(rèn)證性、機(jī)密性、不可否認(rèn)性和數(shù)據(jù)完整性等安全服務(wù)使得其成為當(dāng)前網(wǎng)絡(luò)環(huán)境下保障信息安全的核心技術(shù)。
密碼體制的安全性分析是密碼體制設(shè)計(jì)中不可或缺的重要環(huán)節(jié)，而對直觀上的“安全”給予嚴(yán)格的定義是安全性分析的基礎(chǔ)。到目前為止，學(xué)術(shù)界有兩種定義方法：信息論方法和復(fù)雜度方法。信息論方法所關(guān)注的是密文是否具有相應(yīng)明文的信息。粗略地說，如果密文含有相應(yīng)明文的某些信息，則認(rèn)為該加密體制是不安全的。已經(jīng)證明，只有當(dāng)密鑰長度超過所加密的明文時(shí)，才能實(shí)現(xiàn)高級別的安全性（無條件的安全）。在實(shí)際應(yīng)用中，這是極其不方便的。只使用中等長度的密鑰就可以進(jìn)行不限量安全通信的密碼是更可取的。但是暴力破解的存在使得在原則上不可能有這樣的密碼，然而如果該密碼沒有其他破譯方法，且暴力破解對于當(dāng)前的計(jì)算能力而言是不可行的，那么在實(shí)際中人們?nèi)匀豢梢允褂迷撁艽a。但問題在于如何確信密碼不能被快速破譯。當(dāng)然，在數(shù)學(xué)上對上述問題給予證明是最佳方案，但是NP是否不等于P是世界難題，這說明無法數(shù)學(xué)證明密碼是不可破譯的，所以人們似乎只能依靠實(shí)際證據(jù)來說明密碼體制是安全的。過去，密碼的質(zhì)量靠請專家破譯密碼來評價(jià)，如果他們不能破譯，就會增強(qiáng)對密碼安全的信心。這種方法有明顯的不足，如果別人有更好的專家，或者我們對自己的專家缺乏信任，那么密碼的完善性可能受到損害。盡管如此，直到最近這個(gè)方法仍是唯一可供使用的方法，并且靠它支持像美國國家標(biāo)準(zhǔn)局正式批準(zhǔn)的數(shù)字加密標(biāo)準(zhǔn)（DES、AES）這樣一些廣泛使用的密碼的可靠性。
隨著對密碼基礎(chǔ)研究的深入，密碼學(xué)家認(rèn)為將密碼的不可破譯性與公認(rèn)的數(shù)學(xué)難題相掛鉤，則在現(xiàn)有的計(jì)算能力下，可以說明密碼的安全性，這便是計(jì)算復(fù)雜度方法的安全性證明思想。