論文の概要: Post-Quantum $\kappa$-to-1 Trapdoor Claw-free Functions from
Extrapolated Dihedral Cosets
- arxiv url: http://arxiv.org/abs/2211.16993v2
- Date: Fri, 21 Jul 2023 00:50:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-24 16:39:04.562114
- Title: Post-Quantum $\kappa$-to-1 Trapdoor Claw-free Functions from
Extrapolated Dihedral Cosets
- Title（参考訳）: 後量子$\kappa$-to-1 トラップドア爪のない外挿二面体コセット
- Authors: Xingyu Yan (1), Licheng Wang (2), Lize Gu (1), Ziyi Li (3), Jingwen
Suo (1) ((1) State Key Laboratory of Networking and Switching Technology,
Beijing University of Posts and Telecommunications, Beijing, 100876, China.
(2) School of Cyberspace Science and Technology, Beijing Institute of
Technology, Beijing, 100081, China. (3) State Key Laboratory of Information
Security, Institute of Information Engineering, University of Chinese Academy
of Sciences, Beijing, 100049, China.)
- Abstract要約: emphNohedral trapdoor claw-free function (NTCF) は、信頼性のない量子デバイスの動作を効率的に制限できる強力な量子後暗号ツールである。
本研究ではNTCF$2$をさらに拡張して,有界プレイメージサイズでハンファニーから1対1のトラップドア・クラッチフリーな関数を実現する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: \emph{Noisy trapdoor claw-free function} (NTCF) as a powerful post-quantum
cryptographic tool can efficiently constrain actions of untrusted quantum
devices. However, the original NTCF is essentially \emph{2-to-1} one-way
function (NTCF$^1_2$). In this work, we attempt to further extend the
NTCF$^1_2$ to achieve \emph{many-to-one} trapdoor claw-free functions with
polynomial bounded preimage size. Specifically, we focus on a significant
extrapolation of NTCF$^1_2$ by drawing on extrapolated dihedral cosets, thereby
giving a model of NTCF$^1_{\kappa}$ where $\kappa$ is a polynomial integer.
Then, we present an efficient construction of NTCF$^1_{\kappa}$ assuming
\emph{quantum hardness of the learning with errors (LWE)} problem. We point out
that NTCF can be used to bridge the LWE and the dihedral coset problem (DCP).
By leveraging NTCF$^1_2$ (resp. NTCF$^1_{\kappa}$), our work reveals a new
quantum reduction path from the LWE problem to the DCP (resp. extrapolated
DCP). Finally, we demonstrate the NTCF$^1_{\kappa}$ can naturally be reduced to
the NTCF$^1_2$, thereby achieving the same application for proving the
quantumness.
- Abstract（参考訳）: 強力な量子暗号ツールとしてのntcfは、信頼できない量子デバイスの動作を効率的に制限することができる。
しかし、元の NTCF は本質的には \emph{2-to-1} 片道関数 (NTCF$^1_2$) である。
本研究では, ntcf$^1_2$をさらに拡張し, 多項式有界な前像サイズを持つtrapdoor claw-free関数を実現する。
具体的には、外挿された二面体コセットを描画することにより、NTCF$^1_2$のかなりの外挿に焦点を合わせ、$\kappa$ が多項式整数であるような NTCF$^1_{\kappa}$ のモデルを与える。
そこで, NTCF$^1_{\kappa}$の効率的な構成法として, 誤り付き学習におけるemph{quantum hardness of the learning with error (LWE) を提案する。
NTCFはLWEと二面コセット問題(DCP)の橋渡しに利用できる。
NTCF$^1_2$(resp)を利用する。
NTCF$^1_{\kappa}$, 我々の研究は、LWE問題から DCP (resp. expolated DCP) への新しい量子還元経路を明らかにする。
最後に、NTCF$^1_{\kappa}$を自然にNTCF$^1_2$に還元できることを示し、量子性を証明するために同じ用途を達成する。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Extending the Design Space of Graph Neural Networks by Rethinking
Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。
しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。
我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。
N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文 参考訳（メタデータ） (2023-06-05T21:35:32Z) - Lattice-Based Quantum Advantage from Rotated Measurements [4.196134281008551]
我々は、$XY$-planeの量子ビット測定範囲全体を利用する新しい手法を示す。
パウリ-Z$補正まで$XY$平面上の任意の状態のブラインド遠隔準備のためのワンラウンドプロトコルを構築する。
論文 参考訳（メタデータ） (2022-10-18T20:18:15Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
論文 参考訳（メタデータ） (2022-06-01T03:40:56Z) - Non-local computation of quantum circuits with small light cones [0.0]
ポートベースのテレポーテーションは、一度に少数の量子ビットでのみ行われる場合、はるかに少ない絡み合いになる。
我々は、プロトコルの絡み合いコストが既知のプロトコルよりも良くスケールする、明示的なユニタリのクラスを提供する。
論文 参考訳（メタデータ） (2022-03-18T18:00:06Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - Lower Bounds for XOR of Forrelations [7.510385608531827]
我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。
また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
論文 参考訳（メタデータ） (2020-07-07T17:05:09Z) - Capacity Approaching Coding for Low Noise Interactive Quantum
Communication, Part I: Large Alphabets [15.078027648304115]
ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。
$mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。
我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
論文 参考訳（メタデータ） (2020-01-09T02:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。