Trapdoor-free security from multiple nearby RSA moduli

Definitions and mathematical statement

Consider integers $n_i=n_1+d_i>1$ and exponentiation maps \[ f_i(r)=r^{e_i}\bmod n_i,\qquad1\leq i\leq t. \] For an output $y$, inversion ordinarily means finding an admissible preimage $r$ satisfying $r^{e_i}\equiv y\pmod{n_i}$; this need not be a unique inverse unless the exponent and domain conditions make $f_i$ a permutation.

Desmedt's conjecture is that, with sufficiently many of the specified nearby-modulus components, at least one $f_i$ is not polynomial-time invertible, as needed for the proposed trapdoor-free RSA-like probabilistic function. "Not polynomial-time invertible" is a computational claim, not failure of algebraic bijectivity.

A precise complexity formulation requires an asymptotic family, for example with security parameter related to $\log n_1$, rather than a single finite list of finite maps. The source does not give the modulus-generation rules, restrictions on $e_i$, domain of $r$, size of the offsets $d_i$, or a threshold for $t$. Those restrictions are essential: unrestricted exponents would include $e_i=1$, yielding identity components. No additional restrictions are invented to repair the missing setup.

The hardness quantifier is also unspecified: worst-case inversion, average-case inversion over generated parameters and outputs, one uniformly hard indexed family, and an index that may vary with the parameters are different claims. The composition and sampling rules of the probabilistic function are absent, so the asserted security implication cannot be verified merely from the displayed component formulas. The intended conjecture and its motivation are retained with those gaps explicit.

Short English statement

For the intended family of nearby RSA-like moduli, prove that enough exponentiation components force at least one computationally hard inversion problem. The omitted generation, exponent, component-count, and security quantifiers are essential to the proposed trapdoor-free construction.

Sources

• Local UnsolvedMath registry, permanent ID 8800097, source code catalogue entry; attributed to Yvo Desmedt; no proposal year supplied; update 2026-08-06.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6695, extended abstract page 2: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Registry access date 2026-07-29; PDF and legacy-PPT visual audit. Provenance reports 19 attachments, 17 PDFs and two legacy PPT decks, with repetitions and solved definitions excluded. Present status and redistribution terms require review.
• The supplied summary describes Desmedt's nearby-modulus trapdoor-free conjecture as unproved, without an additional exact reference or verified resolution.