NTRU

NTRU是一個帶有專利保護的開源公開密鑰加密系統，使用晶格加密算法（英語：lattice-based cryptography）來加密數據。它包括兩部分算法：NTRUEncrypt（英語：NTRUEncrypt）用來加密，NTRUSign（英語：NTRUSign）用來進行數字簽名。與其他流行的公鑰加密系統不同，它可以防止被Shor算法破解，並顯著提升了性能。

歷史

第一個被命名為NTRU的加密系統版本，是數學家Jeffrey Hoffstein（英語：Jeffrey Hoffstein），Jill Pipher（英語：Jill Pipher），和Joseph H. Silverman（英語：Joseph H. Silverman）於1996年開發的。同年，Daniel Lieman加入了NTRU開發團隊，並成立了公司NTRU Cryptosystems, Inc.， 獲得了該加密系統的專利。^[1]2009年，該公司被一家名為Security Innovation的軟體安全公司收購。^[2]2013年，Damien Stehle和Ron Steinfeld創建了NTRU的一個可靠版本，目前正在由歐盟執委會授權的後量子加密小組進行研究。^[3]

2016年5月，Daniel Bernstein，Tanja Lange等人發布了NTRU Prime，^[4]通過消除一些令人不安的代數結構以抵抗潛在的攻擊。

性能

在同等加密強度下，NTRU執行大開銷的私鑰操作比RSA算法快得多。^[5]RSA算法的私鑰操作耗時與密鑰長度呈三次方關係，而NTRU相應操作為二次方關係。

據魯汶大學電子工程部門表示，「使用一塊現代的GTX280顯卡，在256 bit加密強度下，最高可達每秒二十萬次的加密的吞吐量。與最新的對稱加密AES實現相比（這並不公平），只慢了大概二十倍。」^[6]

防止量子計算機破解

與RSA加密演算法和橢圓曲線加密算法（英語：Elliptic Curve Cryptography, ECC）不同，NTRU在基於量子計算機的攻擊面前沒有已知的弱點。國家標準技術研究所在一份2009年的調查中寫到「目前不存在一種能同時兼顧公鑰加密和數字簽名，並在Shor算法面前沒有弱點的可行替代方案」以及「在基于格的眾多已有加密方案中，NTRU加密算法族看起來是最可行的」。^[7]歐盟的PQCRYPTO計劃(Horizon 2020 ICT-645622)正在評估Stehle–Steinfeld可靠版本的NTRU (並非原始版本的NTRU算法)，以作為一項潛在的歐洲標準。^[3]然而Stehle-Steinfeld版本的NTRU「比原始版本效率要低得多」."^[8]

標準

• IEEE Std 1363.1標準，發布於2008年，標準化了基于格的公鑰加密算法，尤其是NTRUEncrypt。^[9]
• X9.98標準，標準化了基于格的公鑰加密算法，尤其是NTRUEncrypt，作為X9（頁面存檔備份，存於網際網路檔案館）金融服務標準的一部分。^[10]
• 歐洲理事會的PQCRYPTO計劃正在考慮標準化Stehle-Steinfeld可靠版本的NTRU^[8]

發行方式

最初，NTRU只有一個帶專利保護的付費開源庫可用，打算寫開源實現的作者收到訴訟威脅。^[11][12]直到2011年出現了第一個開源實現，^[13]在2013年，Security Innovation豁免了開源項目的專利授權要求，^[14]並以GPL v2協議釋放了一份NTRU的參考實現。^[15]

Security Innovation依然提供付費的專有軟體選項。^[16]

現在存在兩個開源的NTRU實現：

• GPL-licensed下的參考實現^[15]
• BSD-licensed下的庫^[13]

分別在Java和C下可用。