論文の概要: Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
- arxiv url: http://arxiv.org/abs/2111.00486v2
- Date: Thu, 14 Mar 2024 01:14:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-17 13:51:55.967242
- Title: Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
- Title（参考訳）: 微粒クリプトアナリシス : k-SUMとk-XORの高次条件境界
- Authors: Itai Dinur, Nathan Keller, Ohad Klein,
- Abstract要約: a average-case variant of a $k$-SUM conjecture(英語版)は、$r$乱数のリストで 0 に等しい数を見つけることは $rlceil k/2 rceil$ time よりもはるかに少ない。
リストがより多くの数を持ち、多くの解が存在する高密度なパラメータ体系では、その中の1つを見つける複雑さは、ワーグナーの$k$-treeアルゴリズムによって著しく改善される。
- 参考スコア（独自算出の注目度）: 10.391533135772699
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An average-case variant of the $k$-SUM conjecture asserts that finding $k$ numbers that sum to 0 in a list of $r$ random numbers, each of the order $r^k$, cannot be done in much less than $r^{\lceil k/2 \rceil}$ time. On the other hand, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner's $k$-tree algorithm. Such algorithms for $k$-SUM in the dense regime have many applications, notably in cryptanalysis. In this paper, assuming the average-case $k$-SUM conjecture, we prove that known algorithms are essentially optimal for $k= 3,4,5$. For $k>5$, we prove the optimality of the $k$-tree algorithm for a limited range of parameters. We also prove similar results for $k$-XOR, where the sum is replaced with exclusive or. Our results are obtained by a self-reduction that, given an instance of $k$-SUM which has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense $k$-SUM oracle, and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle's solutions, even though its inputs are highly correlated.
- Abstract（参考訳）: 平均ケースの$k$-SUM予想の変種は、$r$乱数のリストで 0 に等しい$k$数を見つけると、$r^k$は$r^{\lceil k/2 \rceil}$時間以下では達成できないと主張する。
一方、リストがより多くの数を持ち、多くの解が存在する高密度なパラメータ体系では、その中の1つを見つける複雑さは、ワーグナーの$k$-treeアルゴリズムによって著しく改善される。
密集系における$k$-SUMのそのようなアルゴリズムは、特に暗号解析において多くの応用がある。
本稿では、平均ケース$k$-SUM予想を仮定し、既知のアルゴリズムが本質的に$k=3,4,5$に対して最適であることを示す。
k>5$の場合、限られたパラメータに対して$k$-treeアルゴリズムの最適性を証明する。
また、$k$-XORでも同様の結果を示し、ここでは和を排他的または排他的に置き換える。
我々の結果は、いくつかの解を持つ$k$-SUMのインスタンスを考えると、高密度な状態の多くのインスタンスから生成される自己還元によって得られる。
我々は、これら各インスタンスを高密度な$k$-SUMオラクルを用いて解決し、高密度なインスタンスに対する解が元の問題を解くことを期待する。
我々は、密集したインスタンスにノイズを加える難読化プロセスによって、潜在的に悪意のあるオラクル(相関した無意味なソリューションを繰り返し出力する)を扱う。
離散フーリエ解析を用いて、難解化は、その入力が高相関であるにもかかわらず、オラクルの解間の相関を排除していることを示す。
関連論文リスト
- On Wagner's k-Tree Algorithm Over Integers [5.440397659472035]
k-Tree は平均ケース k-SUM 問題に対する非自明なアルゴリズムである。
入力リストのサイズがこれよりもかなり大きい場合、高い確率で成功することを示す。
論文 参考訳（メタデータ） (2024-10-09T13:19:19Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - 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) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。