基于LWE問(wèn)題的采樣算法及應(yīng)用研究.pdf

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

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

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