論文の概要: Witness Encryption via Prime-Order Generic Groups

• arxiv url: http://arxiv.org/abs/2609.18275v1
• Date: Wed, 16 Sep 2026 07:54:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.70282
• Title: Witness Encryption via Prime-Order Generic Groups
• Title（参考訳）: プライマリオーダージェネリックグループによるウイットネス暗号化
• Abstract要約: 古典的なジェネリックグループモデルにおいて、NPの証人暗号を構築する。 SATインスタンスのサイズが$n$の場合、暗号化はpoly$(n)$で実行され、任意の満足な代入はpoly$(n)$時間で正しいエラーで2-n(1)$で復号することができる。
• 参考スコア（独自算出の注目度）: 6.201763450086127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We unconditionally construct witness encryption for NP in the classical generic-group model, using an ordinary cyclic group of prime order. For SAT instances of size $n$, the encryption algorithm runs in time poly$(n)$, and any satisfying assignment can be used to decrypt in poly$(n)$ time with correctness error $2^{-n^{Ω(1)}}$. If no satisfying assignment exists, then every generic adversary making at most $n^{Θ(\log n)}$ group queries has distinguishing advantage at most $n^{-Θ(\log n)}$. Along the way, we prove the first superconstant-factor NP-hardness of approximation result for homogeneous MinRank under randomized polynomial-time reductions, achieving a logarithmic gap even when the rank-one witness has a Boolean right factor.
• Abstract（参考訳）: 古典的一般群モデルにおいて、素数の通常の巡回群を用いてNPの証人暗号を無条件に構築する。 n$のSATインスタンスの場合、暗号化アルゴリズムはpoly$(n)$で動作し、任意の満足な代入はpoly$(n)$ time with correctness error $2^{-n^{Ω(1)}}$で復号することができる。 満足のいく代入が存在しないなら、すべての一般的な逆元は、最大$n^{*(\log n)}$の群クエリは、最大$n^{*(\log n)}$の長所を区別する。 その過程で、ランダム化多項式時間短縮の下で、同種MinRankの近似結果の最初の超定数NP硬度を証明し、ランクワンの証人がブール右因子を持つ場合でも対数的ギャップを達成した。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  RSAモジュールの$N$に対して$varphi(N)$を、ランダムに選択された整数の代入として$N$を演算する計算時間アルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-06-06T13:30:18Z)
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem [2.90985742774369]
  SDLPは,いくつかの重要な症例においてさらに容易であることを示す。 SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
  論文  参考訳（メタデータ） (2023-12-21T16:58:59Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• The Algorithmic Phase Transition of Random $k$-SAT for Low Degree Polynomials [18.00315760946089]
  満足な代入は、節密度$m/n 2k log 2 - frac12で高い確率で存在することが知られている。 低次アルゴリズムは節密度$(1 - o_k(1)) 2k log k / k$で満足な代入を見つけることができる。
  論文  参考訳（メタデータ） (2021-06-03T21:01:02Z)
• Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
  語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。 LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-17T03:13:45Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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