Offline Simon, explicit HSP instances, and a classical-transcript obstruction

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Simon's problem asks for a hidden xor period s of a function on bit strings. A Q1 access model allows quantum computation but only classical queries to a secret primitive. A hidden-subgroup problem seeks a subgroup from a function constant on its cosets; an explicit instance supplies an efficiently implementable function circuit rather than an abstract oracle.

Statement recorded in the supplied source.

1. Simon/Q1 question. Is there a cryptanalytic problem for which Simon's algorithm is useful when the attacker may run a quantum computer but may make only classical queries to the secret primitive, rather than quantum superposition queries? 2. Cryptographic-HSP question. Which hidden-subgroup or closely related hidden-shift problems yield concrete cryptanalytic algorithms? 3. Explicit-instance question. Which HSP algorithms have explicit, noncryptographic input functions, in the sense that Shor's period function $x\mapsto a^x\bmod N$ is an efficiently implementable circuit rather than a formal black-box oracle? [S2]

Scope qualification.

The catalogue flags this record as reconstructed and unverified. The supplied question is preserved; the definitions do not certify a unique intended model. The supplied three-part formulation is explicitly a reconstruction, not a verified quotation of the primary problem list. No specific cryptanalytic example or positive answer is supplied. The supplied catalogue marks this formulation as an unverified reconstruction; the source link does not establish that all missing assumptions were recovered.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness.

Short English statement

Which cryptanalytic tasks use Simon's algorithm with classical secret queries, and which hidden-subgroup instances yield explicit algorithms?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001342 (AIM-CRYPTOGRAPHY-0029). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, original problem source linked by catalogue record AIM-CRYPTOGRAPHY-0029 http://aimpl.org/quantumalg/6/.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 20001342 and source code AIM-CRYPTOGRAPHY-0029 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

Fresh retrieval of the original AIM quantum-algorithm problem pages failed (web timeout and direct network/DNS failure; an escalated retry of the related chapter-four page also failed certificate validation). The supplied original extract remains the source text; successful fresh access to those pages is not claimed. The three-part catalogue statement is explicitly an unverified reconstruction and is retained as such. Bonnetain et al.'s primary Offline Simon abstract was consulted: it gives cryptanalytic examples using classical secret-primitive queries and offline quantum computation. Thus a blanket assertion that Simon-type ideas cannot help in Q1 would contradict the checked context. The following argument instead identifies the exact limitation of an arbitrary classical oracle transcript and separates that from structured cryptographic access.

Research attempt: A classical-transcript obstruction and an explicit linear HSP

Let $V=\mathbb F_2^n$, and suppose an oracle satisfies Simon's exact promise $F(x)=F(y)$ if and only if $y=x$ or $y=x+s$, for unknown $s\ne0$. Consider a transcript of distinct classical queries $x_1,\ldots,x_q$ with distinct answers. Define \[ D=\{x_i+x_j:1\leq i<j\leq q\}. \] Every nonzero $t\notin D$ is compatible with the whole transcript. To prove this construct a function with period $t$: partition $V$ into pairs $\{x,x+t\}$. No pair contains two queried points, because that would put $t$ in $D$. Assign each queried pair its observed answer, and assign distinct fresh labels to all other pairs. With a codomain having at least $2^{n-1}$ labels, this is exactly a Simon-promise function agreeing with every observed value. Therefore at least \[ 2^n-1-\binom q2 \] periods remain compatible whenever this number is positive.

Once the transcript is fixed, any subsequent quantum computation that receives only that transcript has the same input under all these completions. If it outputs a probability distribution on periods, the sum of its success probabilities over $K$ compatible choices is at most one, so some choice has success at most $1/K$. This is a conditional indistinguishability statement for the transcript. It is not a complete distributional lower bound for every adaptive randomized query strategy, and is not used as one. It does show precisely why an arbitrary polynomial-size collision-free table cannot simply replace coherent access to the full Simon oracle.

Algebraic structure changes the situation. For example, in an Even--Mansour-style relation $E(x)=P(x+k_1)+k_2$ over $V$, the formal function $G(x)=P(x)+E(x)$ obeys \[ G(x+k_1)=P(x+k_1)+P(x)+k_2=G(x). \] The public permutation circuit supplies information absent from a bare table. But the identity alone neither guarantees Simon's exact two-preimage promise nor permits a coherent query to the secret $E$ under Q1. Those are separate steps in a complete attack; the published offline construction is not rederived by this identity.

For the noncryptographic explicit-instance part, take a publicly given binary matrix $A\in\mathbb F_2^{m\times n}$ and the efficiently implementable function $F_A(x)=Ax$. Equality $F_A(x)=F_A(y)$ holds exactly when $x-y\in\ker A$, so it hides the subgroup $\ker A$ by its cosets. Its circuit uses at most $mn$ controlled bit additions. A classical algorithm can also find the kernel: row elimination preserves the solution set because swapping equations or adding one equation to another is reversible; after choosing pivots, every assignment to the nonpivot variables determines the pivot variables by back substitution. Assigning each free variable in turn to one and the others to zero yields a basis of the kernel. The usual elimination loops use polynomially many field operations. This is an explicit HSP instance, but no quantum advantage is inferred merely from explicitness.

Verification and adversarial audit

The completion construction respects both directions of Simon's promise, not just periodicity. The postprocessing limitation is conditioned on a fixed collision-free transcript and does not contradict structured offline Simon attacks. The Even--Mansour identity is checked in characteristic two and does not assume away extra periods. The explicit linear example also works with a zero matrix or trivial kernel.

Audit corrections.

Classical queries to the secret primitive were separated from quantum evaluation of public circuits. A transcript-completion lemma was not overstated as an unconditional adaptive lower bound, and periodicity was not confused with Simon's exact collision promise.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The original bundled request for cryptanalytic applications and Q1 usefulness is not fully rederived here. The checked paper supplies relevant known examples; this manuscript gives an exact failed transcript replacement, a verified algebraic period, and an explicit easy HSP family, with no new cryptanalytic speedup or full classification claimed.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://arxiv.org/abs/2002.12439 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written mathematical review at the declared scope; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.