Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user.

What's the state of the art in the multi-users RSA problem and its reduction to other problems?

Assume a public directory of $u$ public keys $(N_i,e_i)$ all with the same bit size $|N_i|=k$. Assume $N_i=p_i\,q_i$ with $p_i,q_i\in[\,\lceil2^{(k-1)/2}\rceil,2^{k/2}\,)$. Assume these primes chosen independently and uniformly at random among those with $\gcd(p_i-1,e_i)=1=\gcd(q_i-1,e_i)$ for some odd $e_i\ge3$, unless that matters.

Adversaries succeed if they pass this test:

  1. Challenger draws and submits random $y\in[0,2^{k-1})$
  2. Adversary chooses and submits $i\in[0,u)$
  3. Adversary submits $x$ and succeeds if $x^e\bmod N_i=y$.

Make this the multi-users RSA (authentication¹) problem. Add two-pass when we exchange 1 and 2 (forcing the adversary to choose its target before the challenger supplies the challenge $y$), which can only make the attacker's task harder. Add low exponent when $|e|$ is upper-bounded by a constant value. Add fixed exponent when $\forall i,\ e_i=e$.

For concreteness, consider an access control system using Smart Cards to authenticate users, where each has internally drawn a public/private key pair. Assume keys per² FIPS 186-4 appendix B.3, which wants $k\in\{1024,2048,3072\}$ and $|e|\in(16,256]$. Assume $e=65537$ when $e$ is fixed. Noticeably, there are special conditions on the primes mandated specifically when $k=1024$, and part of the question is: are they useful³ for some practical parameter $u$?

¹ Omit authentication unless relevant. We could define a multi-users RSA encryption problem, but it has less practical relevance. And when a legitimate user's ability to decipher random challenges is used to authenticate, that multi-users RSA encryption problem becomes equivalent to our multi-users authentication RSA problem: the restriction $y\in[0,2^{k-1})$ is minor, and using the multiplicative property of RSA can be shown irrelevant, I guess.

² This reference's $nlen$ is our $k$. We use the notation in the landmark proof of PPS by Bellare and Rogaway (1996), and improved proof of FDH by Coron (2000).

³ One of these precautions is that $p-1$ has a large prime factor. This is to guard against Pollard's $p-1$ factoring algorithm. This algorithm is a non-issue in the RSA problem, since factoring algorithms with a much better asymptotic cost are known. That's less evident in the multi-users RSA problem: this algorithm's probability of success grows markedly with $u$ at constant cost, when the parameters $B_1$ and $B_2$ of Pollard's $p-1$ are tuned so that all the $N_i$ can be tested. For $k$ in the low hundreds and $u$ in the millions, it seems this strategy beats ECM with random curves (which giveq the adversary an advantage independent of $u$ AFAIK).

  • 1
    $\begingroup$ This problem was studied for DLP and (gap) CDH in a recent Eurocrypt paper. Not sure about the RSA problem. $\endgroup$ – Occams_Trimmer Jun 3 '20 at 4:05
  • $\begingroup$ How is swapping 1 and 2 making it easier for the attacker? I think it will make it harder, as you have to commit to a user before getting the challenge. $\endgroup$ – Paŭlo Ebermann Jun 15 '20 at 21:35
  • $\begingroup$ @PaŭloEbermann : swapping 1 and 2 does not make things easier for the attacker, thanks for noticing. It makes the attacker's task harder (e.g. an hypothetical technique to solve the RSA problem when $y\equiv n\bmod e)$ gives a smaller advantage). I repaired the question. $\endgroup$ – fgrieu Jun 18 '20 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.