論文の概要: The Structured Totient Preimage Problem: Reconstruction, Collisions, and Cryptographic Implications
- arxiv url: http://arxiv.org/abs/2608.19191v1
- Date: Wed, 19 Aug 2026 17:57:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-20 20:13:55.48795
- Title: The Structured Totient Preimage Problem: Reconstruction, Collisions, and Cryptographic Implications
- Title（参考訳）: 構造的トジェント・プレイメージ問題:再構築, 衝突, 暗号的含意
- Abstract要約: 本研究では,Structured Totient Preimage(STP)問題を,直接暗号モチベーションと制限された再構成関係として検討する。
この関係は効率よく検証できるが、その再構築の複雑さは分かっていない。
我々は28のパラメータ対を総じて評価し、2leq kleq5$、対が$16$、最大の国勢調査が4,588,935素集合である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We define and study the Structured Totient Preimage (STP) problem as a restricted reconstruction relation with a direct cryptographic motivation. Let $p_1,\ldots,p_k$ be distinct primes of the same bit length and reveal only $x=\prod_{i=1}^k(p_i-1)$. Given $(x,λ,k)$, STP asks for any set of $k$ distinct $λ$-bit primes satisfying this product. The relation is efficiently verifiable, but its reconstruction complexity is not known. We establish three concrete results. First, for factored $x$ we derive the exact number of ordered exponent allocations and a bound showing that direct reconstruction is polynomial for fixed $k$ when $Ω(x)=O(\logλ)$; this rules out that regime as a basis for a strong hardness claim. Second, we give exhaustive algorithms for reconstruction and collision analysis. Third, we exhaustively evaluate 28 parameter pairs, with $2\leq k\leq5$, up to $λ=16$ for pairs and 4,588,935 prime sets in the largest census. The data quantify non-injectivity through collision participation, maximum multiplicity, and conditional ambiguity in bits. These results isolate STP from general inverse-totient computation and motivate a Structured Totient Preimage Assumption for explicitly growing parameter families. Under such an assumption, STP becomes a candidate preimage-resistant relation whose implications for commitments, proofs of knowledge of multiplicative witnesses, and authentication can be stated precisely. The paper establishes the computational foundation and parameter constraints for those constructions; it does not claim a security reduction or post-quantum hardness.
- Abstract（参考訳）: 本研究では,Structured Totient Preimage(STP)問題を,直接暗号モチベーションと制限された再構成関係として定義・研究する。
p_1,\ldots,p_k$ を同じビット長の異なる素数とし、x=\prod_{i=1}^k(p_i-1)$ だけを明らかにする。
STPは$(x,λ,k)$を与えられたとき、この積を満たす任意の$k$別の$λ$-ビット素数を求める。
この関係は効率よく検証できるが、その再構築の複雑さは分かっていない。
3つの具体的な結果を確立します。
まず、因子付き$x$ の場合、順序付き指数割り当ての正確な数と、$Ω(x)=O(\logλ)$ が固定された$k$ の多項式であることを示す境界を導出する。
第2に、再構成と衝突解析のための網羅的なアルゴリズムを提案する。
第3に、28のパラメータ対を総じて評価し、2,\leq k\leq5$、対がλ=16$、最大の国勢調査が4,588,935素集合である。
このデータは衝突参加、最大乗算、ビットの条件のあいまいさを通じて非射影率を定量化する。
これらの結果は、STPを一般的な逆向き計算から分離し、明示的に成長するパラメーターファミリに対する構造化トジェント推定を動機付ける。
このような仮定の下で、STPは、コミットメント、乗法的証人の知識の証明、および認証が正確に記述されるような、先入観抵抗関係の候補となる。
本論文は, それらの構成に対する計算基礎とパラメータ制約を確立し, 安全性の低下やポスト量子硬度を主張するものではない。
関連論文リスト
- Exact quantum splitting and the structure of finite algebras [1.7277199466514768]
ベルカンプのアルゴリズムは、決定論的線型代数により、平方自由の$finmathbbF_q[x]$を分解する。
我々は、効率よく計算可能な角度で1量子ビットの回転を許す回路モデルに、無条件の正確な量子的実装を与える。
論文 参考訳（メタデータ） (2026-08-31T06:56:14Z) - A Complexity-Theoretic Approach to Proofs of Space [5.160781170457704]
我々は、デランドマイズ仮定と暗号仮定の組み合わせからPoSを構築するための基本的な暗号フレームワークを提供する。
ほぼ最適なパラメータと相互作用パターンを持つPoSは、(a)上の仮定と(c)$mathsfP$に対するSNARGから従う。
論文 参考訳（メタデータ） (2026-08-10T01:28:01Z) - Odds Law: The Decomposition Algebra On How Intelligence Organizes Itself to Solve Difficult Problems Reliably [0.5414847001704247]
信頼性は、合成によって配置された独立した情報で購入され、検証者によって拘束されることを示す。
つまり、信頼性は自由でも魔法でもなく、独立した情報で購入され、構成によって配置され、検証者によって拘束される。
論文 参考訳（メタデータ） (2026-06-14T09:53:11Z) - A Mathematical Theory of Value: a synthesis on goal-directed agency under resource constraints [6.057587531186626]
目的指向エージェントが生成し、破壊し、交換する価値は、情報と同じカテゴリの法的構造量であることを示す。
価格がフレームに依存していない間、価値はフレーム相対的であり、そのリソースをプールし、その知覚を融合する艦隊が天井を継承する。
論文 参考訳（メタデータ） (2026-06-10T16:11:04Z) - Strategic PAC Learnability via Geometric Definability [69.34283267701421]
戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。
中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。
仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。
難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
論文 参考訳（メタデータ） (2026-05-13T12:21:56Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Prefix Sums via Kronecker Products [47.600794349481966]
我々は、893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, $O(n)$ additional qubits で量子加算器を設計する方法を示す。
応用として、これらの回路を用いて1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, $O(n)$ additional qubits の量子加算器を設計する方法を示す。
論文 参考訳（メタデータ） (2025-12-18T08:49:18Z) - REWA: A General Theory of Witness-Based Similarity [0.0]
我々は、すべての離散的、連続的、代数的、学習的類似性を仮定する類似性保存符号化のための普遍的な枠組みを提案する。
この統合により、ブルームフィルタ、Locality Sensitive Hashing (LSH)、Count-Minのスケッチ、ランダムフーリエ機能、Transformerのアテンションカーネルは同じメカニズムのインスタンスであることが分かる。
論文 参考訳（メタデータ） (2025-11-25T07:04:44Z) - Apparent Universal Behavior in Second Moments of Random Quantum Circuits [0.34757790689654594]
ランダムな量子回路の2番目の瞬間について、あなたがいつも知りたがっていたことを全てお教えしますが、計算するにはあまりにも怖かったです。
我々の答えは一般に最大50キュービットの数値結果の形式を取る。
論文 参考訳（メタデータ） (2025-10-27T18:01:55Z) - Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
統計物理学からの予測では、ブロックモデル(SBM)におけるコミュニティの回復は、上述の時間で可能であり、上述のケステンスティグム(KS)しきい値のみである。
Chinら(2025)は、最近、スパース体制では、非バックトラック経路を数えることにより、KS閾値以下でコミュニティの回復が可能であることを証明した。
論文 参考訳（メタデータ） (2025-09-19T09:53:56Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。