論文の概要: Commitments are equivalent to one-way state generators
- arxiv url: http://arxiv.org/abs/2404.03220v1
- Date: Thu, 4 Apr 2024 06:06:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-05 15:43:35.612369
- Title: Commitments are equivalent to one-way state generators
- Title（参考訳）: コミットは一方通行のステートジェネレータと等価です
- Authors: Rishabh Batra, Rahul Jain,
- Abstract要約: ワンウェイ状態発生器 (OWSG) は古典的なワンウェイ関数の自然な量子アナログである。
我々は、$Oleft(fracnlog(n)right)$-copy OWSGs が $poly(n)$-copy OWSG および量子コミットメントに等しいことを示す。
- 参考スコア（独自算出の注目度）: 5.088702935364181
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We show that $O\left(\frac{n}{\log(n)}\right)$-copy OWSGs ($n$ represents the input length) are equivalent to $poly(n)$-copy OWSG and to quantum commitments. Since known results show that $o\left(\frac{n}{\log(n)}\right)$-copy OWSG cannot imply commitments, this shows that $O\left(\frac{n}{\log(n)}\right)$-copy OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of H\r{a}stad, Impagliazzo, Levin and Luby [HILL], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL]. Since we do not argue conditioned on the output of the one-way function, our construction and analysis are arguably simpler and may be of independent interest.
- Abstract（参考訳）: ワンウェイ状態発生器 (OWSG) は古典的なワンウェイ関数の自然な量子アナログである。
我々は、$O\left(\frac{n}{\log(n)}\right)$-copy OWSGs(n$は入力長を表す)が$poly(n)$-copy OWSGと等価であり、量子コミットメントに等しいことを示す。
既知の結果は、$o\left(\frac{n}{\log(n)}\right)$-copy OWSG がコミットメントを示唆できないことを示しているので、$O\left(\frac{n}{\log(n)}\right)$-copy OWSG がコミットメントを得ることのできる最も弱い OWSG であることを示している。
H\r{a}stad, Impagliazzo, Levin, Luby [HILL] は古典的片方向関数 (OWF) から古典的擬似ランダム生成子 (PRG) を得たが、重要な修正を加えた。
我々の構成は、古典的な場合に適用すると、[HILL]が提供する構成の代替となる。
片方向関数の出力に条件づけられた議論はしないので、我々の構成と解析は間違いなく単純であり、独立した関心を持つかもしれない。
関連論文リスト
- Pseudorandom Function-like States from Common Haar Unitary [1.0067421338825544]
古典的にアクセス可能な適応型セキュアPRFSGを量子ハール乱数オラクル(QHRO)モデルで構築する。
我々のPRFSG構造は、単一の置換に基づく古典的な EvenMansour 暗号に似ており、無制限のクエリに対して安全である。
論文 参考訳（メタデータ） (2024-11-05T15:48:27Z) - Quantum Unpredictability [8.093227427119325]
予測不能状態発生器(UPSG)の量子アナログを導入する。
UPSGは擬似乱数関数(PRF)の量子アナログである擬似乱数関数様状態発生器(PRFS)によって暗示される
その結果,多くの応用において,量子擬似ランダム性よりも量子的不予測性が十分であることが示唆された。
論文 参考訳（メタデータ） (2024-05-07T07:19:25Z) - A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。
我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
論文 参考訳（メタデータ） (2024-01-25T17:13:51Z) - Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
量子世界と古典世界における擬似ランダム性の概念の関連について研究する。
量子擬似乱数発生器(QPRGs)と呼ばれる擬似乱数発生器の自然変種は対数出力長PSRGsの存在に基づいていることを示す。
また、擬似乱数関数のような状態生成器と擬似乱数関数の関係についても検討する。
論文 参考訳（メタデータ） (2023-06-09T01:16:58Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳（メタデータ） (2022-10-13T03:55:04Z) - One-Wayness in Quantum Cryptography [9.09597656634436]
本研究では,一方向関数の量子アナログである一方向状態発生器(OWSG)の特性について検討する。
量子デジタル署名はOWSGと等価であることを示す。
我々は、秘密に検証可能で統計的に可逆なOWSGと呼ばれるOWSGの変種を紹介する。
論文 参考訳（メタデータ） (2022-10-07T08:21:21Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳（メタデータ） (2022-05-07T03:15:15Z) - Commitment capacity of classical-quantum channels [70.51146080031752]
古典的量子チャネルに対するコミットメント能力の様々な概念を定義する。
条件エントロピーの観点から上界と下界のマッチングを証明した。
論文 参考訳（メタデータ） (2022-01-17T10:41:50Z) - Coherent randomized benchmarking [68.8204255655161]
独立サンプルではなく,異なるランダム配列の重ね合わせを用いることを示す。
これは、ベンチマーク可能なゲートに対して大きなアドバンテージを持つ、均一でシンプルなプロトコルにつながることを示す。
論文 参考訳（メタデータ） (2020-10-26T18:00:34Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳（メタデータ） (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。