Fugu-MT 論文翻訳(概要): Symplectic Lattices and GKP Codes -- Simple Randomized Constructions from Cryptographic Lattices

論文の概要: Symplectic Lattices and GKP Codes -- Simple Randomized Constructions from Cryptographic Lattices

arxiv url: http://arxiv.org/abs/2509.10183v1
Date: Fri, 12 Sep 2025 12:17:04 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-15 16:03:08.078476
Title: Symplectic Lattices and GKP Codes -- Simple Randomized Constructions from Cryptographic Lattices
Title（参考訳）: シンプレクティック格子とGKP符号-暗号格子からの単純なランダム化構成
Authors: Johannes Blömer, Yinzi Xiao, Zahra Raissi, Stanislaw Soltan,
Abstract要約: 我々は、標準短整数解格子(SIS)と、環SISおよびモジュールSIS格子、R-SISおよびM-SIS格子から優れたGKP符号を構築する。我々の構成では、距離が$sqrtn/pi e$のGKP符号が得られる。我々は,多くのパラメータ選択に対して,NTRUベースのコードと同様の復号結果が得られる簡単な復号アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We construct good GKP (Gottesman-Kitaev-Preskill) codes (in the sense of Conrad, Eisert and Seifert proposed) from standard short integer solution lattices (SIS) as well as from ring SIS and module SIS lattices, R-SIS and M-SIS lattices, respectively. These lattice are crucial for lattice-based cryptography. Our construction yields GKP codes with distance $\sqrt{n/\pi e}$. This compares favorably with the NTRU-based construction by Conrad et al. that achieves distance $\Omega(\sqrt{n/q}),$ with $n\le q^2/0.28$. Unlike their codes, our codes do not have secret keys that can be used to speed-up the decoding. However, we present a simple decoding algorithm that, for many parameter choices, experimentally yields decoding results similar to the ones for NTRU-based codes. Using the R-SIS and M-SIS construction, our simple decoding algorithm runs in nearly linear time. Following Conrad, Eisert and Seifert's work, our construction of GKP codes follows directly from an explicit, randomized construction of symplectic lattices with (up to constants $\approx 1$) minimal distance $(1/\sigma_{2n})^{1/2n}\approx \sqrt{\frac{n}{\pi e}}$, where $\sigma_{2n}$ is the volume of the 2n-dimensional unit ball. Before this result, Buser and Sarnak gave a non-constructive proof for the existence of such symplectic lattices.
Abstract（参考訳）: 我々は、標準短整数解格子(SIS)と、リングSISおよびモジュールSIS格子、R-SISおよびM-SIS格子から、優れたGKP(Gottesman-Kitaev-Preskill)符号(コンラッド、アイザート、セイファート)を構築する。これらの格子は格子ベースの暗号にとって不可欠である。我々の構成は距離$\sqrt{n/\pi e}$のGKP符号を生成する。これは、距離が$\Omega(\sqrt{n/q})、$が$n\le q^2/0.28$となるコンラッドらによるNTRUベースの構成と好意的に比較できる。コードとは異なり、コードにはデコーディングのスピードアップに使用可能な秘密鍵がありません。しかし、多くのパラメータ選択に対して、NTRUベースのコードと同様の復号結果が得られるような単純な復号アルゴリズムを提案する。 R-SIS と M-SIS の構成を用いて、簡単な復号アルゴリズムをほぼ線形時間で実行している。 Conrad, Eisert, Seifert の業績に続いて、GKP 符号の構成は、(定数 $\approx 1$) 最小距離 $(1/\sigma_{2n})^{1/2n}\approx \sqrt {\frac{n}{\pi e}}$,$\sigma_{2n}$ が 2n 次元単位球の体積であるような、明示的でランダムなシンプレクティック格子の構成から直接導かれる。この結果の前に、ブザーとサルナックはそのようなシンプレクティック格子の存在の非構成的証明を与えた。

論文の概要: Symplectic Lattices and GKP Codes -- Simple Randomized Constructions from Cryptographic Lattices

関連論文リスト