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).