論文の概要: 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 次元単位球の体積であるような、明示的でランダムなシンプレクティック格子の構成から直接導かれる。
この結果の前に、ブザーとサルナックはそのようなシンプレクティック格子の存在の非構成的証明を与えた。
関連論文リスト
- On the Maximum Toroidal Distance Code for Lattice-Based Public-Key Cryptography [3.8559042217241566]
格子型公開鍵暗号(PKE)のための最大トロイダル距離(MTD)符号を提案する。
MTDコードは、IACR CHES 2025で最近導入されたマイナーコードの変種であることを示す。
論文 参考訳（メタデータ） (2026-01-13T11:27:15Z) - Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks [18.20811830109862]
我々は、線形次元と距離が非クリフォードゲートをサポートする最初の既知の量子符号を構築した。
これらの符号に対する効率的な復号化アルゴリズムを設計する。
我々の結果は、関数を変換への部分アクセスから再構成するPronyの手法の新たな一般化と見なすことができる。
論文 参考訳（メタデータ） (2025-10-08T09:27:41Z) - Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes [0.9208007322096533]
我々は、長さ$N$、次元$Kgeq N1-epsilon$、距離$Dgeq N1/r/namepoly(log N)$、安定化器重量$wleqoperatorname(log N)$をサポートする量子LDPC符号の明示的な無限族を構築する。
論文 参考訳（メタデータ） (2024-10-18T17:52:59Z) - Unifying error-correcting code/Narain CFT correspondences via lattices over integers of cyclotomic fields [0.0]
シンクロトミック場$Q(zeta_p)$$(zeta_p=efrac2pi ip)$ for general prime $pgeq 3$。
このコードラッチ構造は、三次符号に対するコンストラクションA$_C$や、(後述の一般化後の)バイナリコードのためのコンストラクションAのような、よりよく知られたものの一般化である。
論文 参考訳（メタデータ） (2024-10-16T12:08:04Z) - Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates [23.22566380210149]
我々は、任意の素数次元$q$のクォーディット上の$CCZ$ゲートをサポートする量子符号を構築する。
このような線形次元と距離で知られている唯一の構造は、成長するアルファベットサイズ$q$を必要とした。
論文 参考訳（メタデータ） (2024-08-17T16:54:51Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass [72.07642648108849]
Superposed Decodingは、1つの自己回帰推論パスのコストで$k$のドラフトを生成する新しい復号アルゴリズムである。
Superposed Decodingは、他のデコード戦略と組み合わせることで、推論時間計算のスケーリング時に普遍的なカバレッジが向上する。
論文 参考訳（メタデータ） (2024-05-28T17:40:48Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Divisible Codes for Quantum Computation [0.6445605125467572]
可分符号は、符号語重みが1より大きい共通の因子を共有する性質によって定義される。
本稿では、論理ゲートによって変換される量子情報を保護するために、それらがどのように使用できるかを検討する。
論文 参考訳（メタデータ） (2022-04-27T20:18:51Z) - On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。
このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
論文 参考訳（メタデータ） (2021-10-07T05:25:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。