A batch-fidelity obstruction in hidden-shift attacks on unique-SVP

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.

For a lattice $\Lambda\subseteq\mathbb R^d$, the shortest-vector length is $\lambda_1(\Lambda)=\min_{0\ne v\in\Lambda}\|v\|$. An approximation algorithm seeks a nonzero vector of length at most a stated factor times $\lambda_1(\Lambda)$. Hidden-shift algorithms recover an unknown translation relating oracle functions.

Statement recorded in the supplied source.

How fast are approximate SVP attacks via hidden shift algorithms? [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 approximation factor, lattice encoding, norm, and reduction to a hidden-shift instance are not selected in the original question; no unique-SVP variant is substituted. 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

How fast can hidden-shift methods attack approximate shortest-vector problems?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001331 (AIM-CRYPTOGRAPHY-0018). 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-0018 http://aimpl.org/quantumalg/4/.

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 20001331 and source code AIM-CRYPTOGRAPHY-0018 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

The original AIM URL was attempted on 2026-10-11, but the web fetch timed out and a direct retrieval failed at DNS resolution. Its supplied extract is preserved above; fresh access to that page is not claimed. Regev's primary abstract was read. It describes a reduction involving unique-SVP and dihedral coset sampling, including a stated $\Theta(n^{2.5})$ uniqueness regime. This is not an abstract assertion that arbitrary approximate-SVP instances reduce with the same parameters. The original catalogue formulation is explicitly reconstructed and unverified, and remains so here. The calculation tests two missing steps in the proposed transfer of hidden-shift speed to approximate-SVP attacks.

Research attempt: Accumulated state error and the unique-SVP promise gap

Suppose, as an auxiliary reduction model, an ideal quantum routine needs $t$ independent copies of a unit vector $|\psi\rangle$, but preparation supplies independent copies of $|\phi\rangle$ with $|\langle\psi\mid\phi\rangle|^2=1-\varepsilon$. The squared overlap of the batches is $(1-\varepsilon)^t$, not $1-\varepsilon$. Their trace distance is \[ D_t=\sqrt{1-(1-\varepsilon)^t}. \tag{1} \] For completeness, for any two unit vectors $u,v$, adjust the phase of $v$ to write $v=cu+\sqrt{1-c^2}w$, where $c=|\langle u,v\rangle|$ and $w\perp u$. On their span, $uu^*-vv^*$ has trace zero and determinant $-(1-c^2)$, so its eigenvalues are $\pm\sqrt{1-c^2}$. Half of its trace norm is therefore $\sqrt{1-c^2}$. Tensor-product overlaps give $1$.

This quantity has a direct operational meaning requiring no unproved inference about a particular sieve. If a measurement event has effect $0\leq M\leq I$, diagonalize the trace-zero Hermitian difference $\Delta$ into positive and negative parts. Then $|\operatorname{tr}(M\Delta)|\leq\operatorname{tr}\Delta_+=\|\Delta\|_1/2$, and equality is attained by the projector onto the positive eigenspace. Thus $1$ is an exact worst-case difference in event probability, rather than merely a norm chosen for convenience.

The elementary inequalities $1-(1-\varepsilon)^t\leq t\varepsilon$ and $(1-\varepsilon)^t\leq e^{-t\varepsilon}$ imply \[ \sqrt{1-e^{-t\varepsilon}}\leq D_t\leq\sqrt{t\varepsilon}. \] The upper bound follows by induction from $(1-\varepsilon)^t\geq1-t\varepsilon$; the lower bound uses $\log(1-\varepsilon)\leq-\varepsilon$. To guarantee $D_t\leq\eta$ uniformly by this route, $\varepsilon\leq\eta^2/t$ is sufficient, whereas $1$ also requires $\varepsilon\leq1-(1-\eta^2)^{1/t}$. A fixed single-copy infidelity does not give fixed total error as $t$ grows. Conversely, a particular algorithm might tolerate more error; $1$ does not prove every hidden-shift routine fails.

There is a separate lattice-promise obstruction. For $0<\delta<1$, the two-dimensional lattice generated by $(1,0)$ and $(0,1+\delta)$ has $\lambda_1=1$ and second successive minimum $\lambda_2=1+\delta$. Indeed every vector is $(m,(1+\delta)n)$; a vector independent of $(1,0)$ has $n\ne0$ and length at least $1+\delta$, attained by the second basis vector. For any approximation factor $\gamma>1$, choose $\delta<\min(1,\gamma-1)$. Returning the second basis vector is then a valid $\gamma$-approximate answer, but its gap $\lambda_2/\lambda_1$ can be arbitrarily close to one. Thus a general approximation-factor specification supplies no fixed uniqueness gap exceeding one. A reduction that needs such a gap must construct or prove it separately.

Together these checks locate two concrete missing parameters in a runtime estimate: the cost to prepare each state at accuracy scaling with the total number of consumed states, and a justified reduction from the stated lattice promise. Counting only the subsequent ideal hidden-shift operations omits both.

Verification and adversarial audit

Equation $1$ is exact at $t=1$, $\varepsilon=0$, and $\varepsilon=1$. The trace-distance interpretation is proved on the relevant finite-dimensional span. Independence is stated; correlated state-preparation errors cannot be assigned the product-overlap formula automatically. The lattice example uses Euclidean norm and rational $\delta$ may be chosen to give a finite rational encoding.

Audit corrections.

A single-copy fidelity guarantee was not applied unchanged to an entire batch. The catalogue's unique-SVP-flavored title was not allowed to replace the broader, unverified original question.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No approximate-SVP attack, concrete lattice reduction, or full resource estimate is produced. The source's missing approximation factor, encoding and access model prevent a unique comparison; unique-SVP is discussed only as a distinct promise actually identified by the checked primary abstract.

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/cs/0304005 (consulted 2026-10-11).
• https://arxiv.org/abs/quant-ph/0302112 (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.