論文の概要: Beyond quadratic speedups in quantum attacks on symmetric schemes
- arxiv url: http://arxiv.org/abs/2110.02836v1
- Date: Wed, 6 Oct 2021 15:10:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-12 08:09:49.913049
- Title: Beyond quadratic speedups in quantum attacks on symmetric schemes
- Title(参考訳): 対称スキーム上の量子攻撃における二次速度の超越性
- Authors: Xavier Bonnetain, Andr\'e Schrottenloher, Ferdinand Sibleyras
- Abstract要約: 我々は,古典的クエリのみを用いて,対称ブロック暗号設計に対する最初の量子鍵回復攻撃を報告した。
我々の攻撃は、いくつかの対称構造の構造をこの限界を克服するために利用することができることを示している。
- 参考スコア(独自算出の注目度): 30.01567358439495
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we report the first quantum key-recovery attack on a symmetric
block cipher design, using classical queries only, with a more than quadratic
time speedup compared to the best classical attack.
We study the 2XOR-Cascade construction of Ga\v{z}i and Tessaro
(EUROCRYPT~2012). It is a key length extension technique which provides an
n-bit block cipher with 5n/2 bits of security out of an n-bit block cipher with
2n bits of key, with a security proof in the ideal model. We show that the
offline-Simon algorithm of Bonnetain et al. (ASIACRYPT~2019) can be extended
to, in particular, attack this construction in quantum time \~O($2^n$),
providing a 2.5 quantum speedup over the best classical attack.
Regarding post-quantum security of symmetric ciphers, it is commonly assumed
that doubling the key sizes is a sufficient precaution. This is because
Grover's quantum search algorithm, and its derivatives, can only reach a
quadratic speedup at most. Our attack shows that the structure of some
symmetric constructions can be exploited to overcome this limit. In particular,
the 2XOR-Cascade cannot be used to generically strengthen block ciphers against
quantum adversaries, as it would offer only the same security as the block
cipher itself.
- Abstract(参考訳): 本稿では,古典的問合せのみを用いた対称ブロック暗号設計における最初の量子鍵回復攻撃を,古典的攻撃に比べて2倍以上の速さで報告する。
本稿ではGa\v{z}i と Tessaro (EUROCRYPT~2012) の 2XOR-Cascade 構成について検討する。
これは、2nビットの鍵を持つnビットブロック暗号から5n/2ビットのセキュリティを持つnビットブロック暗号を提供し、理想的なモデルのセキュリティ証明を提供する鍵長拡張技術である。
ボネテン等(ASIACRYPT~2019)のオフライン-サイモンアルゴリズムは、特に量子時間 \~O($2^n$) でこの構造を攻撃することができ、古典的攻撃に対して2.5量子スピードアップを提供する。
対称暗号の量子後セキュリティについては、鍵サイズを倍にすることが十分な予防策であると一般的に仮定される。
これは、グローバーの量子探索アルゴリズムとその導関数が、最大で2倍のスピードアップにしか到達できないためである。
我々の攻撃は、いくつかの対称構造の構造をこの限界を克服するために活用できることを示しています。
特に、2XOR-Cascadeはブロック暗号自体と同じセキュリティを提供するため、量子敵に対するブロック暗号の一般的な強化には使用できない。
関連論文リスト
- Towards Unconditional Uncloneable Encryption [1.18749525824656]
Uncloneablecryptは、古典的なメッセージを量子暗号文に暗号化する暗号化プリミティブである。
関連するセキュリティゲームにおける敵の成功確率は、キー数を表す$K$が1/2+1/ (2sqrtK)$に2次収束し、1/2$は自明に達成可能であることを示す。
論文 参考訳(メタデータ) (2024-10-30T14:40:06Z) - Quantum Key Leasing for PKE and FHE with a Classical Lessor [19.148581164364387]
安全な鍵リースの問題は、取り消し可能暗号(revocable cryptography)としても知られる。
この問題は、量子情報の不可避な性質を活用することを目的としている。
我々は、(古典的な)公開鍵・同型暗号方式の復号鍵をリースするために、セキュアな鍵リース方式を構築した。
論文 参考訳(メタデータ) (2023-10-22T15:25:29Z) - Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions [12.45203887838637]
我々は一方通行関数から量子公開鍵暗号を構築する。
私たちの構成では、公開鍵は量子だが、暗号文は古典的である。
論文 参考訳(メタデータ) (2023-04-04T13:57:17Z) - Revocable Cryptography from Learning with Errors [61.470151825577034]
我々は、量子力学の非閉鎖原理に基づいて、キー呼び出し機能を備えた暗号スキームを設計する。
我々は、シークレットキーが量子状態として表現されるスキームを、シークレットキーが一度ユーザから取り消されたら、それらが以前と同じ機能を実行する能力を持たないことを保証して検討する。
論文 参考訳(メタデータ) (2023-02-28T18:58:11Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳(メタデータ) (2022-05-07T03:15:15Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳(メタデータ) (2021-07-05T17:45:41Z) - Quantum Key-length Extension [17.52560033614633]
量子コンピュータはブロック暗号のような基本的な秘密鍵プリミティブの有効鍵長を減らす。
理想モデルにおける量子攻撃に対するこれらの構成の両方に対して、具体的および厳密な境界を持つ肯定的な結果を与える。
古典および量子オラクルを別々に解析することに頼ることなく、部分的に量子証明を行う手法を導入する。
論文 参考訳(メタデータ) (2021-05-04T01:40:42Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
論文 参考訳(メタデータ) (2020-12-30T18:03:56Z) - Quantum Period Finding against Symmetric Primitives in Practice [3.04585143845864]
我々は、オフラインSimonのアルゴリズムの最初の完全な実装を示し、Chaskey、ブロック暗号PRINCEおよびNIST軽量候補EADスキームElephantを攻撃するコストを見積もる。
これらの攻撃には相当量の量子ビットが必要であり、RSA-2048を破るのに必要な量子ビットの数に匹敵する。
我々は、我々の攻撃が今日の通信に対して将来適用される可能性があることを強調し、長期的なセキュリティが期待されているケースに対して、対称的な構成を選択する際に注意を喚起する。
論文 参考訳(メタデータ) (2020-11-13T17:12:49Z) - 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) - Backflash Light as a Security Vulnerability in Quantum Key Distribution
Systems [77.34726150561087]
量子鍵分布(QKD)システムのセキュリティ脆弱性について概説する。
我々は主に、盗聴攻撃の源となるバックフラッシュ光(backflash light)と呼ばれる特定の効果に焦点を当てる。
論文 参考訳(メタデータ) (2020-03-23T18:23:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。