最短向量問題求解的高維基格約化算法

　　格基約化算法是求解格上最短向量問題（SⅤP）的一類算法，在格理論中有重要地位，尤其在格理論構(gòu)造的公鑰密碼中發(fā)揮重要作用。目前公認(rèn)效率最高的主流算法是 Block wise- Korkine- Zolotarey（BKZ）及其改進(jìn)形式BKZ2.0，主要思想是分塊約化，調(diào)用多項式次的局部格上SⅤP算法。但是BKZ類算法仍然存在約化程度不夠充分、在高維度格中約化效率不高的問題，也存在多種改進(jìn)的算法。本文在已有算法的基礎(chǔ)上，對BKZ結(jié)構(gòu)進(jìn)行優(yōu)化，并應(yīng)用篩法的最新研究成果，設(shè)計了一種新的綜合算法— Blockwise- Sieving-reduction（BSR）。在預(yù)處理階段，將格矩陣劃分后分別進(jìn)行BKZ預(yù)處理，該過程可直接進(jìn)行并行化。在格基約化階段，該算法結(jié)合BKZ算法與篩法的優(yōu)點，使用分塊逐次增大的多輪BKZ算法進(jìn)行預(yù)處理，并在BKZ結(jié)構(gòu)中使用改進(jìn)的篩法替代原有的枚舉子過程，通過插入向量改進(jìn)局部格的性質(zhì)，提高了BKZ算法的效率，使之能在更大的分塊下求解SVP.針對更高維度的格矩陣，設(shè)計了遞歸調(diào)用的算法變種稱為iBSR算法，該算法使用了漸進(jìn)約化等實現(xiàn)技術(shù)，可以進(jìn)行更大維度格的約化。從理論角度進(jìn)行分析，論證了該算洪可以進(jìn)行格基約化并求格上短向量。實驗結(jié)果表明，該算法在較大分塊下，能夠以可接受的時間代價完成SVP求解，且得到的向量優(yōu)于已有算法的實驗結(jié)果，新算法得到的首向量長度可以縮短至BKZ2.0的90%。