What is here the security parameter $1^\kappa$?

Question

Let it be $K$ a key generation algorithm which takes $(k,d)$ as input with $k$ as the bit length for $n=pq$ with $p,q \in \mathbb{P}$ and $d=|p-q|$ as the minimum distance between $p$ and $q$ (RSA). What would be the security parameter $1^\kappa$?

Would it be $\kappa=k+d$ or only $\kappa=k$ and if it were the case on what would it depends?

I searched the following links and could not find an answer to my question:

What does the expression $1^n$ mean as a function argument? Why does key generation take an input $1^k$, and how do I represent it in practice?

Answer 1

For reasons in my comment I'll asume we change the question to define $δ$ with $2^\delta<\lvert p-q\rvert$, and $\kappa=k+\delta$. FIPS 186-4 key generation would for example use $k=3072$ and $\delta=k/2-100=1436$.

I can't find any reference discussing asymptotic RSA security with a notation like $1^k$ that specify a minimum $\lvert p-q\rvert$. That's because:

• Increasing $\delta$ past some point demonstrably decreases security. E.g. for $k=3072$ (which would give about 128-bit symmetric security) and $δ=1912$ we'd have $\min(p,q)<2^{161}$ and Lentra's ECM would likely allow to pull that factor of $n$.
• Simple arguments that increasing $\delta$ improves security are flawed.
• $\delta=0$ is believed fine.
• The historical reason to introduce a lower bound for $\lvert p-q\rvert$ is that Fermat factorization has cost about proportional to $(p-q)^2/n$ times some polynomial in $k$, thus $\lvert p-q\rvert$ must not be too small. It was jumped from that fact to the conclusion that it's needed to specify an explicit minimum $\lvert p-q\rvert$, even though it's demonstrably enough to specify that $p$ and $q$ are chosen independently and roughly uniformly among primes in some interval like $[2^{(k-1)/2},2^{k/2})$ to insure Fermat factorization is hopeless, whenever $k$ is large enough to resist GNFS (or PPMPQS, which was long known in 1998 when the disputable decision was inked in ANS X9.31).

As requested in comment I'll nevertheless assume there's some reason to specify $\delta$, and that increasing $\delta$ increases security in some domain. In order not to contradict the fact in the first bullet point above, I'll assume $0\le\delta\le\alpha\,k+\beta$ for some reals $\alpha$ and $\beta$ with $\alpha\in[0,1)$. Under such hypothesis, it makes sense to define $\kappa=k+\delta$, and use that as the security parameter.

We could define RSA key generation for constant odd integer $e>1$ as: on input $1^\kappa$

1. In polynomial time, choose integers $k$ and $\delta$ with $\kappa=k+\delta$ and $0\le\delta\le\alpha k+\beta$ (fail if that's impossible); suitable ways include $\delta\gets\left\lfloor\frac\alpha2\kappa\right\rfloor$ and $k\gets\kappa-\delta$.
2. Choose $p$ uniformly randomly among primes $p$ in $[2^{(k-1)/2},2^{k/2})$ with $\gcd(p-1,e)=1$
3. Choose $q$ uniformly randomly among primes $q$ in $[2^{(k-1)/2},2^{k/2})$ with $\gcd(q-1,e)=1$ and $2^\delta<\lvert p-q\rvert$.
4. Compute $n\gets p\,q$ and $d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, output public key $(n,e)$ and private key $(n,d)$.

It's believable that: for any valid choice of $e$ in this key generation algorithm, for any polynomial $P$, there exists no Probabilistic Polynomial Time algorithm that when $\kappa$ grows breaks RSA encryption with non-vanishing probability within time $P(\kappa)$.

That plausible conjecture is demonstrably¹ implied by a commonly held and simpler form of the RSA conjecture for fixed/small public exponent, which removes step (1.), replaces the condition $2^\delta<\lvert p-q\rvert$ with $p\ne q$ in step (3.), and uses $k$ where there's $\kappa$. We have no proof the conjectures are equivalent, but no compelling reason to believe otherwise, thus many practitioners and most theoreticians use the simpler conjecture².

---

¹ Proof sketch: we assume there exists an $e$ and algorithm $\mathcal A$ that breaks RSA encryption with non-vanishing probability within time $P(\kappa)$ when using the RSA key generation with $2^\delta<\lvert p-q\rvert$. We use $\mathcal A$ to build an algorithm $\mathcal A'$ invoking $\mathcal A$ as a subprogram, which for the same $e$ breaks RSA encryption with some probability within time $P'(k)$ when using the RSA key generation with $p\ne q$. The probability is non-vanishing because $p$ and $q$ meet the condition insuring $\mathcal A$ works with a probability that we can lower-bound and is non-vanishing. We can establish $P'$ from $P$, $\alpha$ and $\beta$, and that $P'$ is still a polynomial. $\alpha<1$ comes into play.

² Often the condition $p\ne q$ is removed too, which introduces the possibility that decryption fails. That occurs for a vanishing proportion of generated keys, but some definitions of a cipher have no exclusion for such corner case, which is why we keep $p\ne q$.