1
$\begingroup$

pqRSA is MP-RSA with 4096-bit primes to build up a modulus of up to 1TB.

If the objective is to make processing the modulus as expensive as possible for the quantum computer why not use just two 4096-bit primes with the rest being 1024-bit primes? Would that offer comparable security?

$\endgroup$
2
  • $\begingroup$ I'd wager that unless the combination of the multiplication of the primes are quantum safe (and it isn't) the combined quantum complexity is basically not the multiplication of the complexities of having 2 + 1 primes (etc.). That's my intuition, you'd have to dive into the paper to find out. $\endgroup$
    – Maarten Bodewes
    Dec 15, 2023 at 20:27
  • 1
    $\begingroup$ @kodlu I've included a link; it is a joke submission (by DJB) to NIST PQC competition, more information on our own site $\endgroup$
    – Maarten Bodewes
    Dec 15, 2023 at 20:33

1 Answer 1

2
$\begingroup$

No, it would not. As noted in the PQ-RSA paper, there is a Grover accelerated form of the elliptic curve method GEECM which can detect a prime factor $p$ of $N$ with $L_p[1/2,1]$ quantum work (essentially by performing a Grover search for an elliptic curve mod $p$ with smooth order). One could use this to extract all of the 1024-bit primes with work only half of the security margin. We’d then be left with a product of 2 4096-bit primes which would be trivial for Shor’s algorithm.

$\endgroup$
2
  • $\begingroup$ Is the quantum cost 1/2 in relation to modulus bit size or something else? $\endgroup$
    – user113099
    Dec 15, 2023 at 23:57
  • $\begingroup$ @JamesArlington for an $L_p[1/2,1]$ algorithm the cost in bits roughly scales according to the square root of the bit size of $p$. I our case then, if it takes $2^\lambda$ quantum operations to detect a 4096-bit prime, then it takes roughly $2^{\lambda/2}$ quantum operations to detect a 1024-bit primes. $\endgroup$
    – Daniel S
    Dec 16, 2023 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.