Metraipolis › archive › dc_d57f7b339447
The Structured Totient Preimage Problem: Reconstruction, Collisions, and Cryptographic Implications — arXiv:2608.19191
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.19191
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T13:51:55.433Z
- SHA-256 of the archived text
ad09cbaf844070a2a18442296f232a06cfc0821f3e8cdb6ae14b8d3e91daf9e8- Stable URL of this page
https://metraipolis.com/documento/dc_d57f7b339447
How to cite
The Structured Totient Preimage Problem: Reconstruction, Collisions, and Cryptographic Implications — arXiv:2608.19191 — arXiv (en), https://arxiv.org/abs/2608.19191 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d57f7b339447 (Metraipolis archive dc_d57f7b339447, sha256 ad09cbaf844070a2a18442296f232a06cfc0821f3e8cdb6ae14b8d3e91daf9e8)
BibTeX
@misc{dcd57f7b339447,
title = {The Structured Totient Preimage Problem: Reconstruction, Collisions, and Cryptographic Implications — arXiv:2608.19191},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.19191},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d57f7b339447; sha256 ad09cbaf844070a2a18442296f232a06cfc0821f3e8cdb6ae14b8d3e91daf9e8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.19191. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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,\lambda,k)$, STP asks for any set of $k$ distinct $\lambda$-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 $\Omega(x)=O(\log\lambda)$; 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 $\lambda=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.
Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-08-20 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2608.19191 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T13:49:54.243Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-08-20?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).