論文の概要: The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head

• arxiv url: http://arxiv.org/abs/2507.15377v1
• Date: Mon, 21 Jul 2025 08:33:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-22 20:51:32.322591
• Title: The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head
• Title（参考訳）: 行列部分符号等価問題とそのMPC-in-the-Headによる署名への応用
• Authors: Magali Bardet, Charles Brion, Philippe Gaborit, Mercedes Haiech, Romaric Neveu,
• Abstract要約: 本稿では,マトリックスサブコード等価問題とマトリックスコード置換カーネル問題という2つの新しい問題を紹介する。 我々は、MPCitHパラダイムをシグネチャスキームの構築に適用する。 署名サイズは$approx$4 800 Bytesで、公開キーは$approx$275 Bytesです。
• 参考スコア（独自算出の注目度）: 2.123778388986574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nowadays, equivalence problems are widely used in cryptography, most notably to establish cryptosystems such as digital signatures, with MEDS, LESS, PERK as the most recent ones. However, in the context of matrix codes, only the code equivalence problem has been studied, while the subcode equivalence is well-defined in the Hamming metric. In this work, we introduce two new problems: the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem, to which we apply the MPCitH paradigm to build a signature scheme. These new problems, closely related to the Matrix Code Equivalence problem, ask to find an isometry given a code $C$ and a subcode $D$. Furthermore, we prove that the Matrix Subcode Equivalence problem reduces to the Hamming Subcode Equivalence problem, which is known to be NP-Complete, thus introducing the matrix code version of the Permuted Kernel Problem. We also adapt the combinatorial and algebraic algorithms for the Matrix Code Equivalence problem to the subcode case, and we analyze their complexities. We find with this analysis that the algorithms perform much worse than in the code equivalence case, which is the same as what happens in the Hamming metric. Finally, our analysis of the attacks allows us to take parameters much smaller than in the Matrix Code Equivalence case. Coupled with the effectiveness of \textit{Threshold-Computation-in-the-Head} or \textit{VOLE-in-the-Head}, we obtain a signature size of $\approx$ 4 800 Bytes, with a public key of $\approx$ 275 Bytes. We thus obtain a reasonable signature size, which brings diversity in the landscape of post-quantum signature schemes, by relying on a new hard problem. In particular, this new signature scheme performs better than SPHINCS+, with a smaller size of public key + signature. Our signature compares also well with other signature schemes: compared to MEDS, the signature is smaller, and we reduced the size of the sum of signature and public key by a factor close to 5. We also obtain a signature size that is almost half the size of the CROSS signature scheme.
• Abstract（参考訳）: 現在、同値問題は暗号に広く使われており、特にMEDS、LESS、PERKが最新のものとなっている。 しかし、行列符号の文脈では、符号等価性の問題のみが研究されており、サブコード等価性はハミング計量でよく定義されている。 本稿では,MPCitH パラダイムをシグネチャスキーム構築に応用した Matrix Subcode Equivalence Problem と Matrix Code Permuted Kernel Problem の2つの新しい問題を紹介する。 これらの新しい問題はMatrix Code Equivalence問題と密接に関連しており、コード$C$とサブコード$D$が与えられた等尺を求める。 さらに,行列部分符号等価問題は,NP-Completeと呼ばれるハミング部分符号等価問題に還元され,置換カーネル問題の行列符号バージョンが導入された。 また、行列符号等価問題に対する組合せおよび代数的アルゴリズムをサブコードケースに適用し、それらの複雑さを解析する。 この分析により、アルゴリズムはハミング計量で起こるのと同じコード等価性の場合よりもはるかにパフォーマンスが悪くなっていることが分かる。 最後に、攻撃の分析により、Matrix Code Equivalenceの場合よりもパラメータをはるかに小さくすることができる。 textit{Threshold-Computation-in-the-Head} や \textit{VOLE-in-the-Head} の有効性と組み合わせて、$\approx$ 4 800 Bytes の署名サイズと $\approx$ 275 Bytes の公開キーを得る。 そこで我々は,新しい難題に頼って,量子後シグネチャスキームの景観に多様性をもたらす,合理的なシグネチャサイズを得る。 特に、この新しいシグネチャスキームは、公開鍵+シグネチャの小さいSPHINCS+よりもパフォーマンスが良い。 私たちのシグネチャは他のシグネチャスキームとよく似ています。MEDSと比較してシグネチャは小さく、シグネチャと公開キーの合計のサイズを5に近い因子で減らしました。 また、CROSSシグネチャスキームの約半分の大きさのシグネチャサイズを得る。

関連論文リスト

• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  量子コンピュータはShorのアルゴリズムを使って最新の暗号システムを破ることができる。 我々はまず、量子攻撃に対して安全とされるコードベースのスキームであるMcEliece暗号システムについて検討する。 次に,最短ベクトル問題を解くことの難しさを基礎とした格子型システムNTRUについて検討する。
  論文  参考訳（メタデータ） (2025-05-06T03:42:38Z)
• Quantum advantage from soft decoders [0.7728149002473877]
  最適多項式補間法(OPI)問題におけるいくつかのインスタンス化の改善について述べる。 我々の結果は自然で説得力のある復号問題をもたらし、量子的優位性を持っていると信じている。 本稿では,Regevのリダクションの設定にデコーダを利用できるように,シンドロームからコセットサンプリング問題への新たなリダクションを提案する。
  論文  参考訳（メタデータ） (2024-11-19T15:12:03Z)
• Encodings of the weighted MAX k-CUT on qubit systems [0.0]
  本稿では,重み付きMAX k-CUT問題の量子ビットシステム上での符号化法について検討する。 各種符号化方式について検討し,これらの手法の有効性について検討する。 重み付きおよび非重み付きグラフインスタンスの数値シミュレーションは、これらの符号化方式の有効性を実証する。
  論文  参考訳（メタデータ） (2024-11-13T13:21:35Z)
• MinRank Gabidulin encryption scheme on matrix codes [6.471199354529622]
  行列符号とMinRank問題に対するMcElieceスキームとNiederreiterフレームの一般化を提案する。 我々の新しいアプローチは、古典的なMcEliece方式よりも、暗号文と公開鍵とのトレードオフを良くすることを可能にする。
  論文  参考訳（メタデータ） (2024-05-26T12:04:01Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。 これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。 本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
  論文  参考訳（メタデータ） (2024-02-06T18:59:30Z)
• VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme [0.8643517734716606]
  多変量方程式の解法に基づく量子後デジタルシグネチャアルゴリズムを提案する。 我々は、慎重に選択されたパラメータが、既存のすべての最先端攻撃に抵抗できることを示します。 これは、同様のセキュリティを持つ全ての既知の量子後シグネチャスキームの中で最小のシグネチャサイズである。
  論文  参考訳（メタデータ） (2023-12-15T04:58:10Z)
• Deep Learning Assisted Multiuser MIMO Load Modulated Systems for Enhanced Downlink mmWave Communications [68.96633803796003]
  本稿では, マルチユーザ負荷変調アレイ (MU-LMA) に着目し, マイクロウェーブ (mmWave) マルチインプット・マルチアウトプット (MIMO) システムにおいて, マルチユーザ負荷変調アレイ (MU-LMA) の小型化とコスト削減を図っている。 ダウンリンクMU-LMAの既存のプリコーディングアルゴリズムは、自由度と複雑なシステム構成の低下に悩まされるサブアレイ構造化(SAS)送信機に依存している。 本稿では,FAS (Full-array Structured) 送信機を用いたMU-LMAシステムを提案し,それに応じて2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-11-08T08:54:56Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。 RM符号は制限されたレートのみを許容する。 効率的なデコーダは、RM符号に対して有限長で利用可能である。
  論文  参考訳（メタデータ） (2023-01-16T04:11:14Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• Conservation laws and quantum error correction: towards a generalised matching decoder [2.1756081703276]
  原型量子低密度パリティチェック符号である表面符号の復号アルゴリズムについて検討する。 デコーダは、表面符号安定化素子間の物質化された対称性によって生じる基盤構造を利用する。 本研究では,特定の特性を持つ符号に対して,最小重み付き完全整合デコーダを構築する方式を提案する。
  論文  参考訳（メタデータ） (2022-07-13T18:00:00Z)
• Sparsifying Parity-Check Matrices [60.28601275219819]
  パリティチェック行列における1項目数を最小化する問題を考える。 最大型(ML)復号法では、PCMの復号に要する時間と直接関連している。 コード自体ではなく,PCMを変更する単純な行列行操作を提案する。
  論文  参考訳（メタデータ） (2020-05-08T05:51:40Z)

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

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