基于LWE問題的采樣算法及應用研究.pdf

1、隨著量子計算研究的不斷發(fā)展，量子計算機的出現(xiàn)將不再是空談，因此研究出能夠抵御量子攻擊的新型密碼體制成為了研究熱點。而格上的很多問題被證明是困難的，是通過量子計算在多項式時間內(nèi)也無法求解的，因而很多密碼體制的設計都是基于格上的困難問題。帶錯誤學習問題(Learning with error，LWE)是格上的困難問題之一，通過LWE問題構(gòu)造的密碼體制在安全性上可以得到保證。而對LWE問題的采樣效率關系到對應的密碼體制的應用效率，基于這一問題

2、，本文對LWE問題的采樣算法進行了研究。在LWE問題中，對錯誤因子的采樣占用了絕大部分的時間，并且使用的采樣算法靈活多變，是研究LWE問題采樣的主要內(nèi)容。對LWE問題中錯誤因子的采樣是從離散高斯分布上采樣獲得的，因此對離散高斯分布上的采樣算法研究成為了本文的研究重點。
　　本文以設計出高效的新型LWE問題采樣算法為目標，首先對現(xiàn)有的LWE問題采樣算法進行了研究，通過對算法的實現(xiàn)發(fā)現(xiàn)了現(xiàn)有算法中綜合性能最好的離散金字塔(Ziggur

3、at)高斯采樣算法，因此對該算法進行了深入研究。基于將格上的采樣轉(zhuǎn)化為整數(shù)域上的采樣這一思路，本文提出了一種新的LWE問題采樣算法，在該采樣算法中，對整數(shù)域上的離散高斯分布采樣過程進行了優(yōu)化，并與現(xiàn)有最優(yōu)算法離散金字塔采樣算法進行了效率比對，發(fā)現(xiàn)本文提出的優(yōu)化改進算法比離散金字塔采樣算法的采樣速度快了2倍。
　　A-LWE（Augmented Learning with Errors）問題作為LWE問題的擴展問題，增加了信息嵌入的