論文の概要: On the (In)security of optimized Stern-like signature schemes
- arxiv url: http://arxiv.org/abs/2408.15843v1
- Date: Wed, 28 Aug 2024 15:03:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-29 15:40:56.144737
- Title: On the (In)security of optimized Stern-like signature schemes
- Title（参考訳）: 最適化されたスターン様シグネチャスキームの(In)セキュリティについて
- Authors: André Chailloux, Simona Etinski,
- Abstract要約: スターンのシグネチャスキームの重要な最適化は、ランダムではなく擬ランダムベクトルと置換を生成することである。
いくつかのパラメータに対して、この最適化を悪用し、時間内にそのスキームを壊す攻撃が存在することを示す。
0,12lambda$に$saltをスキームに追加し、擬似ランダム文字列の生成方法を少し変更することで、我々の攻撃が機能しないだけでなく、どんな攻撃に対しても、このスキームは$lambda$ bitsのセキュリティを保持することを証明します。
- 参考スコア（独自算出の注目度）: 0.5755004576310334
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stern's signature scheme is a historically important code-based signature scheme. A crucial optimization of this scheme is to generate pseudo-random vectors and a permutation instead of random ones, and most proposals that are based on Stern's signature use this optimization. However, its security has not been properly analyzed, especially when we use deterministic commitments. In this article, we study the security of this optimization. We first show that for some parameters, there is an attack that exploits this optimization and breaks the scheme in time $O(2^{\frac{\lambda}{2}})$ while the claimed security is $\lambda$ bits. This impacts in particular the recent Quasy-cyclic Stern signature scheme [BGMS22]. Our second result shows that there is an efficient fix to this attack. By adding a string $salt \in \{0,1\}^{2\lambda}$ to the scheme, and changing slightly how the pseudo-random strings are generated, we prove not only that our attack doesn't work but that for any attack, the scheme preserves $\lambda$ bits of security, and this fix increases the total signature size by only $2\lambda$ bits. We apply this construction to other optimizations on Stern's signature scheme, such as the use of Lee's metric or the use of hash trees, and we show how these optimizations improve the signature length of Stern's signature scheme.
- Abstract（参考訳）: スターンのシグネチャスキームは歴史的に重要なコードベースのシグネチャスキームである。
このスキームの重要な最適化は、ランダムではなく擬ランダムベクトルと置換を生成することである。
しかし、特に決定論的コミットメントを使用する場合、そのセキュリティは適切に分析されていない。
本稿では,この最適化の安全性について検討する。
まず、いくつかのパラメータに対して、この最適化を利用して、要求されるセキュリティが$\lambda$ bitsである間に、時間$O(2^{\frac{\lambda}{2}})でスキームを壊す攻撃があることを示します。
これは特に最近のQuasy-cyclic Stern signature scheme[BGMS22]に影響を及ぼす。
2つ目の結果は、この攻撃に効果的な修正があることを示しています。
このスキームに$salt \in \{0,1\}^{2\lambda}$を追加することで、擬似ランダム文字列の生成方法がわずかに変わることで、我々の攻撃が機能しないだけでなく、どんな攻撃に対しても$$\lambda$ bitsのセキュリティを保ち、この修正によって署名の総サイズがわずか2\lambda$ bitsになる。
この構成を、リー計量の使用やハッシュツリーの使用など、スターンのシグネチャスキームに関する他の最適化に適用し、これらの最適化がスターンのシグネチャスキームのシグネチャ長をどのように改善するかを示す。
関連論文リスト
- An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes [3.444630356331766]
本稿では,局所フィールドにおけるLVPアルゴリズムの改良について述べる。
このアルゴリズムを用いて上記のスキームを攻撃し、任意のメッセージをフォージし、暗号文を復号化できるようにします。
これらのスキームは壊れているが、この研究は、$p$-adic 格子が暗号プリミティブの構築に適さないという意味ではない。
論文 参考訳（メタデータ） (2024-09-13T12:31:57Z) - RANDAO-based RNG: Last Revealer Attacks in Ethereum 2.0 Randomness and a Potential Solution [0.5917100081691199]
RANDAO 2.0はスケーラビリティ、スループット、セキュリティを改善するための大きなアップグレードである。
LRA(Last Revealer Attack)と呼ばれる脆弱性は、このスキームのランダム性を損なう。
LRAを緩和するために,Shamir's Secret Sharing (SSS) を用いたRANDAO方式を提案する。
論文 参考訳（メタデータ） (2024-03-14T16:28:33Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
我々は $bot$-PRG と $bot$-PRF の新たな定義を導入する。
私たちの主な応用は、古典的な公開鍵と署名を備えた(量子)デジタル署名スキームです。
論文 参考訳（メタデータ） (2023-11-01T20:54:50Z) - Transferable Sparse Adversarial Attack [62.134905824604104]
オーバーフィッティング問題を緩和するジェネレータアーキテクチャを導入し、転送可能なスパース対逆例を効率的に作成する。
提案手法は,他の最適化手法よりも700$times$高速な推論速度を実現する。
論文 参考訳（メタデータ） (2021-05-31T06:44:58Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z) - SMYRF: Efficient Attention using Asymmetric Clustering [103.47647577048782]
本稿では,注目度を近似する新しいタイプのバランスクラスタリングアルゴリズムを提案する。
SMYRFは、再トレーニングすることなく、高密度の注意層をドロップインで置き換えることができる。
SMYRFは,訓練前後の集中的注意と相互に使用できることが示唆された。
論文 参考訳（メタデータ） (2020-10-11T18:49:17Z) - Black-Box Certification with Randomized Smoothing: A Functional
Optimization Based Framework [60.981406394238434]
本稿では,非ガウス雑音とより一般的な攻撃に対する対向的認証の一般的な枠組みを提案する。
提案手法は,従来の手法よりも優れた認証結果を得るとともに,ランダム化スムーズな認証の新たな視点を提供する。
論文 参考訳（メタデータ） (2020-02-21T07:52:47Z) - Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。
我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
論文 参考訳（メタデータ） (2020-02-19T15:41:18Z) - Randomized Smoothing of All Shapes and Sizes [29.40896576138737]
最適」ノルムの適切な概念に対して、任意の「ニッチ」ノルムに対する最適な滑らか化はノルムの *Wulff Crystal* によって与えられるレベル集合を持つことを示す。
ここでは、*バナッハ空間コタイプ*の理論を通して、現在のランダム化平滑化技術に基本的な限界を示す。
論文 参考訳（メタデータ） (2020-02-19T11:41:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。