論文の概要: An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes

• arxiv url: http://arxiv.org/abs/2409.08774v1
• Date: Fri, 13 Sep 2024 12:31:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-16 16:39:02.428040
• Title: An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes
• Title（参考訳）: 公開鍵暗号システムと署名方式に対する$p$-adicの攻撃
• Authors: Chi Zhang,
• Abstract要約: 本稿では,局所フィールドにおけるLVPアルゴリズムの改良について述べる。 このアルゴリズムを用いて上記のスキームを攻撃し、任意のメッセージをフォージし、暗号文を復号化できるようにします。 これらのスキームは壊れているが、この研究は、$p$-adic 格子が暗号プリミティブの構築に適さないという意味ではない。
• 参考スコア（独自算出の注目度）: 3.444630356331766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lattices have many significant applications in cryptography. In 2021, the $p$-adic signature scheme and public-key encryption cryptosystem were introduced. They are based on the Longest Vector Problem (LVP) and the Closest Vector Problem (CVP) in $p$-adic lattices. These problems are considered to be challenging and there are no known deterministic polynomial time algorithms to solve them. In this paper, we improve the LVP algorithm in local fields. The modified LVP algorithm is a deterministic polynomial time algorithm when the field is totally ramified and $p$ is a polynomial in the rank of the input lattice. We utilize this algorithm to attack the above schemes so that we are able to forge a valid signature of any message and decrypt any ciphertext. Although these schemes are broken, this work does not mean that $p$-adic lattices are not suitable in constructing cryptographic primitives. We propose some possible modifications to avoid our attack at the end of this paper.
• Abstract（参考訳）: 格子は暗号に多くの重要な応用がある。 2021年、$p$-adicシグネチャスキームと公開鍵暗号システムが導入された。 それらは、$p$進格子のLongest Vector Problem (LVP) とClosest Vector Problem (CVP) に基づいている。 これらの問題は困難であると考えられており、解くための決定論的多項式時間アルゴリズムは知られていない。 本稿では,局所フィールドにおけるLVPアルゴリズムの改良について述べる。 修正LVPアルゴリズムは、フィールドが完全に分岐し、$p$が入力格子のランクの多項式であるとき、決定論的多項式時間アルゴリズムである。 このアルゴリズムを用いて上記のスキームを攻撃し、任意のメッセージの有効なシグネチャをフォージし、暗号文を復号化できるようにします。 これらのスキームは壊れているが、この研究は、$p$-adic 格子が暗号プリミティブの構築に適さないという意味ではない。 本論文の最後には,攻撃を避けるため,いくつかの可能性のある修正を提案する。

関連論文リスト

• Implementation of Entropically Secure Encryption: Securing Personal Health Data [0.704590071265998]
  Entropically Secure Encryption (ESE) はOne-Time Padに短いキーで無条件のセキュリティを提供する。 バルク暗号のためのESEの実装について述べる。
  論文  参考訳（メタデータ） (2024-04-04T12:07:33Z)
• Homomorphic Encryption Based on Post-Quantum Cryptography [0.0]
  本研究では,量子後暗号(QCP)に基づく同型暗号手法を提案する。 これは、量子コンピューティング攻撃を避けるためのコードベースの暗号法に基づく同型暗号化機能を含んでいる。 その結果,提案手法の暗号化時間は,他の暗号手法よりも短いことがわかった。
  論文  参考訳（メタデータ） (2024-02-22T00:38:23Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH [5.398058794903461]
  自己同型環問題(英語版)(IsERP)は、超特異曲線の間の同型写像の余領域の自己同型環を計算することを要求する。 次数が奇数で、多くの素因子が$O(loglog p)=$である等質性に対して、IsERPを解くための新しい量子時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2023-05-31T14:30:32Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。 我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
  論文  参考訳（メタデータ） (2023-03-15T15:00:20Z)
• Algorithms for Weighted Pushdown Automata [118.67634716230025]
  重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。 WPDA上で直接動作する新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-13T10:21:31Z)
• Cryptanalysis of Three Quantum Money Schemes [1.5254598796939927]
  3つの公開鍵量子マネースキームのセキュリティ仮定について検討する。 困難問題から線形代数問題への時間量子還元を与える。
  論文  参考訳（メタデータ） (2022-05-21T02:16:46Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Lattice sieving via quantum random walks [0.0]
  格子ベースの暗号は、量子後暗号の主要な提案の一つである。 最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。 我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-12T11:59:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。