Weird n_{rsa} usage in the paper

[fjarri]

Definition 3.1 in the 2024 version of the CGGMP paper reads:

So is n_{rsa} the bit length of a single prime, or of N? And where does the [n_rsa, n_rsa + 4) bound come from (and can we use it to speed up our search for primes?).

[dvdplm]

I read it as n_rsa is the bitlength of N and the funny bound notation means that n_rsa has two MSBs set, so that N lies in the upper quarter of the n_rsa-bits long N.

FWIW I think there's a comma missing and that they meant to write: "…that returns a Paillier-Blum modulus N with its factorization, consisting of two primes p,q, of bitlength b ∈ [n_rsa, n_rsa + 4)…" (added a comma after "p, q").

[fjarri]

FWIW I think there's a comma missing and that they meant to write: "…that returns a Paillier-Blum modulus N with its factorization, consisting of two primes p,q, of bitlength b ∈ [n_rsa, n_rsa + 4)…" (added a comma after "p, q").

Hm, quite possible, the phrasing is unfortunate.

and the funny bound notation means that n_rsa has two MSBs set

Do you mean, N has two MSBs set? Or p and q? n_rsa will be something like 2048.

[dvdplm]

Do you mean, N has two MSBs set? Or p and q? n_rsa will be something like 2048.

What I mean is that if p and q have the two MSBs set, then N will be guaranteed to have exactly 2048 bits (given p and q of 1024 bits), and it also means that the range of possible N is in [n/4...n-1]. But that said, I'm not sure if this is what they mean with "bitlength b ∈ [n_rsa, n_rsa + 4)". :/