MathDB

Hardness of the discrete iteration problem

Let VV be the vector space with the second-order multilinear operation defined in the source, and let

∗ ⁣:V×V→V.*\colon V\times V\to V.

For a fixed vector a∈Va\in V and a positive integer nn, write

an:=a∗a∗⋯∗a⏟n times.a^n:=\underbrace{a*a*\dots*a}_{n\text{ times}}.

Hardness conjecture for the discrete iteration problem. Given aa and ana^n, it is computationally hard to recover nn for general parameter values, input vectors, and sufficiently large nn. The problem is introduced as an analogue of the discrete logarithm problem, but the supplied text gives no formal computational model or evidence resolving its hardness.

Sources & referencesView supporting material

Primary source

Stanislav Semenov, “One-way multilinear functions of the second order with linear shifts”, arXiv:2507.02882 (2025).

computational-complexityfinite-fieldsmultilinear-algebra

Progress summary

Refreshed
Open

The conjecture remains an unproved security assumption, with no public proof, disproof, or independent verification found.

The problem asks whether recovering the iteration count from an input and its repeated product is computationally hard, analogous to discrete logarithm recovery. The source states this as Conjecture 5.2\mathrm{Conjecture}\ 5.2, motivated by the apparent algebraic complexity of the iterates, not as a theorem.

Known results

  • The source reports efficient forward iteration but no established hardness proof for reversing it.
  • Formal security guarantees for the associated protocol are explicitly left to further analysis.

Current status (as of August 2026): The hardness conjecture remains open; no proof, counterexample, claimed settlement, or independent verification has been publicly recorded.

Sources

Solutions 0

No solutions have been posted yet.