論文の概要: Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared Entanglement

• arxiv url: http://arxiv.org/abs/2204.02265v2
• Date: Mon, 12 Sep 2022 14:26:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-18 05:28:44.529269
• Title: Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared Entanglement
• Title（参考訳）: Fiat-Shamir:共有絡みがあっても証明できない証明
• Authors: Fr\'ed\'eric Dupuis, Philippe Lamontagne, Louis Salvail
• Abstract要約: 任意の共有物理リソースの暗号能力について検討する。 これをCRQS(Common Reference Quantum State)モデルと呼び、よく知られたCommon Reference String(CRS)と類似している。 我々は、$n-minomega(lg n)$の場合、CRQSモデルにおけるWOTROの任意のプロトコルは(非効率な)敵によって攻撃可能であることを示す。
• 参考スコア（独自算出の注目度）: 0.3222802562733786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore the cryptographic power of arbitrary shared physical resources. The most general such resource is access to a fresh entangled quantum state at the outset of each protocol execution. We call this the Common Reference Quantum State (CRQS) model, in analogy to the well-known Common Reference String (CRS). The CRQS model is a natural generalization of the CRS model but appears to be more powerful: in the two-party setting, a CRQS can sometimes exhibit properties associated with a Random Oracle queried once by measuring a maximally entangled state in one of many mutually unbiased bases. We formalize this notion as a Weak One-Time Random Oracle (WOTRO), where we only ask of the $m$--bit output to have some randomness when conditioned on the $n$--bit input. We show that when $n-m\in\omega(\lg n)$, any protocol for WOTRO in the CRQS model can be attacked by an (inefficient) adversary. Moreover, our adversary is efficiently simulatable, which rules out the possibility of proving the computational security of a scheme by a black-box reduction to a cryptographic game assumption. On the other hand, we introduce a non-game quantum assumption for hash functions that implies WOTRO in the CRQ\$ model (where the CRQS consists only of EPR pairs). We first build a statistically secure WOTRO protocol where $m=n$, then hash the output. The impossibility of WOTRO has the following consequences. First, we show the black-box impossibility of a quantum Fiat-Shamir transform, extending the impossibility result of Bitansky et al. (TCC '13) to the CRQS model. Second, we show a black-box impossibility result for a strenghtened version of quantum lightning (Zhandry, Eurocrypt '19) where quantum bolts have an additional parameter that cannot be changed without generating new bolts.
• Abstract（参考訳）: 任意の共有物理リソースの暗号能力について検討する。 最も一般的なリソースは、プロトコルの実行開始時に、新しい絡み合った量子状態へのアクセスである。 これをCRQS(Common Reference Quantum State)モデルと呼び、よく知られたCommon Reference String(CRS)と類似しています。 CRQSモデルは、CRSモデルの自然な一般化であるが、より強力であるように見える: 二つの党構成では、CRQSは、互いに偏りのない多くの基底のうちの1つにおいて、最大に絡み合った状態を測定することによって、一度クエリされたランダムOracleに関連する性質を示すことがある。 我々は、この概念をWak One-Time Random Oracle (WOTRO) として定式化し、$m$-bitの出力だけを要求すれば、$n$-bitの入力で条件付けられたときにランダム性を持つ。 n-m\in\omega(\lg n)$の場合、crqsモデルにおけるwotroのプロトコルは(非効率な)敵に攻撃される。 さらに、我々の敵は効率的にシミュラブルであり、暗号ゲーム仮定へのブラックボックス還元によるスキームの計算安全性を証明する可能性を規定している。 一方、CRQ\$モデル(CRQS は EPR ペアのみからなる)における WOTRO を暗示するハッシュ関数に対して、非量子的な量子仮定を導入する。 最初に統計的にセキュアなWOTROプロトコルを構築し、$m=n$で出力をハッシュします。 WOTROの不可能性は以下の結果をもたらす。 まず,量子フィアット・シャミール変換のブラックボックス化不可能性を示し,ビタンスキーら (tcc '13) の不可能性結果をcrqsモデルに拡張する。 第2に、量子ボルトが新しいボルトを発生させずに変更できない追加パラメータを持つ量子稲妻(Zhandry, Eurocrypt '19)の強化版に対するブラックボックス不合理性結果を示す。

関連論文リスト

• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Certified Randomness from Quantum Supremacy [5.313318620422295]
  本稿では、暗号的に認証されたランダムビットを生成するような、短期量子デバイスのためのアプリケーションを提案する。 提案プロトコルは,ランダム回路サンプリングに基づいて,既存の「量子超越性」実験を再利用する。 我々のプロトコルの出力は、計算不能な敵に対しても予測不可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-02T23:28:31Z)
• Obfuscation of Pseudo-Deterministic Quantum Circuits [14.026980555435841]
  古典オラクルモデルにおいて擬似決定論的量子回路を難解化する方法を示す。 我々のオブファスケータは任意の入力に対して、量子状態$ketwidetildeQ$を繰り返し出力する。
  論文  参考訳（メタデータ） (2023-02-22T01:14:20Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  量子計算のための古典的簡潔な対話的引数(BQP)を構築する。 我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
  論文  参考訳（メタデータ） (2022-06-29T22:19:12Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  完全同型暗号方式として, 完全同型暗号方式を初めて構築する。 我々の主要な技術要素は、量子証明器が古典的検証器に量子状態の形でのLearning with Errors分布からのサンプルが削除されたことを納得させる対話的プロトコルである。
  論文  参考訳（メタデータ） (2022-03-03T10:07:32Z)
• 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)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。 我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
  論文  参考訳（メタデータ） (2020-11-05T05:40:05Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• 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)
• Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
  クライアントは、古典的なチャネルを使用して量子状態をリモートで準備する。 サブモジュールとして$RSP_CC$を採用することで生じるプライバシ損失は、不明である。 特定の$RSP_CC$プロトコルは、少なくともいくつかのコンテキストにおいて量子チャネルを置き換えることができることを示す。
  論文  参考訳（メタデータ） (2020-07-03T13:15:13Z)

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

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