論文の概要: Proofs of Quantumness from Trapdoor Permutations
- arxiv url: http://arxiv.org/abs/2208.12390v1
- Date: Fri, 26 Aug 2022 01:11:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-29 14:42:57.786849
- Title: Proofs of Quantumness from Trapdoor Permutations
- Title（参考訳）: トラップドア置換による量子性証明
- Authors: Tomoyuki Morimae, Takashi Yamakawa
- Abstract要約: アリスとボブは古典的なチャンネルでしか通信しない。
アリスは古典的な確率時間計算しかできない。
Bobは古典的なセキュアな(フルドメイン)トラップドア置換から構築することができる。
- 参考スコア（独自算出の注目度）: 9.767030279324038
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Assume that Alice can do only classical probabilistic polynomial-time
computing while Bob can do quantum polynomial-time computing. Alice and Bob
communicate over only classical channels, and finally Bob gets a state
$|x_0\rangle+|x_1\rangle$ with some bit strings $x_0$ and $x_1$. Is it possible
that Alice can know $\{x_0,x_1\}$ but Bob cannot? Such a task, called {\it
remote state preparations}, is indeed possible under some complexity
assumptions, and is bases of many quantum cryptographic primitives such as
proofs of quantumness, (classical-client) blind quantum computing, (classical)
verifications of quantum computing, and quantum money. A typical technique to
realize remote state preparations is to use 2-to-1 trapdoor collision resistant
hash functions: Alice sends a 2-to-1 trapdoor collision resistant hash function
$f$ to Bob, and Bob evaluates it on superposition and measures the image. Bob's
post-measurement state is $|x_0\rangle+|x_1\rangle$, where $f(x_0)=f(x_1)=y$.
With the trapdoor, Alice can learn $\{x_0,x_1\}$, but due to the collision
resistance, Bob cannot. This Alice's advantage can be leveraged to realize the
quantum cryptographic primitives listed above. It seems that the collision
resistance is essential here. In this paper, surprisingly, we show that the
collision resistance is not necessary for a restricted case: we show that
(non-verifiable) remote state preparations of $|x_0\rangle+|x_1\rangle$ secure
against {\it classical} probabilistic polynomial-time Bob can be constructed
from classically-secure (full-domain) trapdoor permutations. Trapdoor
permutations are not likely to imply the collision resistance, because
black-box reductions from collision-resistant hash functions to trapdoor
permutations are known to be impossible. As an application of our result, we
construct proofs of quantumness from classically-secure (full-domain) trapdoor
permutations.
- Abstract（参考訳）: アリスは古典的確率多項式時間計算しかできないが、ボブは量子多項式時間演算しかできないと仮定する。
Alice と Bob は古典的なチャネルのみを通信し、Bob は状態 $|x_0\rangle+|x_1\rangle$ を得る。
Alice が $\{x_0,x_1\}$ を知っていても Bob はできないだろうか?
このようなタスクは「it remote state prepareds」と呼ばれ、いくつかの複雑性仮定の下で可能であり、量子性証明、(古典的クライアント)盲目量子コンピューティング、量子コンピューティングの(古典的)検証、量子マネーといった多くの量子暗号プリミティブの基盤である。
遠隔状態準備を実現する典型的な手法は、2対1のトラップドア衝突耐性ハッシュ関数を使用することである: aliceは2対1のトラップドア衝突耐性ハッシュ関数$f$をbobに送信し、bobは重ね合わせでそれを評価し、画像を測定する。
Bobのポスト測定状態は$|x_0\rangle+|x_1\rangle$であり、$f(x_0)=f(x_1)=y$である。
トラップドアで、アリスは$\{x_0,x_1\}$を学ぶことができるが、衝突抵抗のためボブは学べない。
このアリスの利点は、上述の量子暗号プリミティブを実現するのに利用できる。
ここでの耐衝突性は欠かせないようだ。
本稿では、制限された場合において衝突抵抗は必要ないことを示し、(検証不可能な)$|x_0\rangle+|x_1\rangle$ secure against {\it classical} 確率多項式時間Bobが古典的(フルドメイン)トラップドア置換から構築可能であることを示す。
トラップドア置換は、衝突耐性ハッシュ関数からトラップドア置換へのブラックボックス還元が不可能であることが知られているため、衝突抵抗を示唆しない。
この結果の応用として,古典的セキュア(フルドメイン)トラップドア置換法から量子性証明を構築する。
関連論文リスト
- Multicopy quantum state teleportation with application to storage and retrieval of quantum programs [1.151731504874944]
この研究は、ボブが修正を行うことができないシナリオにおいて、アリスとボブのテレポーテーションタスクを考える。
本稿では、量子プログラムの格納と検索の成功確率を高めるために、マルチコピー状態テレポーテーションプロトコルをどのように利用できるかを示す。
論文 参考訳（メタデータ） (2024-09-16T15:30:36Z) - Quantum advantage in a unified scenario and secure detection of
resources [55.2480439325792]
我々は、量子優位性を持つ異なるアプローチを研究するために単一のタスクを考える。
我々は、キュービット通信の全体プロセスにおける最適成功確率が、cbit通信のそれよりも高いことを示す。
論文 参考訳（メタデータ） (2023-09-22T23:06:20Z) - Commuting operations factorise [4.847980206213335]
ティレルソンはアリスとボブの入力と出力が古典的である場合を考えていた。
この場合、解は一般に負であるが、因子化が有限次元に存在することは知られている。
ここでは、完全量子の場合、すなわち可換作用素の分解において、同じホールドを示す。
論文 参考訳（メタデータ） (2023-08-10T18:00:00Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Two quantum algorithms for communication between spacelike separated
locations [0.7614628596146599]
我々は、アシラ量子ビットを用いた高次元ヒルベルト空間における状態判別によって超光通信が可能であると論じる。
本稿では,AliceとBobの2人の観測者間の通信のための状態判別による2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-16T06:54:22Z) - Quantum cryptography with classical communication: parallel remote state
preparation for copy-protection, verification, and more [125.99533416395765]
多くの暗号プリミティブは双方向のプロトコルであり、一方のパーティであるBobは完全な量子計算能力を持ち、もう一方のパーティであるAliceはランダムなBB84状態を送信するためにのみ必要である。
我々は、Bob が LWE 問題を効率的に解くことができないと仮定して、Alice が完全に古典的なプロトコルにどのように変換できるかを示す。
これは、(古典)アリスと(量子)ボブの間の全ての通信は古典的であるが、両者が古典的であれば不可能な暗号プリミティブを使用することができることを意味する。
論文 参考訳（メタデータ） (2022-01-31T18:56:31Z) - 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 advantage for computations with limited space [6.327095331866255]
我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。
我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
論文 参考訳（メタデータ） (2020-08-14T17:31:12Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。