論文の概要: Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of
a Split-key PRF
- arxiv url: http://arxiv.org/abs/2206.08132v3
- Date: Tue, 13 Sep 2022 18:53:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-09 04:45:13.551399
- Title: Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of
a Split-key PRF
- Title（参考訳）: 適応型と静的なマルチオーラアルゴリズムと分割鍵PRFの量子セキュリティ
- Authors: Jelle Don and Serge Fehr and Yu-Hsuan Huang
- Abstract要約: 本論文の前半では,複数のオーラクルを適応的にクエリ可能な任意のオーラクルアルゴリズムを変換する汎用コンパイラについて述べる。
論文の後半では、Giacon, Heuer, Poettering が提案した非常に効率的なハッシュベースのスプリットキー PRF の安全性を示すために、コンパイラを使用します。
- 参考スコア（独自算出の注目度）: 7.281231789947833
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the first part of the paper, we show a generic compiler that transforms
any oracle algorithm that can query multiple oracles adaptively, i.e., can
decide on which oracle to query at what point dependent on previous oracle
responses, into a static algorithm that fixes these choices at the beginning of
the execution. Compared to naive ways of achieving this, our compiler controls
the blow-up in query complexity for each oracle individually, and causes a very
mild blow-up only.
In the second part of the paper, we use our compiler to show the security of
the very efficient hash-based split-key PRF proposed by Giacon, Heuer and
Poettering (PKC 2018), in the quantum random-oracle model. Using a split-key
PRF as the key-derivation function gives rise to a secure KEM combiner. Thus,
our result shows that the hash-based construction of Giacon et al. can be
safely used in the context of quantum attacks, for instance to combine a
well-established but only classically-secure KEM with a candidate KEM that is
believed to be quantum-secure.
Our security proof for the split-key PRF crucially relies on our
adaptive-to-static compiler, but we expect our compiler to be useful beyond
this particular application. Indeed, we discuss a couple of other, known
results from the literature that would have profitted from our compiler, in
that these works had to go though serious complications in order to deal with
adaptivity.
- Abstract（参考訳）: 論文の前半では、複数のオラクルを適応的にクエリできる任意のオラクルアルゴリズム、すなわち、前のオラクル応答に依存するどのポイントでどのオラクルをクエリするかを決定できる汎用コンパイラを、実行開始時にこれらの選択を修正する静的アルゴリズムに変換する。
これを実現するナイーブな方法と比較して、私たちのコンパイラは各オラクルのクエリ複雑さのブローアップを個別に制御し、非常に穏やかなブローアップのみを引き起こします。
論文の第2部では、Giacon, Heuer and Poettering (PKC 2018) が提案した非常に効率的なハッシュベースのスプリットキー PRF の安全性を、量子乱数モデルで示すために、コンパイラを使用します。
鍵導出関数としてスプリットキー PRF を用いると、安全なKEM結合器が生まれる。
以上の結果から,yaconなどのハッシュベースの構成は,量子攻撃の文脈において,例えば,確立されているが古典的にセキュアなkemと,量子安全であると思われるkem候補を組み合わせることで,安全に使用できることが示された。
スプリットキーprfのセキュリティ証明は、当社のadaptive-to-staticコンパイラに依存していますが、コンパイラがこの特定のアプリケーションを超えて役立つことを期待しています。
実際、我々はコンパイラーから利益を得たであろう文献から得られたいくつかの既知の結果について議論し、これらの研究は適応性に対処するために深刻な合併症を伴わなければならなかった。
関連論文リスト
- (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
微分可能性(Indifferentiability)は、理想的なオブジェクトのセキュリティを分析するための暗号パラダイムである。
その強さにもかかわらず、前処理攻撃に対するセキュリティを提供する無差別性は知られていない。
本稿では、構成可能であるだけでなく、任意の事前計算を考慮に入れた微分可能性の強化を提案する。
論文 参考訳（メタデータ） (2024-10-22T00:41:47Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。
我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
論文 参考訳（メタデータ） (2024-01-25T17:13:51Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳（メタデータ） (2022-05-07T03:15:15Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - Verified Compilation of Quantum Oracles [10.942063551929914]
VQOは高保証量子プログラミングフレームワークである。
OQASMはオラクル量子アセンブリ言語である。
VQOのバージョンはクイッパーによって作られた(キュービット数とゲート数の両方で)オーラクルと同等かそれ以上であった。
論文 参考訳（メタデータ） (2021-12-13T14:36:36Z) - Coherent randomized benchmarking [68.8204255655161]
独立サンプルではなく,異なるランダム配列の重ね合わせを用いることを示す。
これは、ベンチマーク可能なゲートに対して大きなアドバンテージを持つ、均一でシンプルなプロトコルにつながることを示す。
論文 参考訳（メタデータ） (2020-10-26T18:00:34Z) - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work [10.43571631715192]
我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。
本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
論文 参考訳（メタデータ） (2020-10-22T12:44:08Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳（メタデータ） (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。