論文の概要: Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model

• arxiv url: http://arxiv.org/abs/2312.16619v2
• Date: Thu, 7 Mar 2024 07:07:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-08 17:17:02.237448
• Title: Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model
• Title（参考訳）: 量子ランダムオラクルモデルにおけるCRYSTALS-Dilithiumの安全性の評価
• Authors: Kelsey A. Jackson, Carl A. Miller, Daochen Wang
• Abstract要約: 我々は、量子ランダムオラクルモデル(QROM)におけるMLWEからの還元によるSelfTargetMSISの硬さの最初の証明を提供する。 MSIS問題から派生した特定のハッシュ関数が崩壊していることの証明である。 Kiltz, Lyubashevsky, Schaffner の以前の研究と比較すると、我々の証明は q = 1 mod 2n という条件で適用できるという利点がある。
• 参考スコア（独自算出の注目度）: 2.486161976966064
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the previous work by Kiltz, Lyubashevsky, and Schaffner (EUROCRYPT 2018) that gave the only other rigorous security proof for a variant of Dilithium, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key size and signature size are about 2.9 times and 1.3 times larger, respectively, than those proposed by Kiltz et al. at the same security level.
• Abstract（参考訳）: 量子コンピューティングハードウェアの最近の進歩を受けて、National Institute of Standards and Technology (NIST)は、量子敵による攻撃に耐性のある暗号プロトコルを標準化している。 NISTが選択した主要なデジタル署名スキームはCRYSTALS-Dilithiumである。 このスキームの難しさは、エラー付きモジュール学習(MLWE)、MSIS(Module Short Integer Solution)、SelfTargetMSIS(SelfTargetMSIS)の3つの計算問題の難しさに基づいている。 MLWEとMSISはよく研究されており、安全であると広く信じられている。 しかし、SelfTargetMSISは新しく、古典的にはMSISと同じくらい硬いが、その量子硬さは不明瞭である。 本稿では,量子ランダムOracleモデル(QROM)におけるMLWEの低減によるSelfTargetMSISの硬さの最初の証明について述べる。 我々の証明は、最近開発された量子再プログラミングと再巻き戻しの技術を用いている。 このアプローチの中心的な部分は、msis問題から派生したハッシュ関数が崩壊していることの証明です。 このアプローチから,ダイアリシウムの適切なパラメータ設定下での新しいセキュリティ証明を推定する。 kiltz氏、lyubashevsky氏、schaffner氏(eurocrypt 2018)によるdilithiumの変種に対する厳密なセキュリティ証明の他に、この証明はq = 1 mod 2n条件の下で適用できるという利点がある。 この条件は元々のディリシウムの提案の一部であり、スキームの効率的な実装に不可欠である。 q = 1 mod 2n という条件の下で、dilithium の新しいセキュアパラメータセットを提供し、セキュリティレベルでkiltzらによって提案されたものよりも、公開鍵サイズと署名サイズがそれぞれ約2.9倍と1.3倍大きいことを見出します。

関連論文リスト

• Hidden-State Proofs of Quantumness [1.0878040851638]
  量子性の実験的暗号的証明は、量子情報科学の進歩における重要なマイルストーンとなる。 このようなテストを実装する上で、エラー寛容は永続的な課題である。 本稿では、(Brakerski et al)と同じ回路構造を維持する量子性の証明を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:04:53Z)
• VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme [0.8643517734716606]
  多変量方程式の解法に基づく量子後デジタルシグネチャアルゴリズムを提案する。 我々は、慎重に選択されたパラメータが、既存のすべての最先端攻撃に抵抗できることを示します。 これは、同様のセキュリティを持つ全ての既知の量子後シグネチャスキームの中で最小のシグネチャサイズである。
  論文  参考訳（メタデータ） (2023-12-15T04:58:10Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Obfuscation of Pseudo-Deterministic Quantum Circuits [14.026980555435841]
  古典オラクルモデルにおいて擬似決定論的量子回路を難解化する方法を示す。 我々のオブファスケータは任意の入力に対して、量子状態$ketwidetildeQ$を繰り返し出力する。
  論文  参考訳（メタデータ） (2023-02-22T01:14:20Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  完全同型暗号方式として, 完全同型暗号方式を初めて構築する。 我々の主要な技術要素は、量子証明器が古典的検証器に量子状態の形でのLearning with Errors分布からのサンプルが削除されたことを納得させる対話的プロトコルである。
  論文  参考訳（メタデータ） (2022-03-03T10:07:32Z)
• Limitations on Uncloneable Encryption and Simultaneous One-Way-to-Hiding [17.660958043781154]
  古典的メッセージに対する不必要な量子暗号方式について検討する。 情報理論の設定に焦点をあて、これらのスキームの構造とセキュリティにいくつかの制限を与えます。
  論文  参考訳（メタデータ） (2021-03-26T15:12:10Z)
• Quantum-access security of the Winternitz one-time signature scheme [5.156484100374058]
  攻撃者が秘密鍵機能への重ね合わせアクセスを許可される量子アクセスセキュリティは、基本的なセキュリティモデルである。 我々は、Alagicらによる量子ランダムオラクルモデル(QROM)におけるLamportワンタイム署名スキーム(OTS)の量子アクセスセキュリティ解析を再考し、そのギャップを埋める(Eurocrypt 2020)。
  論文  参考訳（メタデータ） (2021-03-23T10:55:00Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• 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 Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。