# Multi-users RSA problem

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).

• This problem was studied for DLP and (gap) CDH in a recent Eurocrypt paper. Not sure about the RSA problem. – Occams_Trimmer Jun 3 '20 at 4:05
• 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. – Paŭlo Ebermann Jun 15 '20 at 21:35
• @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. – fgrieu Jun 18 '20 at 18:43