Here efficient implies \mathtt{poly}(k).
Let (\mathcal{Y}_k, g) be a metric space with the properties discussed above. Let M_k : \mathcal{X}^n \rightarrow \mathcal{Y}_k be an efficient \varepsilon -IND-CPD mechanism that is \alpha_k accurate for some q: \mathcal{X}^n \rightarrow \mathcal{Y}_k with respect to g. Then the procedure \widetilde{M} that draws a sample uniformly at random from a neighbourhood of radius c_k = O\left(a_k\right) around M_k(X) is (\varepsilon, \mathsf{negl}\left({k}\right)) -DP.
Define \mathsf{Vol}\left(r\right) = |\mathsf{B}\left(a;r\right)| for any a \in \mathcal{Y}_k, which is well defined as (\mathcal{Y}_k, g) is uniform. Define \widetilde{M} as the protocol that samples a uniformly random point from \mathsf{B}\left(M_k(X);c_k\right).
\begin{align*} \text{ }\Pr\left[\widetilde{M}(X) = s\right] &= \frac{1}{|\mathsf{Vol}\left(c_k\right)|}\text{ }\Pr\left[M(X) \in \mathsf{B}\left(s;c_k\right)\right] \end{align*}
Therefore, for any S \subseteq \mathcal{Y}_k, let A = S \cap \mathsf{B}\left(q;a_k + c_k\right) and q=q(X). Then we have,
\begin{align*} \text{ }\Pr\left[\widetilde{M}(X) \in S\right] &\leq \text{ }\Pr\left[\widetilde{M}(X) \in S | \widetilde{M}(X) \in A\right] + \text{ }\Pr\left[MSDP(X) \notin A\right]\\ &\leq \text{ }\Pr\left[\widetilde{M}(X) \in S | \widetilde{M}(X) \in A\right] + \mathsf{negl}\left({k}\right) \tag{a} \\ &\leq \sum_{s \in A} \frac{1}{|\mathsf{Vol}\left(c_k\right)|}\text{ }\Pr\left[M(X) \in \mathsf{B}\left(s;c_k\right)\right] \\ &\leq = \mathsf{negl}\left({k}\right) + \sum_{s \in A} \mathsf{exp}\left( \varepsilon\right)\left(\frac{1}{|\mathsf{Vol}\left(c_k\right)|}\text{ }\Pr\left[M(X') \in \mathsf{B}\left(s;c_k\right)\right] + \mathsf{negl}'(k)\right) \tag{b} \\ &\leq \mathsf{negl}\left({k}\right) + \frac{\mathsf{Vol}\left(a_k + c_k\right)}{\mathsf{Vol}\left(c_k\right)}\mathsf{negl}'(k) + \mathsf{exp}\left( \varepsilon\right)\sum_{s \in A} \frac{1}{|\mathsf{Vol}\left(c_k\right)|}\text{ }\Pr\left[M(X') \in \mathsf{B}\left(s;c_k\right)\right] \\ & = \mathsf{negl}\left({k}\right) + \frac{\mathsf{Vol}\left(a_k + c_k\right)}{\mathsf{Vol}\left(c_k\right)}\mathsf{negl}'(k) + \mathsf{exp}\left( \varepsilon\right)\sum_{s \in A} \text{ }\Pr\left[\widetilde{M}(X') = s\right] \\ &\leq \mathsf{negl}\left({k}\right) + \frac{\mathsf{Vol}\left(a_k + c_k\right)}{\mathsf{Vol}\left(c_k\right)}\mathsf{negl}'(k) + \mathsf{exp}\left( \varepsilon\right)\text{ }\Pr\left[\widetilde{M}(X') \in S\right] \tag{c} \\ &\leq \mathsf{negl}\left({k}\right) + \mathsf{negl}'(k) + \mathsf{exp}\left( \varepsilon\right)\text{ }\Pr\left[\widetilde{M}(X') \in S\right] \tag{d} \end{align*}
(a): M_k is \alpha_k accurate with probability 1-\mathsf{negl}\left({k}\right).
(b): M_k is \varepsilon-CDP.
(c): A \subseteq S.
(d): \frac{\mathsf{Vol}\left(a_k + c_k\right)}{\mathsf{Vol}\left(c_k\right)} = \mathtt{poly}(k) as c=O\left(a_k\right) and the doubling dimension of \mathcal{Y}_k is \log{}k.
Setting \mathcal{Y}_k = \mathbb{R}^d where d=\log{}k. We should note that as algorithms are deployed on computers, and everything is actually discrete, we are not actually dealing with \mathbb{R}^d but instead we are dealing with the discretised version of \mathbb{R}^d with \mathtt{poly}(k) bits of precisions. In that case, the doubling dimension of \mathbb{R}^d is \log{}k (See2), and \mathbb{R}^d satisfies all the properties above3.
TODO