論文の概要: Quantum security of subset cover problems
- arxiv url: http://arxiv.org/abs/2210.15396v1
- Date: Thu, 27 Oct 2022 12:58:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-21 08:14:24.516413
- Title: Quantum security of subset cover problems
- Title（参考訳）: 部分集合被覆問題の量子セキュリティ
- Authors: Samuel Bouaziz--Ermann, Alex B. Grilo and Damien Vergnaud
- Abstract要約: 多くのハッシュベースのシグネチャスキームのセキュリティは、サブセットカバー問題やこの問題の変種に依存する。
我々は、任意の量子アルゴリズムが、基礎となるハッシュ関数に対する$Omegaleft(k-frac2k-12k-1cdot Nfrac2k-1k-12k-1right)$クエリを作成する必要があることを証明した。
- 参考スコア（独自算出の注目度）: 1.4072904523937533
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The subset cover problem for $k \geq 1$ hash functions, which can be seen as
an extension of the collision problem, was introduced in 2002 by Reyzin and
Reyzin to analyse the security of their hash-function based signature scheme
HORS.
The security of many hash-based signature schemes relies on this problem or a
variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, \dots).
Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset
cover problem, called restricted subset cover, and proposed a quantum algorithm
for this problem. In this work, we prove that any quantum algorithm needs to
make $\Omega\left(k^{-\frac{2^{k-1}}{2^k-1}}\cdot
N^{\frac{2^{k-1}-1}{2^k-1}}\right)$ queries to the underlying hash functions to
solve the restricted subset cover problem, which essentially matches the query
complexity of the algorithm proposed by Yuan, Tibouchi and Abe.
We also analyze the security of the general $(r,k)$-subset cover problem,
which is the underlying problem that implies the unforgeability of HORS under a
$r$-chosen message attack (for $r \geq 1$). We prove that a generic quantum
algorithm needs to make $\Omega\left(N^{k/5}\right)$ queries to the underlying
hash functions to find a $(1,k)$-subset cover.
We also propose a quantum algorithm that finds a $(r,k)$-subset cover making
$O\left(N^{k/(2+2r)}\right)$ queries to the $k$ hash functions.
- Abstract（参考訳）: k \geq 1$ハッシュ関数に対する部分被覆問題は、衝突問題の延長と見なすことができ、2002年にレイジンとレイジンによってハッシュ関数に基づく署名スキームHORSの安全性を解析するために導入された。
多くのハッシュベースのシグネチャスキームのセキュリティは、この問題またはこの問題の変種(例えば、HORS、SPHINCS、SPHINCS+、 \dots)に依存している。
近年,Yuan,Tibouchi,Abe (2022) は,制限部分被覆と呼ばれる部分被覆問題の変種を導入し,この問題に対する量子アルゴリズムを提案した。
本研究では,任意の量子アルゴリズムにおいて,制約付き部分被覆問題を解くために,基礎となるハッシュ関数に対して$\omega\left(k^{-\frac{2^{k-1}}{2^k-1}}\cdot n^{\frac{2^{k-1}-1}{2^k-1}}\right)$クエリを行なわなければならないことを証明した。
また、一般的な$(r,k)$-subsetカバー問題のセキュリティも分析する。これは、$r$-chosenメッセージアタック($r \geq 1$)下でのHORSの偽造性を示す根底にある問題である。
一般的な量子アルゴリズムでは、基礎となるハッシュ関数に対して$\Omega\left(N^{k/5}\right)$クエリを行い、1,k)$-subsetのカバーを見つける必要がある。
また、$(r,k)$-subset 被覆を見つけ、$o\left(n^{k/(2+2r)}\right)$クエリを$k$ハッシュ関数に生成する量子アルゴリズムを提案する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳（メタデータ） (2023-02-20T19:11:44Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Optimal exact quantum algorithm for the promised element distinctness
problem [0.2741266294612775]
要素差分問題は、文字列$x=(x_1,ldots,x_N)$の$N$要素が同じ値の2つの要素を含むかどうかを決定することである。
保証問題に対する厳密な量子アルゴリズムを提案するが、これにはO(N2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2022-11-10T09:33:13Z) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳（メタデータ） (2022-05-27T14:50:45Z) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文 参考訳（メタデータ） (2020-12-16T17:58:45Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。