論文の概要: The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and
More
- arxiv url: http://arxiv.org/abs/2003.05207v3
- Date: Mon, 7 Mar 2022 11:53:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 11:18:16.136317
- Title: The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and
More
- Title（参考訳）: 計測・再プログラム技術2.0:多言語フィアットシャミールなど
- Authors: Jelle Don, Serge Fehr and Christian Majenz
- Abstract要約: 我々は、量子ランダムオラクルモデル(QROM)における$Sigma$-protocolsのフィアット・シャミール変換の安全性に関するDon, Fehr, Majenz, Schaffnerの業績を再考する。
我々は、Grover-search ベースの攻撃を通じて、$Sigma$-protocols の Fiat-Shamir 変換に対する Don らの二次的セキュリティ損失が、小さな定数係数まで最適であることを示す。
- 参考スコア（独自算出の注目度）: 9.399840807973543
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit recent works by Don, Fehr, Majenz and Schaffner and by Liu and
Zhandry on the security of the Fiat-Shamir transformation of $\Sigma$-protocols
in the quantum random oracle model (QROM). Two natural questions that arise in
this context are: (1) whether the results extend to the Fiat-Shamir
transformation of multi-round interactive proofs, and (2) whether Don et al.'s
$O(q^2)$ loss in security is optimal.
Firstly, we answer question (1) in the affirmative. As a byproduct of solving
a technical difficulty in proving this result, we slightly improve the result
of Don et al., equipping it with a cleaner bound and an even simpler proof. We
apply our result to digital signature schemes showing that it can be used to
prove strong security for schemes like MQDSS in the QROM. As another
application we prove QROM-security of a non-interactive OR proof by Liu, Wei
and Wong.
As for question (2), we show via a Grover-search based attack that Don et
al.'s quadratic security loss for the Fiat-Shamir transformation of
$\Sigma$-protocols is optimal up to a small constant factor. This extends to
our new multi-round result, proving it tight up to a factor that depends on the
number of rounds only, i.e. is constant for any constant-round interactive
proof.
- Abstract（参考訳）: 我々は、don, fehr, majenz, schaffner と liu と zhandry によるquantum random oracle model (qrom) における $\sigma$-protocols の fiat-shamir 変換のセキュリティに関する最近の研究を再検討する。
この文脈で生じる2つの自然な疑問は、(1)結果が多ラウンド対話的証明のフィアット・シャミル変換に拡張されるかどうか、(2)don et al.の$o(q^2)$のセキュリティ損失が最適かどうかである。
まず,肯定的な質問(1)を答える。
この結果を証明するための技術的困難を解く副産物として、我々はDonらの結果をわずかに改善し、よりクリーンな境界とさらに単純な証明を備える。
本稿では,QROMにおけるMQDSSのようなスキームの強力なセキュリティを証明するために,デジタルシグネチャスキームに適用する。
別の応用として、Liu, Wei and Wong による非インタラクティブOR証明の QROM-セキュリティを証明する。
質問 (2) に関して、Donらによる$\Sigma$-protocols の Fiat-Shamir 変換に対する2次セキュリティ損失は、小さな定数係数まで最適であることを示す。
これは、新しいマルチラウンド結果に拡張され、ラウンド数のみに依存する要因、すなわち、任意のコンスタントラウンドインタラクティブな証明に対して定数であることが証明されます。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Evaluating the security of CRYSTALS-Dilithium in the quantum random
oracle model [2.486161976966064]
我々は、量子ランダムオラクルモデル(QROM)におけるMLWEからの還元によるSelfTargetMSISの硬さの最初の証明を提供する。
MSIS問題から派生した特定のハッシュ関数が崩壊していることの証明である。
Kiltz, Lyubashevsky, Schaffner の以前の研究と比較すると、我々の証明は q = 1 mod 2n という条件で適用できるという利点がある。
論文 参考訳（メタデータ） (2023-12-27T15:56:27Z) - Verifiable Quantum Advantage without Structure [15.701707809084716]
ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換える。
以上の結果の最小限のインスタンス化が可能である。
論文 参考訳（メタデータ） (2022-04-05T08:58:24Z) - Failing gracefully: Decryption failures and the Fujisaki-Okamoto
transform [3.437656066916039]
復号化失敗の発見に関連する2つのセキュリティゲームを紹介する。
1つは、公開鍵を使用して復号化失敗を見つけるという、計算的に難しいタスクをキャプチャする。
他方は、キー非依存の障害に対してランダムなオラクルを探索する統計的に難しいタスクを捉えている。
論文 参考訳（メタデータ） (2022-03-18T22:39:08Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
論文 参考訳（メタデータ） (2020-12-30T18:03:56Z) - Tight adaptive reprogramming in the QROM [4.234367850767171]
適応的な再プログラム性は、ランダムなオラクルが再プログラムされたかどうかを識別する上で、逆の優位性に縛られることを証明することによって実現可能であることを示す。
提案手法は,3つのQROMアプリケーションにおけるROMの利点を回復することを示す。
論文 参考訳（メタデータ） (2020-10-28T17:38:25Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳（メタデータ） (2020-09-29T08:41:53Z) - Is Multihop QA in DiRe Condition? Measuring and Reducing Disconnected
Reasoning [50.114651561111245]
モデルは、しばしば、複数のサポート事実をまたいで情報を接続することなく、正しい回答を生成するためにデータセットアーティファクトを利用する。
我々は、支持事実のサブセットにまたがる不連結推論のような望ましくない振る舞いを定式化する。
実験によると、読書理解設定においてマルチホップQAがあまり進歩していないことが示唆されている。
論文 参考訳（メタデータ） (2020-05-02T11:01:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。