論文の概要: On the Failure Probability of Quantum Leftover Hashing with Bad Seeds

• arxiv url: http://arxiv.org/abs/2611.03484v1
• Date: Mon, 02 Nov 2026 17:28:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 04:18:48.448483
• Title: On the Failure Probability of Quantum Leftover Hashing with Bad Seeds
• Title（参考訳）: 悪い種子を用いた量子残余ハッシュの故障確率について
• Abstract要約: 暗号アプリケーションで用いられるように、量子敵に対するハッシュについて研究する。 我々は、種子を再利用し、非理想的かもしれない実践的な環境で失敗する可能性の限界を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study hashing against quantum adversaries, as used in cryptographic applications, and provide bounds on the probability of failure in practical settings where seeds might be reused and might be non-ideal. Randomness extraction and privacy amplification are key components of quantum cryptographic protocols, such as quantum randomness generation or key distribution, that allow the compression of partially secure raw data into shorter output with high security. To ensure the security of any cryptographic construction that integrates them, it is desirable to establish composable security. This can be done by using methods based on universal hashing and leveraging the general leftover hash lemma, which allows extraction of near-uniform random numbers from an imperfect entropy source by sampling from an almost two-universal family of hash functions using a seed. This approach is taken in many practical implementations, commonly using Toeplitz hashing. The lemma provides an upper bound $\varepsilon$ on the distance of the output to uniform randomness, which holds on average over the choice of seeds. It makes no claim that any particular seed yields near-uniform random numbers. This poses a problem for practical applications where a seed is sampled once and reused for many rounds (blockwise hashing). Here, we study the subset of \textit{bad} seeds yielding far-from-uniform outputs. We show that randomness extraction against quantum side information is guaranteed to produce $δ$-close-to-uniform random numbers except with failure probability $\left(\frac{\varepsilon}δ\right)^2$. This result is generalised to blockwise hashing providing a guarantee of the security of $k$ rounds except with failure probability $\big(\frac{(2k-1)\varepsilon}δ\big)^2$. Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.
• Abstract（参考訳）: 我々は、暗号アプリケーションで使用される量子敵に対するハッシュについて研究し、種子を再利用し、非理想的かもしれない現実的な環境では、失敗の確率に関するバウンダリを提供する。 ランダム性抽出とプライバシアンプリフィケーションは、量子ランダム性生成や鍵分布などの量子暗号プロトコルの重要なコンポーネントであり、部分的にセキュアな生データをより短い出力に高セキュリティで圧縮することができる。 それらを統合する暗号化構成のセキュリティを確保するためには、構成可能なセキュリティを確立することが望ましい。 これは、一般的なハッシュ補題の普遍的ハッシュに基づく手法を用いて、種子を用いてほぼ2つのユニバーサルなハッシュ関数の族からサンプリングすることにより、不完全エントロピー源からほぼ均一な乱数を抽出することができる。 このアプローチは多くの実践的な実装で採用されており、一般的にはToeplitz hashingを用いている。 補題は、出力から均一なランダム性への距離の上限$\varepsilon$を提供し、種子の選択よりも平均的に保持する。 特定の種がほぼ一様乱数をもたらすという主張は存在しない。 これは、シードが一度サンプリングされ、多くのラウンド(ブロックワイズハッシュ)で再利用される実用的なアプリケーションに問題を引き起こす。 そこで本研究では,一様出力から遠方から得られる種子のサブセットについて検討する。 量子側情報に対するランダム性抽出は、失敗確率$\left(\frac{\varepsilon}δ\right)^2$を除いて、$δ$-close-to-uniformランダム数を生成することが保証されている。 この結果は、失敗確率$\big(\frac{(2k-1)\varepsilon}δ\big)^2$を除いて、$k$ラウンドのセキュリティを保証するブロックワイズハッシュに一般化される。 さらに, 余剰ハッシュ補題をブロックワイズに拡張し, ほぼ2つのユニバーシティの仮定を緩和する。

関連論文リスト

• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [53.80737717363129]
  普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。 ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-21T19:37:35Z)
• Local contextuality-based self-tests are sufficient for randomness expansion secure against quantum adversaries [0.0]
  局所的文脈性に基づく自己テストは、非有界量子敵に対して安全であるランダム性拡張プロトコルを構築するのに十分であることを示す。 本プロトコルは,非コンテクストの不等式からの自己検証に基づいて,$mathcalO(mstepsilon)$-closeで一様分散およびプライベートにセキュアな乱数を生成することを実証する。
  論文  参考訳（メタデータ） (2024-09-30T08:31:46Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  我々は $bot$-PRG と $bot$-PRF の新たな定義を導入する。 私たちの主な応用は、古典的な公開鍵と署名を備えた(量子)デジタル署名スキームです。
  論文  参考訳（メタデータ） (2023-11-01T20:54:50Z)
• A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks [0.6216023343793144]
  ランダム性の分散生成のためのプロトコルを提供する。 無信頼であり、不偏乱数を生成する。 また、タンパー耐性があり、出力を変更したり、その分布に影響を与えない。
  論文  参考訳（メタデータ） (2023-09-20T12:21:39Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• 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)

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

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