文献

J-GLOBAL ID：202102242363914032   整理番号：21A1180917

General Sieve Kernelの考察および改良

著者 (3件)： 長谷川奨 (北陸先端科学技術大学院大) ,  王イントウ (北陸先端科学技術大学院大) ,  藤崎英一郎 (北陸先端科学技術大学院大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2021  号： CSEC-92  ページ： Vol.2021-CSEC-92,No.68,1-7 (WEB ONLY)  発行年： 2021年03月08日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 2019年にAlbrecht等が提案したGeneral Sieve Kernel(G6K)は,2021年2月時点のダルムシュタット工科大学が主催しているSVP Challengeにて180次元の近似最短ベクトルを見つけている.使用時間の制限がある大規模計算機とG6Kを使用して近似最短ベクトルを見つける場合,近似最短ベクトルが見つかる前にプログラムが停止し,解読データが削除されてしまう.本稿では,G6Kに保存機能の追加とパラメータの調整を行った.その結果,SVP Challengeで未解読次元であった154,156,158次元の近似最短ベクトルを見つけた.(著者抄録)

シソーラス用語： 量子コンピュータ ,  *公開鍵暗号 ,  ベクトル ,  *アルゴリズム ,  計算理論 ,  ベクトル空間 ,  格子 ,  数学的変換 ,  発見的方法 ,  実証実験
準シソーラス用語： *G6K【暗号】 ,  量子計算機 ,  *最短ベクトル問題 ,  多項式時間アルゴリズム ,  射影格子 ,  Gram-Schmidtの直交化 ,  LLL基底簡約アルゴリズム ,  逐次最小 ,  ガウシアンヒューリスティック

分類 (2件)： 符号理論  (ND02030R) ,  計算理論  (JB02000A)

引用文献 (13件)：

• Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, Vol. 41, No. 2, pp. 303-332, 1999.
• Post-quantum cryptography csrc. Available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.
• Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische annalen, Vol. 261, No. ARTICLE, pp. 515-534, 1982.
• Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, Vol. 66, No. 1-3, pp. 181-199, 1994.
• Miklós Ajtai, Ravi Kumar, and Dandapani Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 601-610, 2001.