Search papers, labs, and topics across Lattice.
This paper introduces the Structured Totient Preimage (STP) problem, which focuses on reconstructing sets of distinct primes given their totient product, with implications for cryptographic applications. The authors derive polynomial reconstruction bounds for fixed parameters, develop exhaustive algorithms for analyzing reconstruction and collisions, and evaluate a large dataset of prime sets to quantify non-injectivity and ambiguity. Their findings suggest that under certain assumptions, STP could serve as a preimage-resistant relation, influencing the design of cryptographic commitments and proofs of knowledge.
STP could redefine our understanding of preimage resistance in cryptographic systems, challenging existing assumptions about prime reconstruction.
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.
