On Single-Server Delegation of RSA

Abstract

In delegated computation research, the main problem asks how a computationally weaker client device can obtain help from one or more computationally stronger servers to perform some computation. Desirable solution requirements include correctness of the computation, privacy of the inputs, high probability detection of any malicious behavior of a server, low client online runtime, low communication complexity, low client storage complexity, and minimal server trust.

In this paper we investigate the problem of single-server delegated computation of the encryption and decryption algorithms in the ubiquitously applied RSA public-key cryptosystem. Our contribution includes state-of-the-art summaries, the first delegated computation protocol for small-exponent RSA encryption, a delegated computation protocol for RSA decryption with improved server runtime and client storage, and an upper bound on the impact of communication on client device energy, which may be of independent interest.

Appendices

On Delegation of RSA Decryption

Previous Work. In [28], the first paper proposing delegation of cryptographic algorithms, the authors presented two protocols for the delegation of RSA decryption. The basic idea of such a protocols was as follows: the client sends some randomized masking of exponent d to the server; the server computes exponentiations to exponents related to the masking, and sends the results to the client; finally, the client uses the mask computation to turn the received exponentiation results into the desired $x^d\mod n$ exponentiation. The specific masking used in the first of their protocols was

$$ d=f_1d_1+\cdots +f_Md_M\mod \phi (n), $$

for some random integers $d_1,\ldots ,d_M$ send by the client to the server, some random bits $f_1,\ldots ,f_M$ kept secret by the client, and some small value M. While this might seem an interesting approach, in that recovering d might seem to require exhaustive search of all possible vectors $(f_1,\ldots ,f_M)$, about 20 papers were published containing faster attacks to their protocols and/or proposing protocol variants and improvements, as well as faster attacks to these variants. The reader is referred to Sect. 2 of [24] and Sect. 1.2 of [29] for a detailed discussion of these papers. All of these results were published before the introduction of a formal delegation model [23], and therefore protocols were described without proofs for their properties, other than sometimes claiming security against all previous attacks. For some of these papers, it might be interesting to study if their techniques suffice to provably achieve some of the properties formally defined in the more recent delegation models. In particular, some of these attacks were based on an attacker’s knowledge of signatures, which would not necessarily be part of the adversary model when considering decryption delegation.

More recently, protocols were proposed [17, 19, 20, 32, 34, 36] where the RSA exponent was hidden in one or more linear equations depending on a random value t in the exponent group. According to our analysys of these protocols: (a) a full-domain value t would perfectly hide the RSA secret key from the server, but require client work comparable to non-delegated computation of RSA decryption; (b) a smaller-size value t would reduce the client’s work but also proportionally reduce the work needed to derive the RSA secret key. Properties (a) and (b) imply that these protocols do not simultaneously satisfy input privacy and client resource efficiency. Indeed, the variant of this approach used in [34] was broken by [7] using lattice-based cryptanalysis techniques.

Other exponent masking attempts were proposed in [31, 33], where the exponent was masked by a multiple of the group order. This would seem a potentially interesting and valid idea, since, on one hand the random value would mask d, and on the other hand the server’s exponentiation to a multiple of the group order would cancel out and allow C to recover an exponentiation to the original exponent. However, these protocols were broken in [2] using lattice-based cryptanalysis techniques.

Finally, [7] proves, in the generic group model, lower bounds on the efficiency of delegation protocols for a class of functions, including one that has some similarity to RSA decryption: public-online-base private-offline-exponent exponentiation in prime-order groups. These results are summarized in Table 4. We note that it is yet unknown if these results can be extended to RSA groups. Even if they were, it would still be possible to design RSA decryption delegation protocols with non-trivial improvements over non-delegated computation.

Table 4. Summary of lower bound results from Theorems in [7] for protocols for the delegation of public-online-base private-offline-exponent exponentiation in prime order groups, in the generic group model, where s is an arbitrary integer. Each row represents a barrier in the sense that a protocol with a better improvement factor than what written in the 2nd column, in a scenario with protocol parameters as described in columns 3–5, would imply an efficient attack that successfully violates input privacy.

Properties of Our Protocol. $\mathcal{P}_{2,d}$. The efficiency properties are verified by protocol inspection; in particular,

• C’s online runtime complexity consists of $k+1$ multiplications, which improves over non-delegated multiplication by a multiplicative factor of $\ge \log b$;

• S’s runtime complexity consists of only k exponentiations, and $b+k-2$ multiplications in $\mathbb {Z}_n^*$;

• the offline runtime complexity consists of 1 product of k exponentiations with k random bases, 1 inversion in $\mathbb {Z}_n^*$, and time linear in |d|;

• with respect to round complexity, $\mathcal{P}_{d,2}$ requires 3 messages between C and S;

• with respect to communication complexity, the online phase of $\mathcal{P}_{d,2}$ requires the transfer of $b+k-1$ values in $\mathbb {Z}_{n}^*$.

To show the correctness property, we note that if C and S follow the protocol, C outputs $m=c^d \mod n$ since $d = (d_{k-1},\ldots , d_1, d_0)_b=\sum _{i=0}^{k-1} d_i\cdot b^i$ and

$$\begin{aligned} m= & {} w_0\cdot v_0 = \prod _{i=0}^k z_i^{b^i} \cdot (\prod _{i=0}^k u_i^{b^i})^{-1} \\= & {} \prod _{i=0}^k (B_{d_i}\cdot u_i)^{b^i} \cdot \prod _{i=0}^k u_i^{-b^i}= \prod _{i=0}^k (B_{d_i})^{b^i} = \prod _{i=0}^k (c^{d_i})^{b^i} = c^{\sum _{i=0}^k d_i\cdot b^i} = c^d \end{aligned}$$

The privacy property of the protocol against a malicious S follows by observing that C’s message to S is a sequence of pseudo-random values in $\mathbb {Z}_n^{*}$ and is thus pseudo-independent from d. Specifically, the values sent by C to S are $z_0,\ldots , z_k$ where $z_i=B_{d_i}\cdot u_i \mod n$ for all $i=0,\ldots , k-1$ and $z_k = m\cdot u_k \mod n$. Note that as $u_0\ldots , u_k$ are chosen as pseudo-random values in $\mathbb {Z}_n^{*}$ using G’s output on input a random seed s, even $z_0, \dots , z_k$ are pseudo-random values in $\mathbb {Z}_n^{*}$. Thus, under the assumption that G is pseudo-random, the probability that any efficient malicious S learns some additional information about private exponent d, is negligible.

Delegation of Multiplication in $\mathbb {Z}_n^*$

We show how a quasilinear-time client can delegate modular multiplication in the group $\mathbb {Z}_n^*$, where n is an RSA group, in the input case where both factors are public online. (Here, by quasilinear-time client we mean a client that only performs modular additions/subtractions, reductions modulo small primes, and/or multiplications of small integers modulo small primes). The delegation protocol is obtained as a direct generalization of the analogue protocol in [13] for modular multiplication in the group $\mathbb {Z}_p^*$, where p is a prime. It turns out that after replacing a prime modulus with a non-prime modulus in the protocol from [13], all protocol’s poperties still hold, with only syntactic changes to their proofs.

Informal Description of ${\mathcal {P}}_{m}$. The protocol in [13] improves Yao’s generalization [37] of Pippenger’s idea (see, e.g., example 2 in [25]) to efficiently verify integer equations modulo small primes, and adapts it from $\mathbb {Z}$ to $\mathbb {Z}^*_p$. In that protocol, a server would send the product w of the two input integers a and b, and the integer equation $w=a\cdot b$ is verified modulo a small random prime chosen by the client. Directly extending the protocol from [13], a server sends quotient $w_0$ and reminder $w_1$ of the division of w by n, and the integer equation $w_0\cdot n+w_1=a\cdot b$ is verified modulo a small random prime by the client, which can then obtain $w_1$ as the desired $a\cdot b\mod n$ value.

Formal Description of ${\mathcal {P}}_{m}$. Consider algebraic group $\mathbb {Z}^*_n$. We now formally describe a 1-server protocol ${\mathcal {P}}_m=(C, S)$ for the delegation of multiplication of public online group values a and b in $\mathbb {Z}^*_n$, where $|a|=|b|= \sigma$, and with statistical parameter $\lambda$. By $\pi (x)$ we denote the number of prime integers $\le x$.

Offline Input: $1^\sigma ,1^\lambda$, $n\in \{0,1\}^\sigma$

Offline phase instructions:

• 1. Randomly chooses a prime $t<2^\eta$, where $\eta =\lceil \lambda +\log _2\lambda +\log _2(\pi (2\sigma ))\rceil$

• 2. Compute $n'=n\mod t$

• 3. Return: $(t,n')$ and store this pair on C’s device

Online Input to C and S: $1^\sigma ,1^\lambda$, $n\in \{0,1\}^\sigma$, $a,b\in \mathbb {Z}^*_n$

Online Input to C: $t,n'$

Online phase instructions:

• 1. S computes $w:=a\cdot b$ (i.e., the product, over $\mathbb {Z}$, of a, b, considered as integers)

  S computes $w_0,w_1$ such that $w=w_0\cdot n+w_1$ (over $\mathbb {Z}$), where $0 \le w_1 <n$

  S sends $w_0,w_1$ to C

• 2. C computes $w_0':=w_0 \mod t$ and $w_1':=w_1 \mod t$

  C computes $a':=a \mod t$ and $b':=b \mod t$

  If $a'\cdot b'\ne w_0'\cdot n'+w_1' \mod t$ then

        C returns: $\perp$ and the protocol halts

  C returns: $y:=w_1$

In [13], protocol ${\mathcal {P}}_{m}$ is proved to satisfy 1-correctness, unbounded $2^{-\lambda }$-security and $(t_{F},t_{S},t_{P},t_{C},cc,sc,mc)$-efficiency, where $cc=2$, $sc=2$, $mc=2$, $t_F=$ 1 multiplication mod p, $t_C=$ 4 $\eta$-bit-modulus reductions + 2 $\eta$-bit-values multiplications + 1 $\eta$-bit-value addition, $t_S=$ 1 multiplication + 1 division $\mod n$, and $t_P=$ 1 $\eta$-bit random prime generation + 1 $\eta$-bit-modulus reduction. In particular, C’s online computations only consist of 4 reductions modulo q and 2 multiplications modulo q, where q is a small, $\eta$-bit, modulus.

Public-Base Small-Exponent Exponentiation in $\mathbb {Z}_n^*$

We show how to delegate small-exponent exponentiation in the RSA group $\mathbb {Z}_n^*$, in the input case where the base is public online and the exponent is public offline. This is obtained as a direct extension of the analogue result from [15] in the algebraic group $\mathbb {Z}_p^*$, where p is a prime. The extension consists of replacing the subprotocol for delegating multiplication mod p with the subprotocol for delegating multiplication mod n from Appendix B. We obtain the following

Theorem 3

Let $\sigma$ be computational security parameter, let $\lambda$ be a statistical security parameter, and let ${\mathcal {P}}_{m}$ be the single-server protocol for delegating computation of the multiplication operation in group $\mathbb {Z}_n^*$, satisfying 1-correctness, unbounded $2^{-\lambda }$-security and $(t'_{F},t'_{S},t'_{P},t'_{C},cc',sc',mc')$-efficiency, as described in Appendix B. There exist (constructively) a single-server protocols ${\mathcal {P}}_{e,pub}$ for delegating computation of small-exponent exponentiation in the same group for the input case where base $x\in \mathbb {Z}_n^*$ is public online and exponent $e\in \{0,1\}^a$ is public offline, satisfying unbounded 1-decryption-correctness, unbounded $2^{-\lambda }$-security, and $(t_{F},t_{S},t_{P},t_{C},cc,sc,mc)$-efficiency, where

• $t_F\le 2a\cdot t'_F$, $t_S\le 2a\cdot t'_S$, $t_P= t'_P$, $t_C\le 2a\cdot t'_C$,

• $cc\le 2a\cdot cc'+2$, $sc= sc'$, and $mc=2$.

Informal Description of ${\mathcal {P}}_{e,pub}$. Analogously as in [15], our protocol ${\mathcal {P}}_{e,pub}$ can be seen as an optimized simulation of the (iterative) square and multiply algorithm for modular exponentiation, while using a multiplication delegation subprotocol, such as the scheme ${\mathcal {P}}_{m}$ in Appendix B, to compute squares and multiplications modulo n in this algorithm. A first optimization consists of running all executions of protocol ${\mathcal {P}}_{m}$ in parallel instead of sequentially. Specifically, sequential black-box runs of protocol ${\mathcal {P}}_{m}$ at each squaring or multiplication step would result in up to 2a messages, where $a=\lceil \log (x+1)\rceil$. Instead, since the online phase of ${\mathcal {P}}_{m}$ only consists of a single message from S to C, and at the end of the protocol, both S and C can compute the computation result, all executions of ${\mathcal {P}}_{m}$ can be run in parallel, and so ${\mathcal {P}}_e$ consists of a single message from S to C. As a second optimization, we observe that the offline phase of ${\mathcal {P}}_{m}$ can be only run once, even if we run the online phase of the same protocol up to 2a times. This follows from the unbounded security property of ${\mathcal {P}}_{m}$, which we use to keep C’s storage complexity independent on a. Finally, we note that in the executions of protocol ${\mathcal {P}}_{m}$, we set statistical parameter $\lambda _m=\lambda +\lceil \log (2a)\rceil$, where $\lambda$ is the statistical parameter desired for protocol ${\mathcal {P}}_{e}$, to guarantee enough verification confidence for all (up to) 2a squares or multiplications.

Formal Description of ${\mathcal {P}}_{e,pub}$. By ${\mathcal {P}}_{m}=(\text{ Offline}_{m},S_{m},C_{m})$ we denote a protocol for the delegation of $a\cdot b\mod n$ with statistical parameter $\lambda _m$, where a and b are public online, such as the protocol in Appendix B. In particular, the notation $(q,r)\leftarrow S_{m}(out,a,b)$ refers to an execution of the ${\mathcal {P}}_{m}$ server’s algorithm with offline-phase input out and online-phase inputs a, b, returning message (q, r) for C, such that $a\cdot b=q\cdot n+r$, where $0\le r<n$. Similarly, the notation $d\leftarrow C_{m}(out,q,r)$ refers to an execution of the ${\mathcal {P}}_{m}$ client’s algorithm with offline-phase input out, online-phase inputs a, b, and server’s message (q, r), and returning decision bit d where $d=1/0$ depending on whether $C_{m}$ accepts/does not accept the statement $r=a\cdot b\mod n$. We now formally describe protocol ${\mathcal {P}}_{e,pub}$ to delegate small-exponent exponentiation $\mathsf{seExp_{n,e,a}}(x)=x^e\mod n$ in a group $\mathbb {Z}^*_n$, where x is public online and e is public offline.

Offline Input: $1^\sigma ,1^\lambda ,1^a$, $n\in \{0,1\}^\sigma$, public exponent $e\in \{0,1\}^a$

Offline phase of ${\mathcal {P}}_e$:

• 1. Run the offline-phase algorithm $\text{ Offline}_{m}$ from protocol ${\mathcal {P}}_{m}$

• 2. Store the resulting output out on C’s device

Online Input to C and S: $1^\sigma ,1^\lambda ,1^a$, $n\in \{0,1\}^\sigma$, $x\in \mathbb {Z}_n^*$, $e\in \{0,1\}^a$

Online phase of ${\mathcal {P}}_e$:

• 1. S sets $z=x$, $y=1$ and $i=1$

• 2. While $e>1$ do

     if e is even then

        S computes $(q_{1i},r_{1i})=S_{m}(z,z)$

        S sets $z=r_{i1}$, $q_{2i}=r_{2i}=0$, $i=i+1$ and $e=e/2$

     if e is odd then

        S computes $(q_{1i},r_{1i})=S_{m}(z,y)$ and $(q_{2i},r_{2i})=S_{m}(z,z)$

        S sets $y=r_{i1}$, $z=r_{i2}$, $i=i+1$ and $e=(e-1)/2$

• 3. S computes $(q,r)=S_{m}(z,y)$

• 4. S sends $((q_{11},r_{11},q_{21},r_{21}),\ldots ,(q_{1a},r_{1a},q_{2a},r_{2a}),(q,r))$ to C

• 5. C sets $y=1$ and $i=1$

• 6. While $e>1$ do

     if e is even then

        C computes $d_{1i}=C_{m}(out,q_{1i},r_{1i})$

        if $d_{1i}= 0$ then C halts

           else C sets $z=r_{i1}$, $i=i+1$ and $e=e/2$

     if e is odd then

        C computes $d_{1i}=C_{m}(out,q_{1i},r_{1i})$ and $d_{2i}=C_{m}(out,q_{2i},r_{2i})$

        if $d_{1i}= 0$ or $d_{2i}= 0$ then C halts

           else C sets $y=r_{i1}$, $z=r_{i2}$, $i=i+1$ and $e=(e-1)/2$

• 7. C computes $l=C_{m}(out,q,r)$

• 8. If $l= 0$ then C halts else C returns: $y=r$

Properties of ${\mathcal {P}}_{e,pub}$. The efficiency properties of ${\mathcal {P}}_{e,pub}$ follow by protocol inspection, and by observing that ${\mathcal {P}}_{e,pub}$ runs ${\mathcal {P}}_{m}$ up to 2a times, with statistical parameter $\lambda _m=\lambda +\lceil \log (2a)\rceil$. In particular, we note that: (1) the online phase of ${\mathcal {P}}_{e,pub}$ consists of a single round message complexity from C to S and then followed by S to C since it parallelizes the $\le 2a$ executions of protocol ${\mathcal {P}}_{m}$; (2) the offline phase runtime includes the runtime of one execution of the offline phase of ${\mathcal {P}}_{m}$; only one thanks to the unbounded security of ${\mathcal {P}}_{m}$.

The 1-correctness property of ${\mathcal {P}}_{e,pub}$ follows by observing that at the end of the protocol C can compute $y=x^e \mod n$ with probability 1. This follows by combining these 2 facts: (1) At the end of each execution of subprotocol ${\mathcal {P}}_{m}$ on input (a, b), C can compute $a\cdot b\mod n$; (2) If subprotocol ${\mathcal {P}}_{m}$ allows C to obtain a (delegated) computation of multiplication $\mod n$, then protocol ${\mathcal {P}}_{e,pub}$ allows C to obtain a (delegated) computation of the output of the iterative version of the square-and-multiply algorithm for exponentiation $\mod n$ and obtain $r = z^e \mod n = x^e \mod n$. Fact (1) follows from the 1-correctness of subprotocol ${\mathcal {P}}_{m}$. Fact (2) follows by induction on variable i in the while loops in protocol ${\mathcal {P}}_e$, after observing that protocol ${\mathcal {P}}_{e,pub}$ realizes the square-and-multiply algorithm, where computation of multiplications is delegated via ${\mathcal {P}}_{m}$.

The unbounded $2^{-\lambda }$-security property of ${\mathcal {P}}_{e,pub}$ follows from the 1-correctness property of ${\mathcal {P}}_{e,pub}$, the unbounded $2^{-\lambda }$-security property of protocol ${\mathcal {P}}_{m}$ and the setting $\lambda _m=\lambda +\lceil \log (2a)\rceil$. First, we observe that if S returns correct values when running protocol ${\mathcal {P}}_{m}$, then the 1-correctness property implies that C returns a correct output $y=x^e\mod n$ with probability 1. Thus, the probability $\epsilon _s$ that C accepts a value $y\ne x^e \mod n$ is upper bounded by the probability that C accepts an incorrect result in any one of the $\le 2a$ executions of protocol ${\mathcal {P}}_{m}$. By a union bound, we have that

$$ \epsilon _s\le \sum _{i=1}^{2a}\frac{1}{2^{\lambda _m}}\le \sum _{i=1}^{2a}\frac{1}{2^{\lambda +\lceil \log (2a)\rceil }}\le \frac{1}{2^{\lambda }}\sum _{i=1}^{2a}\frac{1}{2a} = 2^{-\lambda }. $$