理想格上格基的快速三角化算法研究
doi: 10.11999/JEIT190725 cstr: 32379.14.JEIT190725
-
1.
中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100093
-
2.
中國(guó)科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 北京 100049
-
3.
衛(wèi)士通摩石實(shí)驗(yàn)室 北京 100166
Fast Triangularization of Ideal Latttice Basis
-
1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
-
2.
School of Cyber Security,University of Chinese Academy of Sciences, Beijing 100049, China
-
3.
Westone Cryptologic Research Center, Beijing 100166, China
-
摘要:
為了提高理想格上格基的三角化算法的效率，該文通過(guò)研究理想格上的多項(xiàng)式結(jié)構(gòu)提出了一個(gè)理想格上格基的快速三角化算法，其時(shí)間復(fù)雜度為O(n3log2B)，其中n是格基的維數(shù)，B是格基的無(wú)窮范數(shù)?；谠撍惴?，可以得到一個(gè)計(jì)算理想格上格基Smith標(biāo)準(zhǔn)型的確定算法，且其時(shí)間復(fù)雜度也比現(xiàn)有的算法要快。更進(jìn)一步，對(duì)于密碼學(xué)中經(jīng)常所使用的一類(lèi)特殊的理想格，可以用更快的算法將三角化矩陣轉(zhuǎn)化為格基的Hermite標(biāo)準(zhǔn)型。
-
關(guān)鍵詞:
- 理想格 /
- Hermite標(biāo)準(zhǔn)型 /
- Smith標(biāo)準(zhǔn)型 /
- 三角化
Abstract:To improve the efficiency of the triangularization of ideal lattice basis, a fast algorithm for triangularizing an ideal lattice basis is proposed by studying the polynomial structure, which runs in time O(n3log2B), where n is the dimension of the lattice, B is the infinity norm of lattice basis. Based on the algorithm, a deterministic algorithm for computing the Smith Normal Form (SNF) of ideal lattice is given, which has the same time complexity and thus is faster than any previously known algorithms. Moreover, for a special class of ideal lattices, a method to transform such triangular bases into Hermite Normal Form (HNF) faster than previous algorithms will be present.
-
Key words:
- Ideal lattice /
- Hermite Normal Form (HNF) /
- Smith Normal Form (SNF) /
- Triangularization
-
表 1 本原格向量序列
輸入：$ {\mathbb{Z}}\left[ {{x}} \right]$中$ f\left( x \right)$和$ g\left( x \right)$，次數(shù)分別為$ n$和$ m$，且$ n>m$； (1) 利用擴(kuò)展歐幾里得算法計(jì)算$ {\mathbb{Q}}[x]$上$ {r_i}^{'}\left( x \right)$, $ {s_i}^{'}\left( x \right)$, $ {t_i}^{'}\left( x \right)$，使得$ {r_i}^{'}\left( x \right) = {r_{i - 2}}^{'}\left( x \right) + {q_i}^{'}\left( x \right){r_{i - 1}}^{'}\left( x \right)$ 和${r_i}^{'}\left( x \right) = {s_i}^{'}\left( x \right)f\left( x \right) + $$ {t_i}^{'}\left( x \right)g\left( x \right)$成立，這里 $ i = 1,2, ··· ,l$； (2) 計(jì)算每一個(gè)$ {t_i}^{'}\left( x \right)$系數(shù)分母的最小公倍數(shù)$ {C_i}$, $ i = 1,2, ··· ,l$； (3) 令$ {r_i}\left( x \right) = {r_i}^{'}\left( x \right) \cdot {C_i}$為余式序列中第$ i$個(gè)余式， $ i = 1,2, ··· ,l$； 輸出：$ {r_1}\left( x \right)$, $ {r_2}\left( x \right)$, ···, $ {r_l}\left( x \right)$ 
下載: 導(dǎo)出CSV
表 2 理想格上格基的三角化
輸入：本原格向量序列，$ {r_0}\left( x \right)$, $ {r_1}\left( x \right)$, ···, $ {r_l}\left( x \right)$(向量形式為$ {{{r}}_{\bf 0}}$,
$ {{{r}}_{\bf 1}}$, ···, $ {{{r}}_{ l}}$)(1) 令$ {{T}} \leftarrow {0^{n \times n}}$ (2) 如果$ k \in {I_l},{{ T}_k}\left( x \right) = {r_l}\left( x \right){x^{n - k}},i \leftarrow l - 1$ (3) 如果$ k \in {I_i}$， (a) 計(jì)算$ \phi $和ψ使得
$ \phi {\rm{lc}}\left( {{r_i}} \right) + \psi {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right) = {\rm{gcd}}\left( {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right),\right.$
$\left.{\rm{lc}}\left( {{r_i}} \right) \right) $(b) 令$ {{{T}}_{n - {n_i}}}\left( {{x}} \right) = \phi {r_i}\left( x \right) + \psi {{{T}}_{n - {n_{i + 1}}}}\left( x \right){x^{{\delta _i}}}$ (c) 如果$ {\rm{lc}}\left( {{{{T}}_{n - {n_i}}}} \right) = 1$，則令
$ {{{T}}_j}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - j}}$,
$ j = 1,2, ··· ,n - {n_i}$，并結(jié)束循環(huán)(d) 否則$ {{{T}}_k}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - k}}$, $ i \leftarrow i - 1$ (e) 如果$ i>0$，到(3)開(kāi)始循環(huán)，否則結(jié)束循環(huán) 輸出：$ {{T}}$
下載: 導(dǎo)出CSV
-
FRUMKIN M A. Complexity questions in number theory[J]. Journal of Soviet Mathematics, 1985, 29(4): 1502–1517. doi: 10.1007/bf02104748 HUNG M S and ROM W O. An application of the Hermite normal form in integer programming[J]. Linear Algebra and its Applications, 1990, 140: 163–179. doi: 10.1016/0024-3795(90)90228-5 HAFNER J L and MCCURLEY K S. A rigorous subexponential algorithm for computation of class groups[J]. Journal of the American Mathematical Society, 1989, 2(4): 837–850. doi: 10.1090/S0894-0347-1989-1002631-0 HARTLEY B and HAWKES T O. Rings, Modules and Linear Algebra[M]. London: Chapman and Hall, 1970: 73. MICCIANCIO D. Improving lattice based cryptosystems using the Hermite normal form[C]. International Conference on Cryptography and Lattices, Providence, 2001: 126–145. doi: 10.1007/3-540-44670-2_1. LYUBASHEVSKY V and PREST T. Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, 2015: 789–815. doi: 10.1007/978-3-662-46800-5_30. HAFNER J L and MCCURLEY K S. Asymptotically fast triangulation of matrices over rings[C]. The 1st Annual ACM-SIAM Symposium on Discrete Algorithm, San Francisco, 1990: 197–200. LE GALL F. Powers of tensors and fast matrix multiplication[C]. The 39th International Symposium on Symbolic and Algebraic Computation, Kobe, 2014: 296–303. doi: 10.1145/2608628.2608664. STORJOHANN A and LABAHN G. Asymptotically fast computation of Hermite normal forms of integer matrices[C]. 1996 International Symposium on Symbolic and Algebraic Computation, Zurich, 1996: 259–266. DING Jintai and LINDNER R. Identifying ideal lattices[EB/OL]. http://eprint.iacr.org/2007/322, 2007. ZHANG Yang, LIU Renzhang, and LIN Dongdai. Improved key generation algorithm for Gentry’s fully homomorphic encryption scheme[C]. The 20th International Conference on Information Security and Cryptology, Seoul, 2018: 93–111. doi: 10.1007/978-3-319-78556-1_6. VON ZUR GATHEN J and GARHARD J. Modern Computer Algebra[M]. 3rd ed. Cambridge: Cambridge University Press, 2013: 313–332. 劉仁章. 格算法及其密碼學(xué)應(yīng)用[D]. [博士論文], 中國(guó)科學(xué)院大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)研究院, 2016. -
計(jì)量
- 文章訪問(wèn)數(shù): 3199
- HTML全文瀏覽量: 1040
- PDF下載量: 75
- 被引次數(shù): 0
下載:
