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:
- Challenger draws and submits random $y\in[0,2^{k-1})$
- Adversary chooses and submits $i\in[0,u)$
- 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).
