論文の概要: Cryptanalysis of Three Quantum Money Schemes
- arxiv url: http://arxiv.org/abs/2205.10488v2
- Date: Sat, 29 Oct 2022 03:39:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-12 05:33:50.438865
- Title: Cryptanalysis of Three Quantum Money Schemes
- Title（参考訳）: 3つの量子マネースキームのクリプトアナリシス
- Authors: Andriyan Bilyk and Javad Doliskani and Zhiyong Gong
- Abstract要約: 3つの公開鍵量子マネースキームのセキュリティ仮定について検討する。
困難問題から線形代数問題への時間量子還元を与える。
- 参考スコア（独自算出の注目度）: 1.5254598796939927
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the security assumptions behind three public-key quantum money
schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of
the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in
2015 that the hard problem underlying the scheme can be solved in
quasi-polynomial time. We confirm this conjecture by giving a polynomial time
quantum algorithm for the underlying problem. Our algorithm is based on
computing the Zariski tangent space of a random point in the hidden subspace.
Zhandry proposed a scheme based on multivariate hash functions in 2017. We
give a polynomial time quantum algorithm for cloning a money state with high
probability. Our algorithm uses the verification circuit of the scheme to
produce a banknote from a given serial number.
Kane, Sharif and Silverberg proposed a scheme based on quaternion algebras in
2021. The underlying hard problem in their scheme is cloning a quantum state
that represents an eigenvector of a set of Hecke operators. We give a
polynomial time quantum reduction from this hard problem to a linear algebra
problem. The latter problem is much easier to understand, and we hope that our
reduction opens new avenues to future cryptanalyses of this scheme.
- Abstract（参考訳）: 3つの公開鍵量子マネースキームのセキュリティ仮定について検討する。
アーロンソンとクリスティアンは2012年にベクトル空間 $\mathbb{F}_2^n$ の隠れ部分空間に基づくスキームを提案した。
2015年にペナらは、このスキームの根底にある難しい問題を準多項式時間で解くことができると推測した。
多項式時間量子アルゴリズムを基礎問題に適用することにより、この予想を裏付ける。
アルゴリズムは隠れ部分空間内のランダム点のザリスキ接空間を計算することに基づいている。
zhandryは2017年に多変量ハッシュ関数に基づくスキームを提案した。
確率の高い貨幣状態をクローンするための多項式時間量子アルゴリズムを与える。
本アルゴリズムは,提案方式の検証回路を用いて,与えられたシリアル番号から紙幣を生成する。
ケーン、シャリフ、シルバーバーグは2021年に四元環に基づくスキームを提案した。
彼らのスキームの根底にある問題は、ヘッケ作用素の集合の固有ベクトルを表す量子状態のクローンである。
この難しい問題から線形代数問題への多項式時間量子還元を与える。
後者の問題は理解しやすく、我々の削減が、このスキームの将来の暗号解読への新しい道を開くことを期待している。
関連論文リスト
- Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
有限次元格子上に$vertpsirangle$を作成する定数深さ量子回路を学習する。
このアルゴリズムは、$U$の深さが$mathrmpolylog(n)$であり、準多項式実行時である場合に拡張される。
応用として、格子上の未知の量子状態が量子回路の複雑さが低いか高いかをテストするための効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-10-31T04:12:49Z) - An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes [3.444630356331766]
本稿では,局所フィールドにおけるLVPアルゴリズムの改良について述べる。
このアルゴリズムを用いて上記のスキームを攻撃し、任意のメッセージをフォージし、暗号文を復号化できるようにします。
これらのスキームは壊れているが、この研究は、$p$-adic 格子が暗号プリミティブの構築に適さないという意味ではない。
論文 参考訳（メタデータ） (2024-09-13T12:31:57Z) - Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Lattice sieving via quantum random walks [0.0]
格子ベースの暗号は、量子後暗号の主要な提案の一つである。
最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。
我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-12T11:59:30Z) - 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) - Quantum Garbled Circuits [9.937090317971313]
我々は、与えられた量子回路と量子入力のエンコーディングの計算方法を示し、そこから計算の出力を導出することができる。
我々のプロトコルは、いわゆる$Sigma$フォーマットで、シングルビットチャレンジがあり、入力を最終ラウンドまで遅らせることができる。
論文 参考訳（メタデータ） (2020-06-01T17:07:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。