論文の概要: 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年に四元環に基づくスキームを提案した。
彼らのスキームの根底にある問題は、ヘッケ作用素の集合の固有ベクトルを表す量子状態のクローンである。
この難しい問題から線形代数問題への多項式時間量子還元を与える。
後者の問題は理解しやすく、我々の削減が、このスキームの将来の暗号解読への新しい道を開くことを期待している。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
代入量子計算に有用な重要な暗号技術である量子同相暗号(QHE)へのこのスキームの適用を見出した。
我々は,完全セキュリティ,$mathcalF$-homomorphism,サーバとクライアント間の相互作用のないQHEスキームを開発し,Mが回路内のゲート数$T$である場合,$O(M)$で束縛された準コンパクト性を示す。
論文 参考訳(メタデータ) (2023-03-30T14:49:15Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - From the Hardness of Detecting Superpositions to Cryptography: Quantum
Public Key Encryption and Commitments [8.834776091974218]
暗号アンフノン・アベル群によるグループアクションから,最初の公開鍵暗号方式を示す。
本研究では,スワップ・トラップドア関数対と呼ばれる新しい抽象化によって構成する。
量子ビットのコミットメントのフレーバーを変換する単純で効率的なコンパイラを提供する。
論文 参考訳(メタデータ) (2022-10-12T07:40:05Z) - 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 [74.52678585199014]
計算・比較プログラム(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) - Quantum Attacks without Superposition Queries: the Offline Simon's
Algorithm [7.819565615098435]
我々はサイモンのサブルーチンを新しい方法で利用する新しい量子アルゴリズムを導入する。
現状の文献に関して量子時間/古典データのトレードオフを改善した。
我々はデータの複雑さを減らし、過去の重ね合わせ攻撃を改善した。
論文 参考訳(メタデータ) (2020-02-27T21:05:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。