%%%%%%%% ICML 2026 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%

\documentclass{article}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{booktabs} % for professional tables
\usepackage[numbers,sort&compress]{natbib}
\usepackage{algorithm}
\usepackage{algorithmic}

% hyperref makes hyperlinks in the resulting PDF.
% If your build breaks (sometimes temporarily if a hyperlink spans a page)
% please comment out the following usepackage line and replace
% \usepackage{icml2026} with \usepackage[nohyperref]{icml2026} above.
\usepackage{hyperref}


% Attempt to make hyperref and algorithmic work together better:
\providecommand{\theHalgorithm}{\arabic{algorithm}}

% arXiv version: use standard article layout instead of the ICML style.
\usepackage[margin=1in]{geometry}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{thm-restate}

% if you use cleveref..
\usepackage[capitalize,noabbrev]{cleveref}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% THEOREMS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

% Avoid duplicate hyperref destinations when theorem counters reset by section.
\makeatletter
\providecommand*{\theHtheorem}{\thesection.\arabic{theorem}}
\providecommand*{\theHproposition}{\theHtheorem}
\providecommand*{\theHlemma}{\theHtheorem}
\providecommand*{\theHcorollary}{\theHtheorem}
\providecommand*{\theHdefinition}{\theHtheorem}
\providecommand*{\theHassumption}{\theHtheorem}
\providecommand*{\theHremark}{\theHtheorem}
\makeatother

% Todonotes is useful during development; simply uncomment the next line
%    and comment out the line below the next line to turn off comments
%\usepackage[disable,textsize=tiny]{todonotes}
% \usepackage[textsize=tiny]{todonotes}
\usepackage[disable,textsize=tiny]{todonotes}

% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\title{Shuffling-Aware Optimization for Private Vector Mean Estimation}
\pdfstringdefDisableCommands{%
  \def\chi{chi}%
  \def\sigma{sigma}%
  \def\varepsilon{epsilon}%
  \def\delta{delta}%
}

\author{
Shun Takagi\\
LY Corporation, Tokyo, Japan\\
\texttt{shutakag@lycorp.co.jp}
\and
Seng Pei Liew\\
LY Corporation, Tokyo, Japan\\
\texttt{sliew@lycorp.co.jp}
}


 
\begin{document}

\maketitle


\begin{abstract}
We study $d$-dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. 
While minimax-optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. 
To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. 
We then establish a minimax lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. 
Finally, we construct an asymptotically minimax optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism.
\end{abstract}


\section{Introduction}
\label{sec:introduction}

Differential privacy (DP)~\cite{dworkDifferentialPrivacy2006b,dworkAlgorithmicFoundationsDifferential2013a} enables principled privacy-preserving data analysis.
In the central model, a trusted curator collects raw data and releases a
privatized aggregate, achieving strong utility at the cost of a strong trust
assumption.
In the local model (LDP)~\cite{duchiLocalPrivacyStatistical2013}, each user randomizes their data before communication, removing the need for trust but often degrading accuracy significantly.
The shuffle model~\cite{erlingssonAmplificationShufflingLocal2019,cheuDistributedDifferentialPrivacy2019,ballePrivacyBlanketShuffle2019,feldmanHidingClonesSimple2022} offers an appealing intermediate point: users send locally randomized messages through an anonymization layer (the shuffler), which permutes the reports before analysis.
By breaking the linkage between users and messages, shuffling amplifies privacy and can approach central-model utility.


We focus on the single-message randomize-then-shuffle setting~\cite{ballePrivacyBlanketShuffle2019}, where each user sends exactly one privatized message.
This is the simplest and most practical instantiation of the shuffle model, and it also serves as a basic component for understanding more complex multi-message constructions~\cite{asiPrivateVectorMean2024}.
Despite its importance, optimal mechanism design for fundamental statistical tasks in the single-message shuffle model remains poorly understood.


In this work we study $d$-dimensional mean estimation over the unit $\ell_2$ ball
$\mathbb B_2^d$.
Given inputs $x_1,\ldots,x_n\in\mathbb B_2^d$, the goal is to estimate the mean
$\frac1n\sum_{i=1}^n x_i$ from the shuffled multiset of privatized
messages.
While minimax-optimal mechanisms are well understood under LDP~\cite{asiOptimalAlgorithmsMean2022}, the analogous question after shuffling has remained largely unexplored: which local randomizer yields the best accuracy under a shuffled DP constraint?
A key difficulty is that privacy after shuffling is inherently global and depends on $n$ and on privacy amplification, making it hard to pose an explicit optimization problem in terms of the local randomizer alone.
As a result, existing approaches often design mechanisms for LDP and then apply amplification, implicitly assuming that local optimality transfers to the shuffled setting.


We address this gap using the recently proposed shuffle index~\cite{takagiAnalysisShufflingPure2026}, a scalar quantity determined solely by the structure of the local randomizer.
In the high privacy regime, the privacy profile~\cite{ballePrivacyAmplificationSubsampling2018a} of the shuffled mechanism is asymptotically governed by the shuffle index in a monotone way as $n\to\infty$, which allows us to replace a global $(\varepsilon,\delta)$ constraint by a local constraint.
This yields a clean post-shuffling mechanism design problem: minimize the worst-case mean squared error (MSE) among unbiased single-message protocols subject to a shuffle-index constraint.


Our main results show that this formulation leads to a sharp minimax theory.
We prove a minimax lower bound showing that any unbiased protocol with shuffle index $\chi$ must incur worst-case MSE at least $d\chi^2$.
This bound implies that LDP-optimal mechanisms can be suboptimal after shuffling.
In particular, we show that PrivUnit~\cite{bhowmickProtectionReconstructionIts2019}, which is minimax-optimal for mean estimation under LDP, fails to attain the shuffle-index lower bound by a constant factor in high dimensions.


Finally, we construct an explicit mechanism that asymptotically matches the
lower bound in the high privacy regime.
Our blanket-mixed Gaussian local randomizer outputs a Gaussian with mean $0$ with some probability and otherwise outputs a Gaussian centered at the user's input, together with a universal unbiased estimator.
We achieve MSE $d\chi^2(1+o(1))$ as $\chi\to \infty$, establishing asymptotic minimax optimality.
Moreover, we prove a central-limit-type correspondence: in the high privacy regime $\varepsilon_n=O(\sqrt{\log n/n})$, the privacy profile of our shuffled mechanism converges to that of the central Gaussian mechanism with the matching noise level, which sharpens earlier order-level and empirical observations in~\cite{chenPrivacyAmplificationCompression2023} by establishing a precise theoretical correspondence, matching constants.



\subsection{Related Work and Contributions}
\label{sec:related-work}


\paragraph{Lower bounds.}
For single-message shuffled mean estimation, most existing lower bounds are typically stated in a form that is uniform over $\varepsilon$~\cite{ballePrivacyBlanketShuffle2019,asiPrivateVectorMean2024} (i.e., $\Omega\left(d\,n^{-2/(d+2)}\right)$), which is well suited to the moderate-privacy regime but provides limited resolution in the high privacy scaling $\varepsilon_n = o(1)$ as $n\to\infty$.
In the high privacy regime, it is common to compare shuffled protocols against trivial lower bounds obtained by invoking minimax lower bounds for mean estimation of the central model~\cite{caiCostPrivacyOptimal2021}.
However, such central-model lower bounds ignore the shuffling structure entirely and can therefore be loose.
Moreover, central-model lower bounds are rarely suited to resolving fine-grained privacy–utility trade-offs (e.g., matching leading constants).


\paragraph{Upper bounds.}
In the single-message shuffle model, order-optimal protocols are known in the moderate-privacy regime $\varepsilon_n=\Theta(1)$ (see, e.g., \citet{ballePrivacyBlanketShuffle2019,asiPrivateVectorMean2024}).
In the high privacy scaling $\varepsilon_n = o(1)$, there are also constructions achieving the corresponding order-optimal rates up to constant factors~\cite{chenPrivacyAmplificationCompression2023}.
Moreover, the resulting MSE is suggestive of convergence up to constants to that of the central Gaussian mechanism as $\varepsilon_n$ decreases.
What has been missing, however, is a theory establishing whether and in what sense single-message shuffling can match the central Gaussian trade-off in the high privacy regime, and how the approach to the Gaussian limit depends quantitatively on the scaling of $\varepsilon_n$.


\citet{scottAggregationTransformationVectorValued2022} propose a single-message vector aggregation protocol, but their analysis incurs additional error terms stemming from coordinate/dimension sampling, which can make the resulting upper bounds loose in regimes where one aims for sharp constants.
While one can alternatively formulate and optimize protocols under an explicit communication constraint, as explored, for instance, by \citet{chenPrivacyAmplificationCompression2023}, in this work we primarily focus on the privacy-utility trade-off and do not attempt to optimize communication.


\paragraph{Multi-message shuffling.}
Multi-message shuffle protocols appear in (at least) two distinct forms.
In the first, each user decomposes their contribution into multiple messages
(multi-message per user), which are then shuffled jointly.
These additional messages can strictly increase what is achievable: in the
$1$-dimensional mean estimation, there are multi-message constructions whose
accuracy can surpass that of the central Gaussian mechanism at comparable privacy
levels \cite{ghaziDifferentiallyPrivateAggregation2021}.
For $d>1$, however, no comparably efficient multi-message-per-user protocols are
known that provably beat the central Gaussian mechanism.


In the second form, one repeats a single-message shuffled
primitive over multiple rounds and composes the privacy losses
(multi-round shuffling).
This is the dominant approach in $d>1$, where mean estimation is invoked repeatedly and one can exploit composition to convert many high privacy rounds into an overall moderate-privacy guarantee~\cite{asiPrivateVectorMean2024,chenPrivacyAmplificationCompression2023}.
Such multi-round constructions are known to approach the privacy-utility trade-off of the central model \cite{girgisRenyiDifferentialPrivacy2021a,erlingssonEncodeShuffleAnalyze2020}, which in turn highlights the importance of understanding the single-round high privacy single-message primitive sharply, since it governs the per-round error and the quality of the composed guarantee.

\paragraph{Contributions.}
\begin{itemize}
    \item 
    Using the shuffle index, we formulate post-shuffle mechanism design for unbiased single-message mean estimation as an explicit optimization problem, and prove a sharp minimax lower bound $\mathrm{MSE} \ge d\chi^2$ in the high privacy regime.

    \item 
    We show that LDP-minimax-optimal primitives (e.g., PrivUnit) can be strictly suboptimal after shuffling and construct a blanket-mixed Gaussian mechanism that is asymptotically minimax optimal, achieving $\mathrm{MSE} = d\chi^2(1+o(1))$ as $\chi \to \infty$.

    \item 
    In the high privacy scaling, we establish a Gaussian-limit correspondence: the privacy-utility trade-off of our shuffled mechanism converges to that of the central Gaussian mechanism with matching noise level, and we validate the theoretical predictions via numerical experiments.
\end{itemize}


\section{Preliminaries}

\subsection{Notations}
We write $\mathbb{R}$ for the set of real numbers. 
For $d\ge 1$, let $\mathbb{B}_2^d := \{x\in\mathbb{R}^d : \|x\|_2 \le 1\}$ and
$\mathbb{S}^{d-1} := \{u\in\mathbb{R}^d : \|u\|_2 = 1\}$ denote the unit $\ell_2$ ball and the unit sphere, respectively.
Throughout the paper, the input space is denoted by $\mathcal X$; we typically take $\mathcal X=\mathbb{B}_2^d$.
$\mathrm{Var}$ and $\mathbb{E}$ denote variance and expectation, respectively.
We use standard asymptotic notations $O(\cdot)$, $o(\cdot)$, $\Omega(\cdot)$, $\omega(\cdot)$, and $\Theta(\cdot)$.

\subsection{Single-message Shuffling}
We briefly review the single-message randomize-then-shuffle model~\cite{ballePrivacyBlanketShuffle2019}.

\begin{definition}[Local randomizer with a blanket distribution~\cite{ballePrivacyBlanketShuffle2019}]
A local randomizer is a randomized mechanism
$
  \mathcal R : \mathcal X \to \mathcal Y .
$
For each input $x\in\mathcal X$, we write $\mathcal R_x$ for the law of
the random output $\mathcal R(x)$.
We denote by $\mathcal R_x(y)$ the corresponding probability density function.
If there exists a scalar $\gamma\in(0,1]$, a probability density $\mathcal R_{\mathrm{BG}}$ on $\mathcal Y$, and a family of probability densities
$\{Q_x\}_{x\in\mathcal X}$ on $\mathcal Y$ such that, for every
$x\in\mathcal X$ and almost every $y\in\mathcal Y$,
\[
  \mathcal R_x(y)
  =
  \gamma\,\mathcal R_{\mathrm{BG}}(y)
  +
  (1-\gamma)\,Q_x(y),
\]
$\mathcal R_{\mathrm{BG}}$ is called a blanket
distribution of $\mathcal R$~\cite{takagiAnalysisShufflingPure2026}, and the
scalar $\gamma$ is called the blanket mass.
\end{definition}

We assume access to an ideal shuffler as a black box.

\begin{definition}[Single-message shuffling and shuffled mechanism]
\label{def:single-message-shuffle}
Let $\mathcal R$ be a local randomizer. Given a dataset $x_{1:n}\in\mathcal X^n$, each user $i\in[n]$ applies the
local randomizer to obtain a single message
$
  Y_i := \mathcal R(x_i)\in\mathcal Y.
$
The shuffler is a randomized map
$
  \mathcal S:\mathcal Y^n\to\mathcal Y^n
$
which samples a permutation $\pi$ uniformly at random from the symmetric
group on $[n]$ and outputs
$
  \mathcal S(y_1,\dots,y_n)
  := (y_{\pi(1)},\dots,y_{\pi(n)}).
$
The shuffled mechanism is defined as $\mathcal{M}=\mathcal{S} \circ \mathcal{R}^n$, where $\mathcal R^n$ denotes the application of $\mathcal R$ independently to each record.
\end{definition}


\paragraph{Unbiased estimators.}
Let $\mathcal{R}$ be a local randomizer.
A pair $(\mathcal{R}, \mathcal{A})$ is called unbiased if
\[
\mathbb E_{Y\sim \mathcal{R}_x}[{\mathcal{A}} (Y)] = x
\qquad\text{for all }x\in\mathcal X.
\]

In the dataset setting, we say that a pair $(\mathcal{R}^n, \mathcal{A})$ is unbiased if
\[
\mathbb E\!\left[\mathcal A\!\left(\mathcal S\circ\mathcal R^n(x_{1:n})\right)\right]
=
\frac{1}{n}\sum_{i=1}^n x_i
\qquad\text{for all } x_{1:n}\in\mathcal X^n.
\]

\subsection{Differential Privacy (DP)}


We recall the notion of DP and express it in a form based on the hockey-stick divergence.

\begin{definition}[Hockey-stick divergence]
Let $\mathcal Y$ be an output space.
Let $P$ and $Q$ be probability distributions on $\mathcal Y$ that admit densities $p$ and $q$, and fix a
parameter $\alpha \ge 1$.
The hockey-stick divergence of $P$ from $Q$ of order $\alpha$ is 
\[
  \mathcal D_{\alpha}(P\|Q)
  :=
  \int_{\mathcal Y} \bigl[p(y) - \alpha\,q(y)\bigr]_+\,dy,
\]
where $[u]_+ := \max\{u,0\}$.
\end{definition}

\begin{definition}[DP~\cite{dworkAlgorithmicFoundationsDifferential2013a, bartheDifferentialPrivacyComposition2013}]
A mechanism is a randomized map
$
  \mathcal M : \mathcal X^n \to \mathcal Z
$
that takes a dataset $x_{1:n}\in\mathcal X^n$ as input and outputs a
random element of $\mathcal Z$.
For each dataset $x_{1:n}$ we write $\mathcal M(x_{1:n})$ for the
corresponding output distribution on $\mathcal Z$, and we denote its
density by the same symbol when convenient.
For a mechanism $\mathcal M$, $\varepsilon\ge0$, and $\delta\in [0,1]$, $\mathcal M$ is $(\varepsilon,\delta)$-DP if and only if
\[
  \delta_\mathcal{M}(\varepsilon):=\sup_{x_{1:n}\simeq x'_{1:n}}
  \mathcal D_{e^\varepsilon}\bigl(\mathcal M(x_{1:n}) \,\big\|\, \mathcal M(x'_{1:n})\bigr)\leq \delta,
\]
where $x_{1:n}\simeq x'_{1:n}$ indicates that the datasets $x_{1:n}$ and $x'_{1:n}$ are \emph{neighboring}.
The function $\delta_\mathcal{M}(\varepsilon)$ is referred to as the privacy profile of $\mathcal M$~\cite{ballePrivacyAmplificationSubsampling2018a}.
\end{definition}


We adopt zero-out neighboring~\cite{kairouzPracticalPrivateDeep2021} as the adjacency relation.
To this end, introduce a special symbol $\perp\notin\mathcal X$ and consider the extended domain
$\mathcal X_\perp := \mathcal X\cup\{\perp\}$.
For $a,b\in\mathcal X_\perp$, we write $a\simeq b$ if
\[
(a=\perp \ \text{and}\ b\in\mathcal X)
\quad\text{or}\quad
(b=\perp \ \text{and}\ a\in\mathcal X).
\]
Two datasets $x_{1:n},x'_{1:n}\in\mathcal X_\perp^n$ are zero-out neighboring,
denoted by $x_{1:n}\simeq x'_{1:n}$, if there exists $i\in[n]$ such that
$x_j=x'_j$ for all $j\neq i$ and $x_i\simeq x'_i$.
This is convenient for analysis in distributed settings where the dataset size is public.
Moreover, the standard replace-one adjacency can be simulated by two zero-out neighboring steps. 
If a mechanism is $(\varepsilon,\delta)$-DP under zero-out neighboring, then it is $(2\varepsilon,2\delta)$-DP under the replace-one adjacency.
We may define the output distribution on input $\perp$ arbitrarily, and we choose it to be the blanket distribution of the local randomizer to simplify the analysis: $\mathcal{R}_\perp := \mathcal{R}_{\mathrm{BG}}$.


\subsection{Shuffle Index}

Given local randomizer $\mathcal R$, define the \emph{generalized privacy amplification random variable}~\cite{ballePrivacyBlanketShuffle2019, takagiAnalysisShufflingPure2026}
$\ell_\varepsilon(\,\cdot\,;x,x',\mathcal R_{\mathrm{ref}}):\mathcal Y\to\mathbb R$ by
\[
  \ell_\varepsilon(Y;x,x',\mathcal R_{\mathrm{ref}})
  :=
  \frac{\mathcal R_x(Y) -e^\varepsilon\,\mathcal R_{x'}(Y)}
       {\mathcal R_{\mathrm{ref}}(Y)}.
\]
Using $\ell_0(\cdot;\,x,x',\mathcal R_{\mathrm{ref}})$ and blanket mass $\gamma$, we introduce two quantities that summarize the privacy amplification due to shuffling.


\begin{definition}[Shuffle index~\cite{takagiAnalysisShufflingPure2026}]
Let $\gamma\in(0,1]$ be the blanket mass of $\mathcal{R}$.
The \emph{lower shuffle index} is
\[
  \chi_{\mathrm{lo}}(\mathcal R)
  :=
  1/\sup_{x_1\simeq x_1'\in\mathcal X_\perp}
  \sqrt{
    \frac{1}{\gamma}\,
    \mathrm{Var}_{Y\sim \mathcal{R}_{\mathrm{BG}}}
    \!\left[
      \ell_0\!\left(Y; x_1,x_1',\mathcal{R}_{\mathrm{BG}}\right)
    \right]
  }.
\]

The \emph{upper shuffle index} is
\[
  \chi_{\mathrm{up}}(\mathcal R)
  :=
  1/\sup_{x_1\simeq x_1'\in\mathcal X_\perp}
  \ \sup_{x\in\mathcal{X}}
  \sqrt{
    \mathrm{Var}_{Y\sim \mathcal{R}_{x}}
    \!\left[
      \ell_0\!\left(Y; x_1,x_1',\mathcal{R}_{x}\right)
    \right]
  }.
\]
We have the inequality $\chi_{\mathrm{up}}(\mathcal R) \;\ge\; \chi_{\mathrm{lo}}(\mathcal R)$.
\end{definition}

We consider a class $\mathfrak R$ of local randomizers such that every $\mathcal R\in\mathfrak R$ satisfies Assumption~2.8 of~\citet{takagiAnalysisShufflingPure2026} (see Section~\ref{sec:regularity-conditions} for details).
The class $\mathfrak R$ is substantially broader than the class of pure LDP mechanisms. 
In particular, it includes non-LDP mechanisms such as Gaussian-type randomizers. 
Roughly speaking, Assumption~\ref{assump:regularity} imposes mild regularity on the output distributions (e.g., absolute continuity for each input $x$ and the absence of extremely heavy tails), while still covering a wide range of practically relevant mechanisms.
For local randomizers in $\mathfrak R$, the privacy profile of $\mathcal{S}\circ\mathcal{R}^n$ can be characterized (up to asymptotically negligible factors) solely in terms of the shuffle indices.



\begin{lemma}[Privacy profile bounds~\cite{takagiAnalysisShufflingPure2026}]
\label{lem:shuffle-index-profile-seq-no-t}
Let $\mathcal R\in \mathfrak R$, and set
$
\chi_{\mathrm{lo}}:=\chi_{\mathrm{lo}}(\mathcal R)
$ 
and
$\chi_{\mathrm{up}}:=\chi_{\mathrm{up}}(\mathcal R).
$
Assume that as $n\to\infty$,
$
\varepsilon_n=\omega(\sqrt{1/n})
$
and
$
\varepsilon_n=O\!\left(\sqrt{\log n/n}\right).
$
Then, there exist sequences
$e_n^{\mathrm{up}},e_n^{\mathrm{lo}}\to 0$ as $n\to\infty$ such that
\[
  f_{n,\varepsilon_n}(\chi_{\mathrm{up}})\,\bigl(1+e_n^{\mathrm{up}}\bigr)
  \le
  \delta_{\mathcal S\circ \mathcal R^n}(\varepsilon_n)
  \le
  f_{n,\varepsilon_n}(\chi_{\mathrm{lo}})\,\bigl(1+e_n^{\mathrm{lo}}\bigr),
\]
where
\[
  f_{n,\varepsilon}(\chi)
  :=
  \frac{1}{\sqrt{2\pi}\,\chi^{3}\,\varepsilon^{2}\,n^{3/2}}
  \exp\!\Bigl(-\frac{\chi^{2}\varepsilon^{2}n}{2}\Bigr).
\]
Note that $f_{n,\varepsilon_n}(\chi)$ is decreasing in $\chi$.
\end{lemma}


Although the characterization is asymptotic, it shows that $\chi_{\mathrm{lo}}(\mathcal R)$ controls the upper bound and $\chi_{\mathrm{up}}(\mathcal R)$ controls the lower bound. Because $f_{n,\varepsilon}(\chi)$ decreases with $\chi$, larger shuffle indices lead to smaller $\delta$, and thus yielding stronger privacy guarantees after shuffling.



\section{Shuffle-Index-Based Optimization for Mean Estimation}

In this section, we analyze post-shuffling mechanism design for mean estimation through a formulation based on the shuffle index. 
We begin by stating our main result, which establishes a Gaussian-limit correspondence for the optimal privacy-utility trade-off in the high privacy regime. 
To this end, we reduce the shuffled DP constraint to the shuffle index constraints.
Then, we analyze the resulting optimization problem. 
Finally, we show that, from this perspective, PrivUnit can be strictly suboptimal after shuffling when $d>1$.



\subsection{Main Result}
\label{sec:main-result}

We begin by specifying the high-privacy scaling regime in which our results apply.
\begin{definition}[$\sigma$-high privacy regime]
\label{def:chi-high-privacy-regime}
Fix a constant $\sigma> 0$ and a sequence $\{\varepsilon_n\}_{n\ge 1}$ such that
$
\varepsilon_n = O\!\left(\sqrt{\log n/n}\right)
$
and
$
\varepsilon_n = \omega\!\left(1/\sqrt{n}\right).
$
Let $f_{n,\varepsilon}(\sigma)$ be defined as in Lemma~\ref{lem:shuffle-index-profile-seq-no-t}.
We say that a sequence $\{(\varepsilon_n,\delta_n)\}_{n\ge 1}$
is in the \emph{$\sigma$-high privacy regime} if
\[
\delta_n
=
f_{n,\varepsilon_n}(\sigma)\,\bigl(1+e_n\bigr)
\qquad\text{for some sequence } e_n\to 0.
\]
\end{definition}

To build intuition for this high-privacy regime, we first recall the central Gaussian mechanism for mean estimation.
For $\sigma>0$ and $x_{1:n}\in (\mathbb{B}_2^d)^n$, define the central Gaussian mechanism $\mathsf{GM}(\sigma)$ by
\begin{equation}\label{eq:gm-def}
\mathsf{GM}(\sigma)(x_{1:n})
~:=~
\frac{1}{n}\sum_{i=1}^n x_i \;+\; \frac{\sigma}{\sqrt{n}}\,Z,
Z\sim \mathcal N(0,I_d).
\end{equation}
The mean squared error of $\mathsf{GM}$ is
\begin{equation}\label{eq:gm-mse}
\mathbb E\!\left[\left\|\mathsf{GM}(\sigma)(x_{1:n})-\bar x\right\|_2^2\right]
=
\frac{d\,\sigma^2}{n}.
\end{equation}

Under the zero-out neighboring relation, the $\ell_2$-sensitivity of the mean is $1/n$.
We write $\delta_{\mathsf{GM}(\sigma)}(\varepsilon)$ for the privacy profile of the Gaussian mechanism~\cite{balleImprovingGaussianMechanism2018}.
By construction, $\mathsf{GM}(\sigma)$ satisfies $(\varepsilon_n,\delta_n)$-DP in the $\sigma$-high privacy regime.
\begin{restatable}{proposition}{gausshighprivacy}
\label{prop:gausshighprivacy}
Assume that $\varepsilon_n=O\!\left(\sqrt{\log n/n}\right)$ and
$\varepsilon_n=\omega\!\left(1/\sqrt{n}\right)$.
Then, for each $\sigma>0$, the sequence
$
\Bigl\{ \bigl(\varepsilon_n,\ \delta_{\mathsf{GM}(\sigma)}(\varepsilon_n)\bigr) \Bigr\}_{n\ge 1}
$
lies in the $\sigma$-high privacy regime.
\end{restatable}
The proof is given in Appendix~\ref{sec:gausshighprivacy}.
In the scaling regime $\varepsilon_n = O\!\left(\sqrt{\log n/n}\right)$ and $\varepsilon_n=\omega\!\left(1/\sqrt n\right)$, the dominant behavior of the privacy profile is governed by the exponential term $\exp\!\bigl(-\tfrac{\sigma^{2}}{2}\varepsilon_n^{2}n\bigr)$: since $\varepsilon_n^2 n \to \infty$ but $\varepsilon_n^2 n = O(\log n)$, $\delta_{\mathsf{GM}(\sigma)}(\varepsilon_n)$ decays between $\exp(-\omega(1))$ and $n^{-\Theta(1)}$ (and becomes polynomially small precisely when $\varepsilon_n^2 n = \Theta(\log n)$). 
If a mechanism $\mathcal M_n$ is DP with $(\varepsilon_n,\delta_n)$ in the $\sigma$-high privacy regime, then its privacy profile at level $\varepsilon_n$ is asymptotically no larger than that of the central Gaussian mechanism $\mathsf{GM}(\sigma)$; equivalently, $\mathcal M_n$ provides privacy that is (to leading order) at least as strong as $\mathsf{GM}(\sigma)$.



% We will compare the optimal value
% $\mathsf{Err}^{\star}_{\mathrm{DP}}(\varepsilon_n,\delta_n)$ of \eqref{eq:minimax-mse-shuffle-l2-dp} against $\mathsf{GM}$ in the high privacy regime.



\paragraph{Problem Formulation}
Here, we formulate the post-shuffling mechanism design problem directly
under an $(\varepsilon,\delta)$-DP constraint.
% We work in the single-message randomize-then-shuffle model (Definition~\ref{def:single-message-shuffle}) and restrict attention to unbiased protocols.


Let $\mathcal R:\mathbb B_2^d\to\mathcal Y$ be a local randomizer and let
$\mathcal A_n:\mathcal Y^n\to\mathbb R^d$ be an analyzer.
Given a dataset $x_{1:n}\in(\mathbb B_2^d)^n$, each user
produces a single message $Y_i=\mathcal R(x_i)$, the shuffler outputs
$\mathcal S(Y_{1:n})$, and the analyzer returns $\mathcal A_n(\mathcal S(Y_{1:n}))$.
We measure performance by the worst-case squared $\ell_2$ loss
\begin{equation}\label{eq:Riskn-shuffle}
\begin{aligned}
&\mathsf{Err}_n(\mathcal R,\mathcal A_n)
:=\\
&\sup_{x_{1:n}\in(\mathbb B_2^d)^n}\ 
\mathbb E\!\left[
\left\|
\mathcal A_n\!\left(\mathcal S\!\left(\mathcal R^n(x_{1:n})\right)\right)
-
\frac{1}{n}\sum_{i=1}^n x_i
\right\|_2^2
\right].
\end{aligned}
\end{equation}


For $n=1$ (i.e., $\mathsf{Err}_1$), $\mathcal S$ is the identity map, and $\mathcal R^1=\mathcal R$.
Let $\delta_{\mathcal S\circ \mathcal R^n}(\varepsilon)$ denote the privacy
profile of the shuffled mechanism.
We consider the minimax design problem:
\begin{equation}\label{eq:minimax-mse-shuffle-l2-dp}
\begin{aligned} 
&\inf_{\mathcal R\in \mathfrak R}\;
\inf_{\{\mathcal A_n\}_{n\ge 1}}\limsup_{n\to\infty}\;
n\cdot \mathsf{Err}_n(\mathcal R,\mathcal A_n)\ \text{s.t.} \\
& (\mathcal{R}^n, \mathcal{A}_n)\ \text{is unbiased for all sufficiently large } n, \\
& \delta_{\mathcal{S}\circ\mathcal{R}^n}(\varepsilon_n)\ \le\ \delta_n
\quad \text{for all sufficiently large } n,
\end{aligned}
\end{equation}
This problem formalizes \emph{post-shuffling} mechanism design: among all
single-message shuffled protocols that are $(\varepsilon_n,\delta_n)$-DP after
shuffling and unbiased for mean estimation over $\mathbb B_2^d$, find the one
minimizing the worst-case MSE.
Let $\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})$ denote the
optimal value for the problem~\eqref{eq:minimax-mse-shuffle-l2-dp} (i.e., $\limsup_{n\to\infty} n\mathsf{Err}_n(\mathcal R^\star,\mathcal A_n^\star)$).




\paragraph{The Gaussian Limit Correspondence of Shuffling.}
We now state our main result: in the $\sigma$-high privacy regime, the optimal worst-case MSE in the single-message shuffle model matches that of $\mathsf{GM}(\sigma)$ asymptotically.

\begin{restatable}[Gaussian Limit Correspondence]{theorem}{centrallimittheorem}
\label{thm:centrallimittheorem}
Fix a constant $\sigma>0$.
In the $\sigma$-high privacy regime $\{(\varepsilon_n,\delta_n)\}_{n\ge 1}$
\[
d\,\sigma^{2}
\ \le\
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
d\,\sigma^{2}\,\bigl(1+\eta(\sigma)\bigr),
\]
where $\eta(\sigma)\ge 0$ depends only on $\sigma$ and satisfies $\eta(\sigma)=O(\sigma^{-2/3})$ as $\sigma\to\infty$.
\end{restatable}

A proof is provided in Section~\ref{sec:proof-centrallimittheorem}.
In other words, in the $\sigma$-high privacy regime, the optimal single-message shuffle protocol achieves a privacy-utility trade-off that is asymptotically identical to $\mathsf{GM}(\sigma)$ up to vanishing relative error.
Both the lower and upper bounds are proved via a shuffle-index-based analysis developed in Section~\ref{sec:shuffle-index-based-optimization}.

\subsection{Reduction to Shuffle-Index-Based Optimization}
\label{sec:shuffle-index-based-optimization}

Here, our goal is to reduce the $n$-user design problem \eqref{eq:minimax-mse-shuffle-l2-dp} to a single-user design problem with the shuffle indices, and then to solve the resulting problem via matching lower and upper bounds.



\paragraph{Single-user shuffle-index constrained problems.}
We consider the following single-user design problems under shuffle-index constraints.
\begin{equation}\label{eq:minimax-variance-chilo}
\begin{aligned}
\min_{\mathcal R\in\mathfrak R,\ \widehat x}\quad
& \mathsf{Err}_{1}(\mathcal R,\widehat x) \\
\text{s.t.}\quad
& \mathbb E_{Y\sim \mathcal R_x}\!\big[\widehat x(Y)\big] = x,
\qquad \forall\, x\in\mathbb{B}_2^d,\\
& \chi_{\mathrm{lo}}(\mathcal R)\ \ge\ \chi,
\end{aligned}
\end{equation}
and
\begin{equation}\label{eq:minimax-variance-chiup}
\begin{aligned}
\min_{\mathcal R\in\mathfrak R,\ \widehat x}\quad
& \mathsf{Err}_{1}(\mathcal R,\widehat x) \\
\text{s.t.}\quad
& \mathbb E_{Y\sim \mathcal R_x}\!\big[\widehat x(Y)\big] = x,
\qquad \forall\, x\in\mathbb{B}_2^d,\\
& \chi_{\mathrm{up}}(\mathcal R)\ \ge\ \chi.
\end{aligned}
\end{equation}
Let $\mathsf{Err}^{\star}_{\mathrm{lo}}(\chi)$ and
$\mathsf{Err}^{\star}_{\mathrm{up}}(\chi)$ denote the optimal values of
\eqref{eq:minimax-variance-chilo} and \eqref{eq:minimax-variance-chiup},
respectively.


\paragraph{Relating the shuffled-DP design problem.}
We now relate the $n$-user design problem \eqref{eq:minimax-mse-shuffle-l2-dp} to the single-user problems with shuffle indices.
The next lemma shows that, in the $\chi$-high privacy regime, the optimal risk under an $(\varepsilon_n,\delta_n)$ shuffled-DP constraint is sandwiched between the optimal single-user risks under the shuffle index constraint of $\chi$.

\begin{restatable}[Reduction to shuffle-index constraints]{lemma}{reductionShuffleDP}
\label{thm:sandwich-alpha-over-n}
Fix a constant $\chi>0$. Let $\{(\varepsilon_n,\delta_n)\}_{n\ge 1}$ be in the $\chi$-high privacy regime.
Then, given any $\eta>0$
\[
\mathsf{Err}^{\star}_{\mathrm{up}}(\chi)
\ \le\
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
\mathsf{Err}^{\star}_{\mathrm{lo}}(\chi+\eta).
\]
\end{restatable}
We perform two reductions.
First, by the unbiasedness constraint, the $n$-user design problem reduces to a single-user design problem~\cite{asiOptimalAlgorithmsMean2022}.
Second, Lemma~\ref{lem:shuffle-index-profile-seq-no-t} converts the shuffled-DP constraint at $\{(\varepsilon_n,\delta_n)\}_{n\ge 1}$ in $\chi$-high privacy regime into shuffle-index constraints with $\chi$. 
The full proof is provided in Section~\ref{app:proof-reduction-shuffle-dp}.


Consequently, we can sandwich the $n$-user design problem~\eqref{eq:minimax-mse-shuffle-l2-dp} between single-user problems under shuffle-index constraints.
Thus, analyzing the lower and upper bounds of these problems yields corresponding bounds for~\eqref{eq:minimax-mse-shuffle-l2-dp}.





\paragraph{Lower bound.}
The upper shuffle index $\chi_{\mathrm{up}}$ controls a $\chi^2$-type discrepancy of the worst-case neighboring output distributions $\mathcal{R}_{x_1}$ and $\mathcal{R}_{x_1'}$.
Intuitively, larger $\chi_{\mathrm{up}}$ means that $\mathcal{R}_{x_1}$ and $\mathcal{R}_{x_1'}$ are harder to distinguish.
Therefore, we can employ the Hammersley-Chapman-Robbins-type lower bound~\cite{lehmannTheoryPointEstimation1998}: under unbiasedness, small distinguishability forces a universal variance lower bound.
Formally, we have the following result.

\begin{restatable}{theorem}{hcrChiUpLowerBound}
\label{thm:hcr-chiup-lower-bound}
Let $\mathcal R\in\mathfrak R$ be a local randomizer with $\chi_{\mathrm{up}}(\mathcal R)<\infty$ and $\widehat x$ be any unbiased estimator.
Then,
\[
\mathsf{Err}_1(\mathcal R,\widehat x)
\ \ge\
d\,\chi_{\mathrm{up}}(\mathcal R)^2.
\]
\end{restatable}
The proof is found in Appendix~\ref{sec:proof-hcr-chiup-lower-bound}.

\paragraph{Upper bound.}
Next, we show that the lower bound is asymptotically attainable under a
$\chi_{\mathrm{lo}}$ constraint.

\begin{corollary}
\label{cor:chi_lo_upperbound}
As $\chi\to \infty$,
\[
\mathsf{Err}_{\mathrm{lo}}^\star(\chi)
\ \le\
d\,\chi^2 \bigl(1+\frac{3}{2}\chi^{-2/3}+O(\chi^{-4/3})\bigr).
\]
\end{corollary}

Corollary~\ref{cor:chi_lo_upperbound} is proved constructively in
Section~\ref{sec:blanket-mixed-gaussian-mechanism}, where we present an explicit
local randomizer (the \emph{blanket-mixed Gaussian} mechanism) together with a
universal unbiased estimator achieving the stated risk.


\subsection{Suboptimality of Existing Mechanisms in $d>1$}
PrivUnit~\cite{duchiLocalPrivacyStatistical2013,bhowmickProtectionReconstructionIts2019} is optimal in LDP~\cite{asiOptimalAlgorithmsMean2022}, but once we apply shuffling, it no longer achieves the optimal performance when $d>1$.
\begin{restatable}{proposition}{privunitconstantgap}
\label{prop:privunit-constant-gap}
Consider the input domain
$\mathcal X = \mathbb S^{d-1}\subset\mathbb R^d$ for PrivUnit where $d>1$. 
Let $\mathrm{PrivUnit}(p,\theta)$ be the PrivUnit local randomizer, and let $\chi_{\mathrm{lo}}:=\chi_{\mathrm{lo}}(\mathrm{PrivUnit}(p,\theta))$.
For any choice of $\{\theta_d\}_{d\ge2}$,
let $\widehat x_d$ be an unbiased estimator for $\mathrm{PrivUnit}(p,\theta_d)$.
Then, $\chi_{\mathrm{lo}}\to \infty$,
\[
\mathsf{Err}_1\!\left(\mathrm{PrivUnit}(p,\theta_d),\widehat x_d\right)
=
C(\theta_d,d)d \chi_{\mathrm{lo}}^2\Bigl(1+O(\chi_{\mathrm{lo}}^{-1})\Bigr)
\]
for some quantity $C(\theta_d,d)>0$ depending only on $(\theta_d,d)$.
Moreover, the best achievable leading constant is bounded away from~$1$:
\[
\liminf_{d\to\infty}\ \inf_{\theta\in[-1,1]} C(\theta,d)
\ \ge\ \frac{\pi}{2}.
\]
\end{restatable}
We defer the proof to Appendix~\ref{sec:proof-privunit-constant-gap}.
Intuitively, PrivUnit is constrained to a two-level cap-vs-complement reweighting of the uniform measure on $\mathbb S^{d-1}$.
Therefore, once the shuffle-index budget fixes the allowable reweighting magnitude, there is essentially no remaining freedom to maximize the input-direction mean shift that controls the risk, which leads to suboptimality.





\paragraph{Optimality in the case of $d=1$.}
In one dimension, $\mathrm{PrivUnit}$ reduces to randomized response $\mathrm{RR}$, which is the important primitive in shuffling (see, e.g., \citet{ballePrivacyBlanketShuffle2019,asiPrivateVectorMean2024}).
$\mathrm{RR}$ asymptotically attains the lower bound.


\begin{restatable}{proposition}{privunitconstantgapdOne}
\label{prop:privunit-constant-gap-d1}
Consider the input domain $\mathcal X=\mathbb S^{0}\subset\mathbb R$ for $\mathrm{RR}(p)$.
Let $\mathrm{RR}(p)$ be the randomized response local randomizer, and let $\chi_{\mathrm{lo}}$ be its lower shuffle index.
Let $\widehat x_1$ be an unbiased estimator for
$\mathrm{RR}(p)$.
Then, $\chi_{\mathrm{lo}}\to \infty$,
\[
\mathsf{Err}_1\!\left(\mathrm{RR}(p),\widehat x_1\right)
=
\chi_{\mathrm{lo}}^2
\left(1+\chi_{\mathrm{lo}}^{-1}+O(\chi_{\mathrm{lo}}^{-2})\right).
\]
\end{restatable}
See Appendix~\ref{app:privunit-constant-gap-d1} for the proof.

\begin{remark}[Kashin-based reductions]
Kashin-based reductions~\cite{chenBreakingCommunicationPrivacyAccuracyTrilemma2020a,chenPrivacyAmplificationCompression2023, feldmanStatisticalQueryAlgorithms2021} provide a convenient way to turn $d$-dimensional mean
estimation over $\mathbb{B}_2^d$ into a collection of scalar problems by mapping
$x$ to a coefficient vector $z=z(x)\in\mathbb{R}^N$ in a fixed frame so that
$x = Uz$ and $\|z\|_\infty \le \tfrac{K}{\sqrt{N}}\|x\|_2$.
This allows one to plug in a mechanism that is (near-)optimal in the
one-dimensional setting described above at the level of the
induced scalar subproblem.
However, the reduction itself typically incurs a nontrivial distortion constant $K=\Theta(1)$ (and generally $K>1$) in worst case.
Consequently, the overall protocol can suffer a constant-factor loss in worst-case MSE due solely to the $\ell_2 \to \ell_\infty$ coordinate transformation.
\end{remark}



\section{Blanket-Mixed Gaussian Mechanism}
\label{sec:blanket-mixed-gaussian-mechanism}
The shuffle-index formulation implies that existing mechanisms can be suboptimal after shuffling.
Here, we construct an explicit local randomizer that matches the shuffle-index lower bound asymptotically.

\subsection{Mechanism}
Algorithm~\ref{alg:blanket_mixed_gaussian} defines our blanket-mixed Gaussian local randomizer.
Given input $x$, it outputs a blanket sample $Y\sim\mathcal N(0,\sigma_0^2 I_d)$ with probability $\gamma$, and with probability $1-\gamma$ it outputs an informative sample $Y\sim\mathcal N(x,\sigma_0^2 I_d)$.
The role of $\gamma$ is to explicitly embed a blanket into the mechanism; the mechanism is designed for amplification via shuffling.


\paragraph{Unbiased estimator}
Given a single message $Y\in\mathbb R^d$ produced by
Algorithm~\ref{alg:blanket_mixed_gaussian}, we use the linear estimator
\begin{equation}\label{eq:gaussian-blanket-unbiased-estimator}
\widehat x(Y):=\frac{1}{1-\gamma}\,Y .
\end{equation}
This choice is universal.
Indeed, for any $x\in\mathcal X$, Algorithm~\ref{alg:blanket_mixed_gaussian}
outputs $Y\sim \gamma\,\mathcal N(0,\sigma_0^2 I_d)+(1-\gamma)\,\mathcal N(x,\sigma_0^2 I_d)$,
so $\mathbb E[Y]= (1-\gamma)x$ and hence
\[
\mathbb E_{Y\sim \mathcal R_x}\big[\widehat x(Y)\big]
=
\frac{1}{1-\gamma}\,\mathbb E[Y]
=
x.
\]




\begin{algorithm}[tb]
  \caption{Blanket-Mixed Gaussian Mechanism}
  \label{alg:blanket_mixed_gaussian}
  \begin{algorithmic}[1]
    \STATE {\bfseries Input:} $w\in\mathcal X_\perp$, where $\mathcal X:=\{x\in\mathbb R^d:\|x\|_2\le 1\}$ and $\mathcal X_\perp:=\mathcal X\cup\{\perp\}$
    \STATE {\bfseries Parameters:} dimension $d\ge 1$, blanket mass $\gamma\in(0,1]$, Gaussian scale $\sigma_0>0$
    \STATE {\bfseries Output:} a single message $Y\in\mathbb R^d$

    \IF{$w=\perp$}
      \STATE Sample $Y\sim\mathcal N(0,\sigma_0^2 I_d)$
      \STATE \textbf{return} $Y$
    \ENDIF

    \STATE Sample $B\sim\mathrm{Bernoulli}(\gamma)$
    \IF{$B=1$}
      \STATE \hspace{1em} Sample $Y\sim\mathcal N(0,\sigma_0^2 I_d)$
    \ELSE
      \STATE \hspace{1em} Sample $Y\sim\mathcal N(w,\sigma_0^2 I_d)$
    \ENDIF

    \STATE \textbf{return} $Y$
  \end{algorithmic}
\end{algorithm}

\subsection{Analysis and Parameter Optimization}
\label{sec:analysis}

Let $\mathcal R^{\mathsf{BMG}}$ be the Blanket-Mixed Gaussian Mechanism ($\mathsf{BMG}$) in Algorithm~\ref{alg:blanket_mixed_gaussian} with parameters $(\gamma,\sigma_0)$.
Then its lower shuffle index admits the exact expression
\[
\chi_{\mathrm{lo}}\!\left(\mathcal R^{\mathsf{BMG}}\right)^2
=
\frac{\gamma}{(1-\gamma)^2}\cdot \frac{1}{e^{1/\sigma_0^2}-1}.
\]

We can express $\sigma_0$ in terms of $\gamma$ and $\chi_{\mathrm{lo}}$.
Therefore, for a fixed lower shuffle index budget $\chi>0$, substituting $\sigma_0$ into the expression of the risk yields
\[
\mathsf{Err}_1
=
\frac{d}{(1-\gamma)^2\,\log\!\Bigl(1+\frac{\gamma}{(1-\gamma)^2\chi^2}\Bigr)}
+
\frac{\gamma}{1-\gamma}.
\]

Therefore, we can easily optimize $\gamma$ numerically to minimize
$\mathsf{Err}_1$ under the constraint $\chi_{\mathrm{lo}}(\mathcal
R^{\mathsf{BMG}})\ge \chi$. This optimization yields the following result.
\begin{restatable}{theorem}{mixgauss}
\label{thm:gaussian-blanket-mixture-minimax}
Fix $d\ge 1$.
There exists a choice of parameters $(\gamma,\sigma_0)$ such that
$\chi_{\mathrm{lo}}(\mathcal R^{\mathsf{BMG}})\ge \chi$ and, as $\chi\to\infty$,
\[
\mathsf{Err}_1(\mathcal R^{\mathsf{BMG}},\widehat x)
=
d\,\chi^{2}\left(1+\frac{3}{2}\chi^{-2/3}
+O\!\left(\chi^{-4/3}\right)\right).
\]
\end{restatable}

The detailed derivation of $\chi_{\mathrm{lo}}$ and $\mathsf{Err}_1$ and the
proof are deferred to Appendix~\ref{sec:proof-gaussian-blanket-mixture-minimax}.





\subsection{The Gaussian local randomizer ($\gamma=0$ case)}
\label{sec:gamma0}

When $\chi_{\mathrm{up}}>\chi_{\mathrm{lo}}$, this upper bound can be loose, and in fact $\chi_{\mathrm{up}}>\chi_{\mathrm{lo}}$ holds for most local randomizers, including $\mathsf{BMG}$.
While the relative gap can vanish in the high-privacy regime (i.e., $\chi_{\mathrm{up}}/\chi_{\mathrm{lo}}\to 1$ as $\chi_{\mathrm{lo}}\to\infty$), the indices typically remain distinct for finite parameters, so a nonzero absolute gap may persist.

A particularly interesting special case is the Gaussian local randomizer obtained by setting $\gamma=0$ in $\mathsf{BMG}$.
\begin{restatable}{proposition}{gaussianRiskChiUp}
\label{prop:gaussian-risk-chiup}
Consider the Gaussian local randomizer
$
\mathcal R_x^{\mathsf{GL}}=\mathcal N(x,\sigma_0^2 I_d),x\in\mathbb B_2^d,
$
together with the unbiased estimator $\widehat x(Y)=Y$.
Let $\chi_{\mathrm{chua}}
  :=
  1/\sqrt{
    \mathrm{Var}_{Y\sim \mathcal{R}^\mathsf{GL}_{-e}}
    \!\left[
      \ell_0\!\left(Y; e,0,\mathcal{R}^{\mathsf{GL}}_{-e}\right)
    \right]
  }$
  where $e\in\mathbb{S}^{d-1}$.
Then, as $\sigma_0\to\infty$ (equivalently $\chi_{\mathrm{chua}}\to\infty$),
\[
\mathsf{Err}_1(\mathcal R^{\mathsf{GL}},\widehat x)
=
d\,\chi_{\mathrm{chua}}^{2}
\left(
1+\frac{9}{2}\chi_{\mathrm{chua}}^{-2}
+O(\chi_{\mathrm{chua}}^{-4})
\right).
\]
\end{restatable}
See Appendix~\ref{app:gaussian} for the proof.
Proposition~\ref{prop:gaussian-risk-chiup} shows that the Gaussian local randomizer has a particularly sharp utility with respect to $\chi_{\mathrm{chua}}$: the excess over the leading term decays at rate $O(\chi^{-2}_\mathrm{chua})$, which is faster than $\mathsf{BMG}$, whose excess term is $O(\chi_{\mathrm{lo}}^{-2/3})$.

$\chi_{\mathrm{chua}}$ is induced from the conjecture 3.2 of~\citet{chuaHowPrivateAre2024}, which implicates that, for $\mathcal{R}^\mathsf{GL}$, the privacy profile can be upper bounded in terms of $\chi_{\mathrm{chua}}$, namely as $n\to\infty$,
\[
  \delta_{\mathcal{S}\circ\mathcal{R}^{\mathsf{GL} n}}(\varepsilon_n)\ \le\ f_{n,\varepsilon_n}\!\left(\chi_{\mathrm{chua}}\right)(1+o(1)).
\]
This means that we can use $\chi_{\mathrm{chua}}$ instead of $\chi_{\mathrm{lo}}(\mathcal{R}^{\mathsf{GL}})$ to upper bound the privacy guarantee.
Unfortunately, the conjecture is currently open, so we cannot yet turn this observation into an unconditional privacy–utility guarantee.
While our numerical search did not reveal counterexamples, this does not constitute evidence of the conjecture’s validity.
Thus, proving or refuting this conjecture remains a significant and challenging open problem, and would directly sharpen the privacy-utility trade-off.



\section{Numerical Evaluation}



\begin{figure*}[t]
  \centering
  \begin{minipage}[t]{0.32\textwidth}
    \centering
    \includegraphics[width=\linewidth]{gaussian_vs_shuffle_blanket_gaussian_rmse.png}
    \caption{
      Utility comparison at fixed $(n,\delta)=(10^4,10^{-5})$.
    }
    \label{fig:utility}
  \end{minipage}\hfill
  \begin{minipage}[t]{0.32\textwidth}
    \centering
    \includegraphics[width=\linewidth]{gaussian_vs_shuffle_blanket_gaussian_privacy.png}
    \caption{
      Privacy profile (upper bound) comparison at fixed $(n,\mathrm{RMSE})=(10^3,3.16)$.
    }
    \label{fig:privacy}
  \end{minipage}\hfill
  \begin{minipage}[t]{0.32\textwidth}
    \centering
    \includegraphics[width=\linewidth]{gaussian_vs_shuffle_blanket_gaussian_n.png}
    \caption{
      Scaling with $n$ with fixed local randomizer with   $(\gamma, \sigma_0)=(0.95, 4.6)$.
    }
    \label{fig:n-scaling}
  \end{minipage}
\end{figure*}


We provide a numerical illustration of the Gaussian correspondence behavior induced by shuffling (Theorem~\ref{thm:centrallimittheorem}).
We plot the theoretical privacy-utility trade-offs implied by our analysis, and compare the proposed shuffled BMG mechanism ($\mathsf{BMG}$) and the case of $\gamma=0$ against the central Gaussian mechanism ($\mathsf{GM}$) with sensitivity $1/n$.

\paragraph{Setup and parameter tuning.}
We consider $d$-dimensional mean estimation, but since both $\mathsf{GM}$ and $\mathsf{BMG}$ have $\mathrm{Err}_n$ error that scales as $d$, we report the per-coordinate error $\mathrm{RMSE}=\sqrt{\mathrm{Err}_n/d}$.
The $\mathsf{BMG}$ parameters $(\gamma,\sigma_0)$ are chosen using the optimization described in Section~\ref{sec:analysis}.
To evaluate the $(\varepsilon,\delta)$-DP guarantee, we compute certified numerical upper bounds using the FFT-based accountant of~\citet{takagiAnalysisShufflingPure2026} (see Appendix~\ref{app:delta-computation} for details).

\paragraph{Utility curves at fixed $(n,\delta)$ (Figure~\ref{fig:utility}).}
We first fix
$
n=10^4,\delta=10^{-5},
$
and plot the resulting RMSE as a function of $\varepsilon$.
Figure~\ref{fig:utility} shows that in the high privacy regime (i.e., small $\varepsilon$), the RMSE curve of $\mathsf{BMG}$ approaches that of $\mathsf{GM}$.
This numerically supports the prediction that shuffling yields a central-limit effect, leading to a privacy-utility trade-off that is nearly $\mathsf{GM}$ in the high privacy regime.

\paragraph{Privacy profiles at fixed RMSE (Figure~\ref{fig:privacy}).}
Next, we fix $n=10^3$ and the target accuracy level to
$
\mathrm{RMSE}=3.16,
$
and plot the upper bounds of privacy profile $\delta(\varepsilon)$ as a function of $\varepsilon$.
As shown in Figure~\ref{fig:privacy}, the numerically evaluated privacy profile of the
shuffled $\mathsf{BMG}$ closely matches that of $\mathsf{GM}$ in the practical range of $\varepsilon$.

\paragraph{Scaling with the number of users (Figure~\ref{fig:n-scaling}).}
We next examine how the correspondence manifests as we vary the number of users $n$.
We fix the local randomizer to a single instance of $\mathsf{BMG}$ same as that of Figure~\ref{fig:privacy} (i.e., calibrated at $n=10^3$ so that the shuffled protocol attains target accuracy $\mathrm{RMSE}=3.16$
at $\delta=10^{-5}$).
We then sweep
$
n \in \{10^2,10^3,10^4\},
$
and for each $n$ compute the privacy level $\varepsilon_n$ such that $\mathsf{BMG}$ is $(\varepsilon_n,10^{-5})$-DP.
To compare against the $\mathsf{GM}$, we calibrate the noise standard deviation so that it satisfies the same privacy constraint $(\varepsilon_n,10^{-5})$.
The resulting curves show that the RMSE of $\mathsf{BMG}$ closely tracks that of $\mathsf{GM}$.
Notably, the agreement is already strong at $n=10^2$, indicating that the correspondence behavior induced by shuffling becomes practically relevant at small sample sizes.



\section{Discussion}

\paragraph{On the unbiasedness constraint.}
We impose unbiasedness throughout in order to pursue sharp constant-level minimax optimality rather than merely order-optimal rates, in the same spirit as \citet{asiOptimalAlgorithmsMean2022}. 
Under this restriction, we are able to 
(i) reduce post-shuffling mechanism design to an explicit single-user optimization problem governed by the shuffle index and
(ii) prove a universal minimax lower bound that reveals that existing mechanisms can become strictly suboptimal after shuffling.
That said, unbiasedness is a substantive structural constraint, and it remains an open question whether allowing biased estimation can strictly improve the privacy-utility trade-off, potentially yielding protocols whose achievable trade-off is strictly better than the central Gaussian mechanism.


\paragraph{On the high privacy regime and composition}
\label{sec:discussion_high_privacy_gdp}
Gaussian DP (GDP)~\cite{dongGaussianDifferentialPrivacy2022} offers a clean view of multi-round composition for mean estimation with the central Gaussian mechanism. 
Consider running $\mathsf{GM}(\sqrt{T}\sigma)$ independently for $T$ rounds on the same dataset and releasing the average of the $T$ outputs. 
Because GDP is closed under composition and the squared GDP parameter adds across rounds, this averaged $T$-round procedure has the same overall GDP guarantee as a single execution of $\mathsf{GM}(\sigma)$, and it also attains the same mean-squared error. 
Since single-message shuffling has a privacy profile approaching that of the central Gaussian mechanism in the high privacy regime, we expect a similar near-lossless composition behavior for multi-round shuffled protocols: repeating a high privacy single-message shuffled primitive should yield, in the moderate-privacy regime, a privacy-utility trade-off close to the central Gaussian baseline. 
A fully rigorous statement would require tighter composition tools, which we leave for future work.




\section{Conclusion}


In this work, we formulated and analyzed post-shuffling mechanism design as an explicit optimization problem via the shuffle index.
In the $\chi$-high privacy regime, we established a sharp minimax lower bound $d\chi^{2}$ on the worst-case MSE for unbiased protocols, implying that existing mechanisms can become strictly suboptimal after shuffling.
We further constructed $\mathsf{BMG}$ that asymptotically achieves this lower bound, and proved a Gaussian-limit correspondence showing that its privacy profile converges to that of the central Gaussian mechanism
under the matching noise level.
This provides a principled explanation of previously observed Gaussian-like behavior under shuffling~\cite{chenPrivacyAmplificationCompression2023}, sharpening earlier order-level and empirical comparisons by establishing a constant-accurate theoretical correspondence.

Several directions remain open.
An important next step is to improve the convergence rate (i.e., tighten the vanishing excess term) $O(\chi^{-2/3})$.
It is also of interest to extend the shuffle-index-based formulation beyond mean estimation to other fundamental estimation and learning tasks.
Finally, developing tighter composition analyses for multi-round shuffled protocols may extend the constant-level correspondence beyond the high privacy regime.





% In the unusual situation where you want a paper to appear in the
% references without citing it in the main text, use \nocite


\bibliography{shuffle-gauss}
\bibliographystyle{plainnat}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% APPENDIX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\appendix
\onecolumn

\section{Missing Proofs}


\subsection{Proposition~\ref{prop:gausshighprivacy}}
\label{sec:gausshighprivacy}
\gausshighprivacy*


\begin{proof}
  
We begin by relating the privacy profile of the central Gaussian mechanism to
the asymptotic template $f_{n,\varepsilon}(\cdot)$.
\begin{lemma}[Asymptotic Gaussian privacy profile matches $f_{n,\varepsilon}(\cdot)$]
\label{lem:gauss-profile-asymptotic-f}
Fix any sequence $\{\varepsilon_n\}_{n\ge1}$ with $\varepsilon_n=O\!\left(\sqrt{\frac{\log n}{n}}\right)$ and $\varepsilon_n=\omega\!\left(\frac{1}{\sqrt n}\right)$ and $\sigma>0$.
Then, as $n\to\infty$,
\[
\delta_{\mathsf{GM}(\sigma)}(\varepsilon_n)
=
f_{n,\varepsilon_n}(\sigma)\,\bigl(1+o(1)\bigr).
\]
\end{lemma}

\begin{proof}
For the Gaussian mechanism with $\ell_2$-sensitivity $\Delta$
and noise standard deviation $\sigma_{\mathrm{gm}}$, the analytic privacy
profile admits the closed form (see, e.g., \citet{balleImprovingGaussianMechanism2018})
\begin{equation}
\label{eq:analytic-gauss-delta}
\delta_{\mathrm{GM}}(\varepsilon)
=
\Phi\!\left(\frac{\Delta}{2\sigma_{\mathrm{gm}}}-\frac{\varepsilon\sigma_{\mathrm{gm}}}{\Delta}\right)
-
e^{\varepsilon}\,
\Phi\!\left(-\frac{\Delta}{2\sigma_{\mathrm{gm}}}-\frac{\varepsilon\sigma_{\mathrm{gm}}}{\Delta}\right),
\end{equation}
where $\Phi$ is the standard normal CDF.  In our setting,
$\sigma_{\mathrm{gm}}=\sigma/\sqrt{n}$ and $\Delta=1/n$.  Define
\[
a := \varepsilon\sigma\sqrt{n},
\qquad
b := \frac{1}{2\sigma\sqrt{n}}.
\]
Substituting into \eqref{eq:analytic-gauss-delta} and using
$\bar\Phi(t):=1-\Phi(t)$ gives
\begin{equation}
\label{eq:delta-ab}
\delta_{\mathsf{GM}(\sigma)}(\varepsilon)
=
\bar\Phi(a-b)-e^{\varepsilon}\bar\Phi(a+b).
\end{equation}

We now use the Mills ratio expansion: as $t\to\infty$,
\begin{equation}
\label{eq:mills}
\bar\Phi(t)
=
\phi(t)\left(\frac{1}{t}-\frac{1}{t^{3}}+O(t^{-5})\right),
\qquad
\phi(t):=\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}.
\end{equation}
Apply \eqref{eq:mills} with $t=a\pm b$.  Since
\[
\phi(a\pm b)=\phi(a)\exp\!\left(\mp ab-\frac{b^{2}}{2}\right),
\qquad
ab = \varepsilon/2,
\]
we obtain
\begin{align}
\delta_{\mathsf{GM}(\sigma)}(\varepsilon)
&=
\phi(a)e^{\varepsilon/2}e^{-b^{2}/2}
\Biggl[
\left(\frac{1}{a-b}-\frac{1}{(a-b)^3}+O(a^{-5})\right)
-
\left(\frac{1}{a+b}-\frac{1}{(a+b)^3}+O(a^{-5})\right)
\Biggr]. \label{eq:delta-expanded}
\end{align}
Next, expand the bracketed term in $b/a$ (with $b=o(a)$, since $a\to\infty$ and
$b\to0$):
\begin{equation}
\label{eq:diff-expand}
\left(\frac{1}{a-b}-\frac{1}{(a-b)^3}\right)
-
\left(\frac{1}{a+b}-\frac{1}{(a+b)^3}\right)
=
\frac{2b}{a^{2}}+O\!\left(\frac{b}{a^{4}}\right).
\end{equation}
Substituting \eqref{eq:diff-expand} into \eqref{eq:delta-expanded} and using
$e^{-b^{2}/2}=1+o(1)$ yields
\begin{equation}
\label{eq:delta-leading}
\delta_{\mathsf{GM}(\sigma)}(\varepsilon)
=
\phi(a)e^{\varepsilon/2}\left(\frac{2b}{a^{2}}\right)\bigl(1+o(1)\bigr).
\end{equation}
Finally, since $\varepsilon\to0$ we have $e^{\varepsilon/2}=1+o(1)$, and
plugging in $a=\varepsilon\sigma\sqrt{n}$ and $2b=1/(\sigma\sqrt{n})$ gives
\[
\delta_{\mathsf{GM}(\sigma)}(\varepsilon)
=
\frac{1}{\sqrt{2\pi}}
\exp\!\left(-\frac{\varepsilon^{2}\sigma^{2}n}{2}\right)
\cdot
\frac{1}{\sigma^{3}\varepsilon^{2}n^{3/2}}
\bigl(1+o(1)\bigr),
\]
which is exactly $f_{n,\varepsilon}(\sigma)\,(1+o(1))$.
Applying this with $(\varepsilon,\sigma)=(\varepsilon_n,\sigma)$ completes the
proof.
\end{proof}

Let $\{\varepsilon_n\}_{n\ge 1}$ satisfy $\varepsilon_n=O\!\left(\sqrt{\frac{\log n}{n}}\right)$ and $\varepsilon_n=\omega\!\left(\frac{1}{\sqrt n}\right)$ and fix any $\sigma>0$.
By Lemma~\ref{lem:gauss-profile-asymptotic-f}, as $n\to\infty$ we have
\[
\delta_{\mathsf{GM}(\sigma)}(\varepsilon_n)
=
f_{n,\varepsilon_n}(\sigma)\,\bigl(1+o(1)\bigr).
\]
Define $e_n := o(1)$ so that $e_n\to 0$ and
\[
\delta_{\mathsf{GM}(\sigma)}(\varepsilon_n)
=
f_{n,\varepsilon_n}(\sigma)\,\bigl(1+e_n\bigr).
\]
Therefore, by Definition~\ref{def:chi-high-privacy-regime} (with $\chi=\sigma$),
the sequence $\{(\varepsilon_n,\delta_{\mathsf{GM}(\sigma)}(\varepsilon_n))\}_{n\ge 1}$ lies in the $\sigma$-high privacy regime if $\varepsilon_n=O\!\left(\sqrt{\frac{\log n}{n}}\right)$ and $\varepsilon_n=\omega\!\left(\frac{1}{\sqrt n}\right)$.
\end{proof}


\subsection{Theorem~\ref{thm:sandwich-alpha-over-n}}
\label{app:proof-reduction-shuffle-dp}



\reductionShuffleDP*



\begin{proof}


We first outline the structure of the argument. 
The key point is that, under the unbiased mean-estimation constraint, the $n$-user shuffled design problem can be reduced to a \emph{single-user} estimation problem in the same spirit as~\cite{asiOptimalAlgorithmsMean2022}. 
After performing this reduction, the remaining task is to relate the shuffled-DP
constraint to shuffle-index constraints via Lemma~\ref{lem:shuffle-index-profile-seq-no-t}.
This yields two single-user optimization problems, one governed by $\chi_{\mathrm{up}}(\mathcal R)$ and the other by $\chi_{\mathrm{lo}}(\mathcal R)$, which lead respectively to the lower and upper bounds in the statement.

Accordingly, we proceed in two steps. 
We begin with the reduction from the $n$-user optimization to single-user estimation, and then we prove the desired upper and lower bounds separately.


\subsubsection{Reduction to single-user estimation}
We first reformulate the $n$-user design problem by replacing the shuffled-DP constraint with an explicit shuffle-index constraint on the local randomizer $\mathcal R$, which leads to \eqref{eq:minimax-variance-chilo-n} (and analogously \eqref{eq:minimax-variance-chiup-n}).

\begin{equation}\label{eq:minimax-variance-chilo-n}
\begin{aligned}
\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{lo}}(\chi)
:=\;
\inf_{\mathcal R \in \mathfrak R}\;
\inf_{\{\mathcal A_n\}_{n\ge 1}}
\quad
& \limsup_{n\to\infty}\;
n\cdot \mathsf{Err}_n(\mathcal R,\mathcal A_n) \\
\text{s.t.}\quad
& (\mathcal R^n,\mathcal A_n)\ \text{is unbiased for all sufficiently large } n,\\
& \chi_{\mathrm{lo}}(\mathcal R)\ \ge\ \chi,
\end{aligned}
\end{equation}

\begin{equation}\label{eq:minimax-variance-chiup-n}
\begin{aligned}
\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{up}}(\chi)
:=\;
\inf_{\mathcal R \in \mathfrak R}\;
\inf_{\{\mathcal A_n\}_{n\ge 1}}
\quad
& \limsup_{n\to\infty}\;
n\cdot \mathsf{Err}_n(\mathcal R,\mathcal A_n) \\
\text{s.t.}\quad
& (\mathcal R^n,\mathcal A_n)\ \text{is unbiased for all sufficiently large } n,\\
& \chi_{\mathrm{up}}(\mathcal R)\ \ge\ \chi.
\end{aligned}
\end{equation}

Let $\mathsf{Err}_{\mathrm{lo}}^\star(\chi)$ and $\mathsf{Err}_{\mathrm{up}}^\star(\chi)$ denote the optimal values of
\eqref{eq:minimax-variance-chilo} and \eqref{eq:minimax-variance-chiup}, respectively.
Let $\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{lo}}(\chi)$ and $\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{up}}(\chi)$ denote the optimal values of
\eqref{eq:minimax-variance-chilo-n} and \eqref{eq:minimax-variance-chiup-n}, respectively.


We can reduce these $n$-user optimization problems to single-user estimation problems.
\begin{restatable}[Reduction to single-user estimation]{lemma}{reductionMinimax}
\label{lem:reduction-minimax}
Fix $\chi>0$.
Then
\[
\mathsf{Err}_{\mathrm{lo}}^\star(\chi)
=
\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{lo}}(\chi).
\]
\[
\mathsf{Err}_{\mathrm{up}}^\star(\chi)
=
\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{up}}(\chi).
\]
\end{restatable}
The proof is given in Appendix~\ref{sec:proof-reduction-minimax}.




\subsubsection{Upper bound}

Fix any $\eta>0$.
Let $(\mathcal R^\eta,\widehat x^\eta)$ be an (exact or $\zeta$-approximate)
minimizer for the single-user shuffle-index constrained problem
\eqref{eq:minimax-variance-chilo} at level $\chi+\eta$, i.e.,
\begin{align*}
\mathbb E_{Y\sim \mathcal R^\eta_x}\!\big[\widehat x^\eta(Y)\big] &= x
\quad\text{for all }x\in\mathbb B_2^d,\\
\chi_{\mathrm{lo}}(\mathcal R^\eta)&\ge \chi+\eta,\\
\mathsf{Err}_1(\mathcal R^\eta,\widehat x^\eta)
&\le \mathsf{Err}^{\star}_{\mathrm{lo}}(\chi+\eta)+\zeta,
\end{align*}
where $\zeta>0$ is arbitrary.

\paragraph{Step 1: Privacy feasibility under $(\varepsilon_n,\delta_n)$.}
Apply Lemma~\ref{lem:shuffle-index-profile-seq-no-t} (upper bound direction)
to $\mathcal R^\eta$. Since $\varepsilon_n\to 0$,
$\varepsilon_n=\omega(\sqrt{1/n})$, and
$\varepsilon_n=O(\sqrt{\log n/n})$, there exists a sequence
$e_{n}^{\mathrm{lo}}(\eta)\to 0$ such that for all sufficiently large $n$,
\begin{equation}\label{eq:delta-upper-Reta}
\delta_{\mathcal S\circ (\mathcal R^\eta)^n}(\varepsilon_n)
\ \le\
f_{n,\varepsilon_n}\!\bigl(\chi_{\mathrm{lo}}(\mathcal R^\eta)\bigr)\,
\bigl(1+e_{n}^{\mathrm{lo}}(\eta)\bigr).
\end{equation}
Using $\chi_{\mathrm{lo}}(\mathcal R^\eta)\ge \chi+\eta$ and that
$f_{n,\varepsilon}(\cdot)$ is decreasing, we obtain
\begin{equation}\label{eq:delta-upper-chi-plus-eta}
\delta_{\mathcal S\circ (\mathcal R^\eta)^n}(\varepsilon_n)
\ \le\
f_{n,\varepsilon_n}(\chi+\eta)\,\bigl(1+e_{n}^{\mathrm{lo}}(\eta)\bigr).
\end{equation}

Next, compare $f_{n,\varepsilon_n}(\chi+\eta)$ and $f_{n,\varepsilon_n}(\chi)$:
\begin{equation}\label{eq:ratio-f}
\frac{f_{n,\varepsilon_n}(\chi+\eta)}{f_{n,\varepsilon_n}(\chi)}
=
\left(\frac{\chi}{\chi+\eta}\right)^3
\exp\!\left(
-\frac{(\chi+\eta)^2-\chi^2}{2}\,\varepsilon_n^2\,n
\right).
\end{equation}
Since $\eta>0$ is fixed and $\varepsilon_n^2 n\to\infty$ (because
$\varepsilon_n=\omega(\sqrt{1/n})$), the right-hand side of
\eqref{eq:ratio-f} tends to $0$.

From the definition \ref{def:chi-high-privacy-regime}, we have
$\delta_n = f_{n,\varepsilon_n}(\chi)(1+e_n)$ with $e_n\to 0$.
Therefore, combining \eqref{eq:delta-upper-chi-plus-eta} and \eqref{eq:ratio-f},
we conclude that for all sufficiently large $n$,
\begin{equation}\label{eq:dp-feasible-Reta-final}
\delta_{\mathcal S\circ (\mathcal R^\eta)^n}(\varepsilon_n)
\ \le\
\delta_n .
\end{equation}
Hence the shuffled mechanism induced by $\mathcal R^\eta$ is
$(\varepsilon_n,\delta_n)$-DP for all sufficiently large $n$.

\paragraph{Step 2: Risk bound.}
Define an $n$-user analyzer $\mathcal A^\eta:\mathcal Y^n\to\mathbb R^d$ by
\[
\mathcal A^\eta(y_{1:n}) := \frac{1}{n}\sum_{i=1}^n \widehat x^\eta(y_i),
\]
which is permutation-invariant and hence compatible with shuffling.
Since $(\mathcal R^\eta,\widehat x^\eta)$ is unbiased at the single-user level,
$( (\mathcal R^\eta)^n, \mathcal A^\eta)$ is unbiased for the mean.
Moreover, by Lemma~\ref{lem:reduction-minimax},
\[
\mathsf{Err}_n(\mathcal R^\eta,\mathcal A^\eta)
=
\frac{1}{n}\,\mathsf{Err}_1(\mathcal R^\eta,\widehat x^\eta).
\]
Combining this with \eqref{eq:dp-feasible-Reta-final}, we see that
$(\mathcal R^\eta,\mathcal A^\eta)$ is feasible for
\eqref{eq:minimax-mse-shuffle-l2-dp} (for all sufficiently large $n$), and thus
\[
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
\limsup_{n\to\infty} n\mathsf{Err}_n(\mathcal R^\eta,\mathcal A^\eta)
=
\mathsf{Err}_1(\mathcal R^\eta,\widehat x^\eta)
\ \le\
\mathsf{Err}^{\star}_{\mathrm{lo}}(\chi+\eta)+\zeta.
\]
Finally, letting $\zeta\downarrow 0$ proves the claim.



\subsubsection{Lower bound}

Assume throughout that $(\varepsilon_n,\delta_n)$ is in the $\chi$-high privacy
regime (Definition~\ref{def:chi-high-privacy-regime}).

We prove the lower bound
\[
\mathsf{Err}^{\star}_{\mathrm{up}}(\chi)
\ \le\
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1}).
\]

\paragraph{Step 1: Any shuffled-DP feasible $\mathcal R$ must satisfy
$\chi_{\mathrm{up}}(\mathcal R)\ge \chi$.}
Fix any local randomizer $\mathcal R\in\mathfrak R$ and any analyzer
$\mathcal A$ such that $(\mathcal R^n,\mathcal A)$ is unbiased and the shuffled
mechanism is $(\varepsilon_n,\delta_n)$-DP, i.e.,
\begin{equation}\label{eq:dp-feasible}
\delta_{\mathcal S\circ \mathcal R^n}(\varepsilon_n)\ \le\ \delta_n .
\end{equation}
We claim that necessarily $\chi_{\mathrm{up}}(\mathcal R)\ge \chi$ for all
sufficiently large $n$.

Suppose for contradiction that $\chi_{\mathrm{up}}(\mathcal R)<\chi$.
Since $\varepsilon_n\to 0$, $\varepsilon_n=\omega(\sqrt{1/n})$,
and $\varepsilon_n=O(\sqrt{\log n/n})$ by the definition of the high privacy
regime, we may apply Lemma~\ref{lem:shuffle-index-profile-seq-no-t}
to obtain a sequence $e_n^{\mathrm{up}}\to 0$ such that, for all sufficiently
large $n$,
\begin{equation}\label{eq:profile-lb}
\delta_{\mathcal S\circ \mathcal R^n}(\varepsilon_n)
\ \ge\
f_{n,\varepsilon_n}\!\bigl(\chi_{\mathrm{up}}(\mathcal R)\bigr)\,
\bigl(1+e_n^{\mathrm{up}}\bigr),
\end{equation}
where $f_{n,\varepsilon}(\chi)$ is defined in
Lemma~\ref{lem:shuffle-index-profile-seq-no-t}.

On the other hand, since $(\varepsilon_n,\delta_n)$ is in the $\chi$-high
privacy regime, there exists a sequence $e_n\to 0$ such that, for all
sufficiently large $n$,
\begin{equation}\label{eq:regime-ub}
\delta_n \ = f_{n,\varepsilon_n}(\chi)\,(1+e_n).
\end{equation}
Combining \eqref{eq:dp-feasible}, \eqref{eq:profile-lb}, and
\eqref{eq:regime-ub} yields, for all sufficiently large $n$,
\begin{equation}\label{eq:key-ineq}
f_{n,\varepsilon_n}\!\bigl(\chi_{\mathrm{up}}(\mathcal R)\bigr)\,
\bigl(1+e_n^{\mathrm{up}}\bigr)
\ \le\
f_{n,\varepsilon_n}(\chi)\,(1+e_n).
\end{equation}

Now consider the ratio
\[
\frac{f_{n,\varepsilon_n}(\chi_{\mathrm{up}}(\mathcal R))}{f_{n,\varepsilon_n}(\chi)}
=
\left(\frac{\chi}{\chi_{\mathrm{up}}(\mathcal R)}\right)^3
\exp\!\left(
\frac{\chi^2-\chi_{\mathrm{up}}(\mathcal R)^2}{2}\,\varepsilon_n^2\,n
\right).
\]
Since $\chi_{\mathrm{up}}(\mathcal R)<\chi$, we have
$\chi^2-\chi_{\mathrm{up}}(\mathcal R)^2>0$, and since
$\varepsilon_n=\omega(\sqrt{1/n})$ we have $\varepsilon_n^2 n\to\infty$.
Therefore,
\[
\frac{f_{n,\varepsilon_n}(\chi_{\mathrm{up}}(\mathcal R))}{f_{n,\varepsilon_n}(\chi)}
\ \longrightarrow\ \infty.
\]
Moreover, $(1+e_n^{\mathrm{up}})/(1+e_n)\to 1$. Hence, for all sufficiently
large $n$,
\[
f_{n,\varepsilon_n}\!\bigl(\chi_{\mathrm{up}}(\mathcal R)\bigr)\,
\bigl(1+e_n^{\mathrm{up}}\bigr)
\ >\
f_{n,\varepsilon_n}(\chi)\,(1+e_n),
\]
which contradicts \eqref{eq:key-ineq}. This proves the claim:
\begin{equation}\label{eq:chiup-ge-chi}
\chi_{\mathrm{up}}(\mathcal R)\ \ge\ \chi
\end{equation}

\paragraph{Step 2: Reduction to the $\chi_{\mathrm{up}}$-constrained minimax risk.}
By \eqref{eq:chiup-ge-chi}, every protocol feasible for
\eqref{eq:minimax-mse-shuffle-l2-dp} (i.e., unbiased and shuffled-DP at level
$(\varepsilon_n,\delta_n)$) is also feasible for the shuffled-index constrained
problem defining $\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{up}}(\chi)$ (namely, the same
unbiasedness constraint together with $\chi_{\mathrm{up}}(\mathcal R)\ge\chi$).
Therefore the feasible set of \eqref{eq:minimax-mse-shuffle-l2-dp} is contained
in the feasible set of the $\chi_{\mathrm{up}}$-constrained problem, and
consequently the optimal value satisfies
\begin{equation}\label{eq:dp-ge-up}
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \ge\
\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{up}}(\chi).
\end{equation}

Finally, by Lemma~\ref{lem:reduction-minimax} we have
$\mathsf{Err}^{\star,\mathrm{uni}}_{\mathrm{up}}(\chi)=\mathsf{Err}^{\star}_{\mathrm{up}}(\chi)$.
Substituting into \eqref{eq:dp-ge-up} yields
\[
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \ge\
\mathsf{Err}^{\star}_{\mathrm{up}}(\chi),
\]
as desired.







\end{proof}

\subsubsection{Lemma~\ref{lem:reduction-minimax}}
\label{sec:proof-reduction-minimax}

\reductionMinimax*



\begin{proof}
The reduction is in the same spirit as the canonicalization results of
Asi et al.~\cite{asiOptimalAlgorithmsMean2022} for unbiased local protocols.
We first establish two auxiliary results: Lemma~\ref{lem:data-processing-shuffle-index} and Lemma~\ref{lem:additivization-kernel}, and then use them to prove
Lemma~\ref{lem:reduction-minimax}.


\begin{lemma}[Post-processing for shuffle indices]
\label{lem:data-processing-shuffle-index}
Let $\mathcal R\in \mathfrak R$ be a local randomizer that admits
a blanket distribution $\mathcal R_{\mathrm{BG}}$ with blanket mass
$\gamma\in(0,1]$, i.e.,
for every $x\in\mathcal X_\perp$ and a.e.\ $y\in\mathcal Y$,
\[
  \mathcal R_x(y)
  =
  \gamma\,\mathcal R_{\mathrm{BG}}(y)
  +
  (1-\gamma)\,Q_x(y)
\]
for some family of densities $\{Q_x\}_{x\in\mathcal X_\perp}$.
Let $\mathcal K:\mathcal Y\to\mathcal Z$ be an arbitrary (possibly randomized)
post-processing map, i.e., a Markov kernel from $\mathcal Y$ to $\mathcal Z$.
Define the post-processed randomizer
\[
  \mathcal R' := \mathcal K \circ \mathcal R : \mathcal X_\perp\to\mathcal Z,
\qquad
  \mathcal R'_x := \mathcal K \circ \mathcal R_x.
\]
Then $\mathcal R'$ admits a blanket distribution
$\mathcal R'_{\mathrm{BG}}:=\mathcal K\circ \mathcal R_{\mathrm{BG}}$
with blanket mass at least $\gamma$, and moreover its shuffle indices satisfy
\[
  \chi_{\mathrm{up}}(\mathcal R') \ge \chi_{\mathrm{up}}(\mathcal R),
  \qquad
  \chi_{\mathrm{lo}}(\mathcal R') \ge \chi_{\mathrm{lo}}(\mathcal R).
\]
\end{lemma}

\begin{proof}



We first show that $\mathcal R'$ admits a blanket of mass $\gamma$.
Applying $\mathcal K$ to the blanket decomposition of $\mathcal R_x$ yields
\[
  \mathcal R'_x
  =
  \mathcal K\circ \mathcal R_x
  =
  \gamma\,(\mathcal K\circ \mathcal R_{\mathrm{BG}})
  +
  (1-\gamma)\,(\mathcal K\circ Q_x).
\]
Thus, $\mathcal R'_{\mathrm{BG}}:=\mathcal K\circ \mathcal R_{\mathrm{BG}}$
is a valid blanket distribution of $\mathcal R'$ with blanket mass $\gamma$
(and hence the maximal blanket mass $\gamma'$ of $\mathcal R'$ satisfies
$\gamma'\ge \gamma$).

We next prove the monotonicity of the lower shuffle index.
Fix $x\simeq x'$ and consider the generalized privacy amplification random variable
with reference $\mathcal R_{\mathrm{BG}}$:
\[
  \ell_0(Y;x,x',\mathcal R_{\mathrm{BG}})
  :=
  \frac{\mathcal R_x(Y)-\mathcal R_{x'}(Y)}{\mathcal R_{\mathrm{BG}}(Y)},
  \qquad Y\sim \mathcal R_{\mathrm{BG}}.
\]
Let $Z\sim \mathcal R'_{\mathrm{BG}}$ be obtained by sampling
$Y\sim \mathcal R_{\mathrm{BG}}$ and then applying $Z\mid Y\sim \mathcal K(\cdot\mid Y)$.
Define analogously
\[
  \ell_0'(Z;x,x',\mathcal R'_{\mathrm{BG}})
  :=
  \frac{\mathcal R'_x(Z)-\mathcal R'_{x'}(Z)}{\mathcal R'_{\mathrm{BG}}(Z)}.
\]
Then, for $\mathcal R_{\mathrm{BG}}$-a.e.\ $y$ and $\mathcal R'_{\mathrm{BG}}$-a.e.\ $z$,
\[
  \ell_0'(z;x,x',\mathcal R'_{\mathrm{BG}})
  =
  \mathbb E\!\left[\ell_0(Y;x,x',\mathcal R_{\mathrm{BG}})\,\middle|\, Z=z \right].
\]
Indeed, writing $\mathcal K(z\mid y)$ for the kernel density,
we have
\[
  \mathcal R'_x(z)-\mathcal R'_{x'}(z)
  =
  \int \mathcal K(z\mid y)\bigl(\mathcal R_x(y)-\mathcal R_{x'}(y)\bigr)\,dy,
  \qquad
  \mathcal R'_{\mathrm{BG}}(z)
  =
  \int \mathcal K(z\mid y)\mathcal R_{\mathrm{BG}}(y)\,dy,
\]
and the claim follows by Bayes' rule.

Therefore, by the law of total variance,
\[
  \mathrm{Var}\!\left(\ell_0'(Z;x,x',\mathcal R'_{\mathrm{BG}})\right)
  =
  \mathrm{Var}\!\left(\mathbb E\!\left[\ell_0(Y;x,x',\mathcal R_{\mathrm{BG}})\mid Z\right]\right)
  \le
  \mathrm{Var}\!\left(\ell_0(Y;x,x',\mathcal R_{\mathrm{BG}})\right).
\]
Combining this with $\gamma'\ge \gamma$ yields
\[
  \frac{1}{\gamma'}\,
  \mathrm{Var}\!\left(\ell_0'(Z;x,x',\mathcal R'_{\mathrm{BG}})\right)
  \le
  \frac{1}{\gamma}\,
  \mathrm{Var}\!\left(\ell_0(Y;x,x',\mathcal R_{\mathrm{BG}})\right).
\]
Taking the supremum over $x\simeq x'$ and the square root gives
$\chi_{\mathrm{lo}}(\mathcal R')\ge \chi_{\mathrm{lo}}(\mathcal R)$.

The proof for the upper shuffle index is analogous.
For any fixed $x\in\mathcal X$, let $Y\sim \mathcal R_x$ and obtain
$Z$ by applying the same post-processing kernel $\mathcal K$.
Then, defining
\[
  \ell_{0,x}(Y;x_1,x_1')
  :=
  \frac{\mathcal R_{x_1}(Y)-\mathcal R_{x_1'}(Y)}{\mathcal R_x(Y)},
  \qquad
  \ell_{0,x}'(Z;x_1,x_1')
  :=
  \frac{\mathcal R'_{x_1}(Z)-\mathcal R'_{x_1'}(Z)}{\mathcal R'_x(Z)},
\]
one similarly has
\[
  \ell_{0,x}'(Z;x_1,x_1')
  =
  \mathbb E\!\left[\ell_{0,x}(Y;x_1,x_1') \,\middle|\, Z\right],
\]
and hence
\[
  \mathrm{Var}\!\left(\ell_{0,x}'(Z;x_1,x_1')\right)
  \le
  \mathrm{Var}\!\left(\ell_{0,x}(Y;x_1,x_1')\right).
\]
Taking the supremum over $x_1\simeq x_1'$ and $x\in\mathcal X$,
and then the square root, concludes that
$\chi_{\mathrm{up}}(\mathcal R')\ge \chi_{\mathrm{up}}(\mathcal R)$.
\end{proof}



\begin{lemma}[Additivization via a Markov kernel]
\label{lem:additivization-kernel}
Fix $n\ge 2$.
Let $\mathcal R$ be any local randomizer and let
$\mathcal A$ be any unbiased estimator in the
single-message shuffle model.
Then there exists a Markov kernel $K:\mathcal Y\to \mathbb R^d$ such that, letting
$
\mathcal A^+(z_{1:n})
:=
\frac{1}{n}\sum_{i=1}^n z_i,
$
the estimator $\mathcal A^+$ is unbiased with respect to the local randomizer
$K\circ \mathcal R:\mathcal X\to\mathbb R^d$, and moreover,
\[
\mathsf{Err}_n(K\circ \mathcal R,\mathcal A^+)
\ \le\
\mathsf{Err}_n(\mathcal R,\mathcal A).
\]
\end{lemma}

\begin{proof}
Define the composed analyzer $\widetilde{\mathcal A}:=\mathcal A\circ\mathcal S$.
Since shuffling is a post-processing operation, the single-message shuffled
protocol $(\mathcal R,\mathcal A)$ can be equivalently viewed as the (non-shuffled)
local protocol $(\mathcal R,\widetilde{\mathcal A})$ with the same output
distribution.
In particular, unbiasedness is preserved:
for all datasets $x_{1:n}\in\mathcal X^n$,
\[
\mathbb E\!\left[\widetilde{\mathcal A}\!\left(\mathcal R^n(x_{1:n})\right)\right]
=
\mathbb E\!\left[\mathcal A\!\left(\mathcal S\!\left(\mathcal R^n(x_{1:n})\right)\right)\right]
=
\frac{1}{n}\sum_{i=1}^n x_i.
\]
Therefore, we may invoke a canonicalization (additivization) argument in the spirit of
Proposition~3.3 of~\citet{asiOptimalAlgorithmsMean2022}.
Concretely, for any unbiased analyzer $\widetilde{\mathcal A}$, there exists a Markov kernel
$K:\mathcal Y\to\mathbb R^d$ such that, letting $\mathcal R':=K\circ\mathcal R$ and
$\mathcal A^+(z_{1:n}):=\frac{1}{n}\sum_{i=1}^n z_i$, the estimator $\mathcal A^+$ is unbiased
with respect to $\mathcal R'$ and satisfies
\[
\mathsf{Err}_n(\mathcal R',\mathcal A^+)\ \le\ \mathsf{Err}_n(\mathcal R,\widetilde{\mathcal A}).
\]
Unlike~\cite{asiOptimalAlgorithmsMean2022}, we do not require $\mathcal R$ to satisfy
$\varepsilon$-LDP; the canonicalization construction we use relies only on unbiasedness.
The only closure property needed under post-processing concerns the shuffle-index constraints,
which is guaranteed by Lemma~\ref{lem:data-processing-shuffle-index}.
\end{proof}


\paragraph{Proof of Lemma~\ref{lem:reduction-minimax}}


We prove the claim for the $\chi_{\mathrm{lo}}$-constrained problem; the proof
for $\chi_{\mathrm{up}}$ is identical by using the corresponding monotonicity in
Lemma~\ref{lem:data-processing-shuffle-index}.

Recall that $\mathsf{Err}_{n,\mathrm{lo}}^\star(\chi)$ is the optimal value of
\eqref{eq:minimax-variance-chilo-n} and $\mathsf{Err}_{\mathrm{lo}}^\star(\chi)$
is the optimal value of \eqref{eq:minimax-variance-chilo}.

\paragraph{Step 1: $\le$ direction.}
Let $(\mathcal R,\widehat x)$ be any feasible solution to the single-user
problem \eqref{eq:minimax-variance-chilo}, i.e.,
$\mathbb E_{Y\sim \mathcal R_x}[\widehat x(Y)]=x$ for all $x\in\mathbb B_2^d$ and
$\chi_{\mathrm{lo}}(\mathcal R)\ge \chi$.
Define an $n$-user protocol by applying $\mathcal R$ independently to each user
and using the additive estimator
\[
  \mathcal A(y_{1:n})
  :=
  \frac{1}{n}\sum_{i=1}^n \widehat x(y_i),
  \qquad y_{1:n}\in\mathcal Y^n,
\]
(which is permutation-invariant and hence unaffected by shuffling).
Then the resulting estimator is unbiased:
\[
  \mathbb E\!\left[\mathcal A(\mathcal S(\mathcal R^n(x_{1:n})))\right]
  =
  \frac{1}{n}\sum_{i=1}^n \mathbb E[\widehat x(Y_i)]
  =
  \frac{1}{n}\sum_{i=1}^n x_i.
\]
Moreover, writing $Y_i\sim \mathcal R_{x_i}$ independently and setting
$\Delta_i:=\widehat x(Y_i)-x_i$, we have $\mathbb E[\Delta_i]=0$ and hence
\[
  \mathbb E\Bigl\|
    \mathcal A(Y_{1:n})-\frac{1}{n}\sum_{i=1}^n x_i
  \Bigr\|_2^2
  =
  \mathbb E\Bigl\|
    \frac{1}{n}\sum_{i=1}^n \Delta_i
  \Bigr\|_2^2
  =
  \frac{1}{n^2}\sum_{i=1}^n \mathbb E\|\Delta_i\|_2^2,
\]
where the cross terms vanish by independence and mean-zero.
Taking the supremum over $x_{1:n}\in(\mathbb B_2^d)^n$ yields
\[
  \mathsf{Err}_n(\mathcal R,\mathcal A)
  =
  \frac{1}{n}\sup_{x\in\mathbb B_2^d}\mathbb E_{Y\sim \mathcal R_x}
  \bigl[\|\widehat x(Y)-x\|_2^2\bigr]
  =
  \frac{1}{n}\mathsf{Err}_1(\mathcal R,\widehat x).
\]
Since $(\mathcal R,\mathcal A)$ is feasible for \eqref{eq:minimax-variance-chilo-n},
we obtain
\[
  \mathsf{Err}_{n,\mathrm{lo}}^\star(\chi)
  \le
  \mathsf{Err}_{\mathrm{lo}}^\star(\chi).
\]

\paragraph{Step 2: $\ge$ direction.}
Let $(\mathcal R,\mathcal A)$ be any feasible $n$-user solution to
\eqref{eq:minimax-variance-chilo-n}, i.e., $\mathcal A$ is unbiased for
$\mathcal S\circ\mathcal R^n$ and $\chi_{\mathrm{lo}}(\mathcal R)\ge \chi$.
Define the non-shuffled analyzer $\widetilde{\mathcal A}:=\mathcal A\circ\mathcal S$.
Since shuffling is post-processing, the pair $(\mathcal R,\widetilde{\mathcal A})$
induces the same output distribution and remains unbiased:
\[
  \mathbb E\!\left[\widetilde{\mathcal A}(\mathcal R^n(x_{1:n}))\right]
  =
  \mathbb E\!\left[\mathcal A(\mathcal S(\mathcal R^n(x_{1:n})))\right]
  =
  \frac{1}{n}\sum_{i=1}^n x_i.
\]
Applying Lemma~\ref{lem:additivization-kernel} to $(\mathcal R,\widetilde{\mathcal A})$, we obtain a Markov kernel
$K:\mathcal Y\to\mathbb R^d$ such that, letting $\mathcal R':=K\circ\mathcal R$
and $\mathcal A^+(z_{1:n}):=\frac{1}{n}\sum_{i=1}^n z_i$, the estimator
$\mathcal A^+$ is unbiased with respect to $\mathcal R'$ and
\begin{equation}\label{eq:canon-risk}
  \mathsf{Err}_n(\mathcal R',\mathcal A^+)
  \le
  \mathsf{Err}_n(\mathcal R,\mathcal A).
\end{equation}
By Lemma~\ref{lem:data-processing-shuffle-index},
\[
  \chi_{\mathrm{lo}}(\mathcal R')
  =
  \chi_{\mathrm{lo}}(K\circ\mathcal R)
  \ge
  \chi_{\mathrm{lo}}(\mathcal R)
  \ge
  \chi,
\]
so $(\mathcal R',\mathcal A^+)$ is feasible for \eqref{eq:minimax-variance-chilo-n}.

Now let $Z_i\sim \mathcal R'_{x_i}$ be independent and define $\Xi_i:=Z_i-x_i$.
Unbiasedness implies $\mathbb E[\Xi_i]=0$, and thus
\[
  \mathbb E\Bigl\|
    \mathcal A^+(Z_{1:n})-\frac{1}{n}\sum_{i=1}^n x_i
  \Bigr\|_2^2
  =
  \mathbb E\Bigl\|
    \frac{1}{n}\sum_{i=1}^n \Xi_i
  \Bigr\|_2^2
  =
  \frac{1}{n^2}\sum_{i=1}^n \mathbb E\|\Xi_i\|_2^2,
\]
and hence
\[
  \mathsf{Err}_n(\mathcal R',\mathcal A^+)
  =
  \frac{1}{n}\sup_{x\in\mathbb B_2^d}
  \mathbb E_{Z\sim \mathcal R'_x}\bigl[\|Z-x\|_2^2\bigr]
  =
  \frac{1}{n}\,\mathsf{Err}_1(\mathcal R',\mathrm{id}),
\]
where $\mathrm{id}:\mathbb R^d\to\mathbb R^d$ denotes the identity estimator.
Since $\mathrm{id}$ is an admissible unbiased estimator for $\mathcal R'$,
the single-user optimum satisfies
\[
  \mathsf{Err}_{\mathrm{lo}}^\star(\chi)
  \le
  \mathsf{Err}_1(\mathcal R',\mathrm{id}).
\]
Combining the last two displays with \eqref{eq:canon-risk} gives
\[
  \mathsf{Err}_n(\mathcal R,\mathcal A)
  \ge
  \mathsf{Err}_n(\mathcal R',\mathcal A^+)
  =
  \frac{1}{n}\,\mathsf{Err}_1(\mathcal R',\mathrm{id})
  \ge
  \frac{1}{n}\,\mathsf{Err}_{\mathrm{lo}}^\star(\chi).
\]
Taking the infimum over all feasible $(\mathcal R,\mathcal A)$ for
\eqref{eq:minimax-variance-chilo-n} yields
\[
  \mathsf{Err}_{n,\mathrm{lo}}^\star(\chi)
  \ge
  \mathsf{Err}_{\mathrm{lo}}^\star(\chi).
\]

\paragraph{Conclusion.}
Combining the $\le$ and $\ge$ directions proves
\[
  \mathsf{Err}_{n,\mathrm{lo}}^\star(\chi)
  =
  \mathsf{Err}_{\mathrm{lo}}^\star(\chi).
\]
The statement for $\mathsf{Err}_{n,\mathrm{up}}^\star(\chi)$ follows by the same
argument, replacing $\chi_{\mathrm{lo}}$ by $\chi_{\mathrm{up}}$ throughout.

\end{proof}


\subsection{Theorem~\ref{thm:hcr-chiup-lower-bound}}

\label{sec:proof-hcr-chiup-lower-bound}

\hcrChiUpLowerBound*


\begin{proof}
Let $\mathcal R:\mathcal X_\perp\to\mathcal Y$ be a local randomizer, and let
$\widehat x:\mathcal Y\to\mathbb R^d$ be an unbiased estimator in the sense that
\[
\mathbb E_{Y\sim \mathcal R_x}\big[\widehat x(Y)\big]=x
\qquad\text{for all }x\in\mathcal X_\perp,
\]
where we interpret $\perp$ as contributing $0$ to the mean and thus require $\mathbb E_{Y\sim \mathcal R_\perp}[\widehat x(Y)]=0$.

Fix an arbitrary reference point $x\in\mathcal X$.
By mutual absolute continuity due to $\mathcal R\in \mathfrak R$, for every $x'\in\mathcal X_\perp$ the
Radon--Nikodym derivative
\[
w_{x';x}(y):=\frac{d\mathcal R_{x'}}{d\mathcal R_x}(y)
\]
is well-defined $\mathcal R_x$-a.s.
For $x_1, x_1'\in\mathcal{X}_\perp$, define
\[
\ell_{x_1,x_1';x}(y):=w_{x_1;x}(y)-w_{x_1';x}(y).
\]
Then $\mathbb E_{Y\sim \mathcal R_x}[\ell_{x_1,x_1';x}(Y)]=0$.
Moreover, by a change of measure and unbiasedness, for any $x'\in\mathcal X_\perp$,
\[
\mathbb E_{Y\sim\mathcal R_{x'}}[\widehat x(Y)]
=
\mathbb E_{Y\sim\mathcal R_x}\!\big[\widehat x(Y)\,w_{x';x}(Y)\big]
=
x'.
\]
Subtracting the identities for $x'$ equal to $x_1$ and $x_1'$ yields
\begin{equation}\label{eq:unbiased-diff-x}
\mathbb E_{Y\sim\mathcal R_x}\!\big[\widehat x(Y)\,\ell_{x_1,x_1';x}(Y)\big]
=
x_1-x_1'.
\end{equation}

Let $\varphi\in(\mathbb R^d)^\ast$ be any linear functional.
Applying $\varphi$ to \eqref{eq:unbiased-diff-x} gives
\[
\mathbb E_{Y\sim\mathcal R_x}\!\Big[\varphi(\widehat x(Y))\,\ell_{x_1,x_1';x}(Y)\Big]
=
\varphi(x_1-x_1').
\]
Since $\mathbb E_{\mathcal R_x}[\ell_{x_1,x_1';x}(Y)]=0$, we may center
$\varphi(\widehat x(Y))$ to obtain
\[
\mathbb E_{Y\sim\mathcal R_x}\!\Big[
\big(\varphi(\widehat x(Y))-\mathbb E_{\mathcal R_x}[\varphi(\widehat x(Y))]\big)\,
\ell_{x_1,x_1';x}(Y)\Big]
=
\varphi(x_1-x_1').
\]
By Cauchy--Schwarz,
\[
\big|\varphi(x_1-x_1')\big|
\le
\Big(\mathrm{Var}_{Y\sim\mathcal R_x}\big(\varphi(\widehat x(Y))\big)\Big)^{1/2}
\Big(\mathrm{Var}_{Y\sim\mathcal R_x}\big(\ell_{x_1,x_1';x}(Y)\big)\Big)^{1/2},
\]
and hence
\begin{equation}\label{eq:hcr-linear}
\mathrm{Var}_{Y\sim\mathcal R_x}\big(\varphi(\widehat x(Y))\big)
\ \ge\
\frac{\big(\varphi(x_1-x_1')\big)^2}
{\mathrm{Var}_{Y\sim\mathcal R_x}\big(\ell_{x_1,x_1';x}(Y)\big)}.
\end{equation}

We now identify $\ell_{x_1,x_1';x}$ with the generalized privacy amplification
random variable at $\varepsilon=0$:
\[
\ell_{x_1,x_1';x}(y)
=
\frac{\mathcal R_{x_1}(y)-\mathcal R_{x_1'}(y)}{\mathcal R_x(y)}
=
\ell_0\!\left(y; x_1,x_1',\mathcal R_x\right).
\]
Thus, by the definition of the upper shuffle index,
\[
\sup_{x_1\simeq x_1'\in\mathcal X_\perp}\ \sup_{x\in\mathcal X}
\mathrm{Var}_{Y\sim\mathcal R_x}\!\left[\ell_0(Y;x_1,x_1',\mathcal R_x)\right]
\ \le\
\frac{1}{\chi_{\mathrm{up}}(\mathcal R)^2},
\]
or equivalently, for every $x\in\mathcal X$ and every neighboring pair
$x_1\simeq x_1'$,
\begin{equation}\label{eq:var-ell-bound}
\mathrm{Var}_{Y\sim\mathcal R_x}\!\left[\ell_0(Y;x_1,x_1',\mathcal R_x)\right]
\ \le\
\frac{1}{\chi_{\mathrm{up}}(\mathcal R)^2}.
\end{equation}

Next, fix $j\in[d]$ and take $\varphi(v)=v_j$ in \eqref{eq:hcr-linear}.
Choose a zero-out neighboring pair $(x_1,x_1')=(e_j,\perp)$, where $e_j$ is the
$j$-th standard basis vector (note that $e_j\in\mathbb B_2^d$ and $e_j\simeq\perp$).
Then $\varphi(x_1-x_1')=1$, and combining \eqref{eq:hcr-linear} with
\eqref{eq:var-ell-bound} yields
\begin{equation}\label{eq:coord-var-lb}
\mathrm{Var}_{Y\sim\mathcal R_x}\big(\widehat x_j(Y)\big)
\ \ge\ \chi_{\mathrm{up}}(\mathcal R)^2
\qquad\text{for all }x\in\mathcal X.
\end{equation}

Finally, since $\widehat x$ is unbiased, for any $x\in\mathcal X$ we have
\[
\mathbb E_{Y\sim\mathcal R_x}\!\left[\|\widehat x(Y)-x\|_2^2\right]
=
\sum_{j=1}^d \mathbb E_{Y\sim\mathcal R_x}\!\left[(\widehat x_j(Y)-x_j)^2\right]
=
\sum_{j=1}^d \mathrm{Var}_{Y\sim\mathcal R_x}\big(\widehat x_j(Y)\big),
\]
and therefore by \eqref{eq:coord-var-lb},
\[
\mathbb E_{Y\sim\mathcal R_x}\!\left[\|\widehat x(Y)-x\|_2^2\right]
\ \ge\
\sum_{j=1}^d \chi_{\mathrm{up}}(\mathcal R)^2
=
d\,\chi_{\mathrm{up}}(\mathcal R)^2.
\]
Taking the supremum over $x\in\mathbb B_2^d\subseteq\mathcal X$ gives
\[
\mathsf{Err}_1(\mathcal R,\widehat x)
=
\sup_{x\in\mathbb B_2^d}
\mathbb E_{Y\sim\mathcal R_x}\!\left[\|\widehat x(Y)-x\|_2^2\right]
\ \ge\
d\,\chi_{\mathrm{up}}(\mathcal R)^2,
\]
which proves the claim.
\end{proof}


\subsection{Proposition~\ref{prop:privunit-constant-gap}}
\label{sec:proof-privunit-constant-gap}

\privunitconstantgap*

\begin{proof}[Proof]
\begin{definition}[PrivUnit local randomizer {\cite{duchiLocalPrivacyStatistical2013,bhowmickProtectionReconstructionIts2019}}]
\label{def:privunit}
Fix $d\ge 2$ and let the input domain be $\mathcal X=\mathbb S^{d-1}\subset\mathbb R^d$.
Fix parameters $p\in[0,1]$ and $\theta\in[-1,1]$.
For an input $v\in\mathbb S^{d-1}$ define the spherical cap
\[
C_\theta(v)\;:=\;\{u\in\mathbb S^{d-1}:\ \langle u,v\rangle\ge \theta\}.
\]
Let $U\sim\mathrm{Unif}(\mathbb S^{d-1})$ and define
\[
q(\theta,d)\;:=\;\Pr\!\big(\langle U,v\rangle<\theta\big),
\qquad
1-q(\theta,d)\;=\;\Pr\!\big(U\in C_\theta(v)\big),
\]
which depends only on $(\theta,d)$ by rotational symmetry.
The \emph{PrivUnit} local randomizer $\mathrm{PrivUnit}(p,\theta)$ is the map
$\mathcal R:\mathbb S^{d-1}\to\mathbb S^{d-1}$ defined by:
given input $v\in\mathbb S^{d-1}$, output a random $Y\in\mathbb S^{d-1}$ such that
\[
Y \sim
\begin{cases}
\mathrm{Unif}\!\big(C_\theta(v)\big), & \text{with probability }p,\\[3pt]
\mathrm{Unif}\!\big(C_\theta(v)^c\big), & \text{with probability }1-p,
\end{cases}
\]
where $\mathrm{Unif}(A)$ denotes the uniform distribution on a measurable set
$A\subseteq\mathbb S^{d-1}$ with respect to the uniform probability measure on
$\mathbb S^{d-1}$.
\end{definition}


Fix $d\ge 2$ and a threshold $\theta\in[-1,1]$.
Let $v\in\mathbb S^{d-1}$ be an arbitrary input and let
$U\sim\mathrm{Unif}(\mathbb S^{d-1})$.
Write
\[
T:=\langle U,v\rangle,\qquad
q:=\Pr(T<\theta),\qquad 1-q=\Pr(T\ge \theta).
\]
Define the (cap) conditional first moment
\[
\alpha:=\mathbb E[T\mid T\ge \theta].
\]
Similarly, define
\[
\beta=\mathbb E[T\mid T<\theta].
\]
By rotational symmetry, $\mathbb E[U\mid T\ge\theta]$ and $\mathbb E[U\mid T<\theta]$ lie in $\mathrm{span}(v)$, so
\[
\mathbb E[U\mid T\ge \theta]=\alpha\,v,
\qquad
\mathbb E[U\mid T<\theta]=\beta\,v.
\]
Since $\mathbb E[T]=0$, we have $(1-q)\alpha+q\beta=0$, hence
\begin{equation}\label{eq:privunit-beta}
\beta=-\frac{1-q}{q}\,\alpha .
\end{equation}

\paragraph{Step 1: PrivUnit and its mean.}
Fix $p\in[0,1]$. PrivUnit$(p,\theta)$ outputs $Y$ distributed as
$U\mid (T\ge\theta)$ with probability $p$ and as $U\mid (T<\theta)$ with
probability $1-p$. Therefore,
\[
\mathbb E[Y]
=
p\,\alpha v+(1-p)\,\beta v
=
\Bigl(p\alpha-(1-p)\frac{1-q}{q}\alpha\Bigr)v
=
m\,v,
\]
where, defining $\Delta:=p+q-1$,
\begin{equation}\label{eq:privunit-m}
m=\alpha\,\frac{\Delta}{q}.
\end{equation}

\paragraph{Step 2: Reduction to linear unbiased estimators.}
Let $\widehat x:\mathbb S^{d-1}\to\mathbb R^d$ be any (possibly randomized) estimator
such that $\mathbb E[\widehat x(Y)\mid v]=v$ for all $v\in\mathbb S^{d-1}$.
We show that, without loss of generality, we may restrict attention to estimators
of the form $\widehat x(y)=a\,y$ for a scalar $a$.

\medskip
\noindent
\emph{(i) Orthogonal equivariance of PrivUnit.}
For any orthogonal matrix $U\in O(d)$, PrivUnit$(p,\theta)$ satisfies the
equivariance relation
\[
\mathcal R_{Uv} \stackrel{d}{=} U\,\mathcal R_v ,
\]
i.e., if $Y\sim \mathcal R_v$ then $UY \sim \mathcal R_{Uv}$.
(This holds because the spherical cap condition $\langle u,v\rangle\ge\theta$
is preserved under orthogonal transformations.)

\medskip
\noindent
\emph{(ii) Symmetrization of the estimator.}
Let $U\sim \mathrm{Haar}(O(d))$ be independent of everything else, and define the
symmetrized estimator
\[
\widetilde x(y)
~:=~
\mathbb E_U\!\left[\,U^\top\,\widehat x(Uy)\,\right].
\]
This definition depends only on the observation $y$ and does not depend on the
unknown input $v$.

\medskip
\noindent
\emph{Unbiasedness is preserved.}
For any $v\in\mathbb S^{d-1}$ and $Y\sim\mathcal R_v$,
let $Y'\sim \mathcal R_{Uv}$. By (i), we may couple so that $Y'=UY$.
Then
\begin{align*}
\mathbb E[\widetilde x(Y)\mid v]
&=
\mathbb E_U\!\left[U^\top\,\mathbb E\big[\widehat x(UY)\mid v,U\big]\right]\\
&=
\mathbb E_U\!\left[U^\top\,\mathbb E\big[\widehat x(Y')\mid Uv\big]\right]
=
\mathbb E_U[U^\top\,(Uv)]
=
v,
\end{align*}
so $\widetilde x$ is unbiased whenever $\widehat x$ is unbiased.

\medskip
\noindent
\emph{Risk does not increase.}
By Jensen's inequality and orthogonality of $U$,
for any $v\in\mathbb S^{d-1}$,
\begin{align*}
\mathbb E\!\left[\|\widetilde x(Y)-v\|_2^2\mid v\right]
&=
\mathbb E\!\left[\left\|\mathbb E_U\!\left[U^\top\widehat x(UY)-v\right]\right\|_2^2\Bigm| v\right]\\
&\le
\mathbb E_U\,\mathbb E\!\left[\|U^\top\widehat x(UY)-v\|_2^2\mid v,U\right]\\
&=
\mathbb E_U\,\mathbb E\!\left[\|\widehat x(UY)-Uv\|_2^2\mid v,U\right].
\end{align*}
Using $UY\sim\mathcal R_{Uv}$ from (i) and the fact that the map
$w\mapsto \mathbb E[\|\widehat x(Y)-w\|_2^2\mid w]$ is constant over $w\in\mathbb S^{d-1}$
by the same symmetry, we conclude that
\[
\sup_{v\in\mathbb S^{d-1}}\mathbb E\!\left[\|\widetilde x(Y)-v\|_2^2\mid v\right]
\ \le\
\sup_{v\in\mathbb S^{d-1}}\mathbb E\!\left[\|\widehat x(Y)-v\|_2^2\mid v\right].
\]
Hence, for minimax risk, it is without loss of generality to assume that the
estimator is \emph{orthogonally equivariant}, i.e.,
\[
\widetilde x(Uy)=U\,\widetilde x(y)
\qquad \forall\,U\in O(d),\ \forall\,y\in\mathbb S^{d-1}.
\]

\medskip
\noindent
\emph{(iii) Form of an orthogonally equivariant map on the sphere.}
Let $e_1$ be the first basis vector and let
$H:=\{U\in O(d): Ue_1=e_1\}$ be its stabilizer subgroup.
Equivariance implies $\widetilde x(e_1)=\widetilde x(Ue_1)=U\widetilde x(e_1)$
for all $U\in H$. The only vectors fixed by all $U\in H$ are multiples of $e_1$,
so $\widetilde x(e_1)=a e_1$ for some scalar $a$.
For a general $y\in\mathbb S^{d-1}$, pick $V\in O(d)$ with $Ve_1=y$; then
\[
\widetilde x(y)=\widetilde x(Ve_1)=V\widetilde x(e_1)=a\,Ve_1=a\,y.
\]
Therefore, without loss of generality, we may assume $\widehat x(y)=a\,y$.

Finally, imposing unbiasedness gives $a\,\mathbb E[Y\mid v]=v$, and since
$\mathbb E[Y\mid v]=m v$ (from Step~1), we obtain $a=1/m$.
Hence it suffices to analyze the estimator $\widehat x(Y)=Y/m$.


\paragraph{Step 3: Exact $\ell_2$ risk under the optimal unbiased estimator.}
Since $\|Y\|_2=1$ almost surely and $\|v\|_2=1$, we compute
\begin{align*}
\mathsf{Err}_1\!\left(\mathrm{PrivUnit}(p,\theta),\widehat x\right)
&=
\mathbb E\bigl[\|Y/m-v\|_2^2\bigr]\\
&=
\frac{1}{m^2}\,\mathbb E\|Y\|_2^2
- \frac{2}{m}\,\langle \mathbb E[Y],v\rangle
+\|v\|_2^2\\
&=
\frac{1}{m^2}-2+\;1
=
\frac{1}{m^2}-1.
\end{align*}
In the high privacy regime, we have $m\to 0$, hence
\begin{equation}\label{eq:err1-asymp-1overm2}
\mathsf{Err}_1\!\left(\mathrm{PrivUnit}(p,\theta),\widehat x\right)
=
\frac{1}{m^2}\bigl(1+o(1)\bigr).
\end{equation}
Combining \eqref{eq:privunit-m} and \eqref{eq:err1-asymp-1overm2} yields
\begin{equation}\label{eq:err1-in-Delta-chilo-pre}
\mathsf{Err}_1\!\left(\mathrm{PrivUnit}(p,\theta),\widehat x\right)
=
\frac{q^2}{\alpha^2\,\Delta^2}\bigl(1+o(1)\bigr).
\end{equation}

\paragraph{Step 4: Relating $\Delta$ to the lower shuffle index $\chi_{\mathrm{lo}}$.}
Let $\mu$ denote the uniform probability measure on $\mathbb S^{d-1}$.
With respect to $\mu$, the output density of PrivUnit$(p,\theta)$ at input $v$
takes two values:
\[
f_v(u)=
\begin{cases}
\displaystyle h:=\frac{p}{1-q}, & u\in C_\theta(v),\\[6pt]
\displaystyle \ell:=\frac{1-p}{q}, & u\in C_\theta(v)^c.
\end{cases}
\]
Recall we adopt zero-out adjacency and set $\mathcal R_\perp:=\mathcal R_{\mathrm{BG}}:=\mu$.
Then for neighboring inputs $(v,\perp)$ we have
$\ell_0(u;v,\perp,\mathcal R_{\mathrm{BG}})=f_v(u)-1$.
A direct calculation using $\mathbb E_\mu[f_v(U)]=1$ shows
\[
\mathrm{Var}_{U\sim\mu}[f_v(U)-1]
=
(1-q)\Bigl(\frac{p-(1-q)}{1-q}\Bigr)^2
+
q\Bigl(\frac{(1-p)-q}{q}\Bigr)^2
=
\frac{\Delta^2}{q(1-q)}.
\]
Let $\gamma$ be the blanket mass of PrivUnit with blanket distribution $\mu$.
By definition of $\chi_{\mathrm{lo}}$,
\begin{equation}\label{eq:chilo-Delta}
\chi_{\mathrm{lo}}^2
=
\frac{1}{\frac{1}{\gamma}\mathrm{Var}_{U\sim\mu}[f_v(U)-1]}
=
\frac{\gamma\,q(1-q)}{\Delta^2},
\qquad\text{equivalently}\qquad
\Delta^2=\frac{\gamma\,q(1-q)}{\chi_{\mathrm{lo}}^2}.
\end{equation}
Substituting \eqref{eq:chilo-Delta} into \eqref{eq:err1-in-Delta-chilo-pre} gives
\begin{equation}\label{eq:err1-in-chilo}
\mathsf{Err}_1\!\left(\mathrm{PrivUnit}(p,\theta),\widehat x\right)
=
\frac{q}{1-q}\cdot\frac{1}{\gamma\,\alpha^2}\,
\chi_{\mathrm{lo}}^2\bigl(1+O(\chi_{\mathrm{lo}}^{-1})\bigr).
\end{equation}

\paragraph{Step 5: High privacy scaling and the leading constant.}
The high privacy regime for PrivUnit corresponds to $\Delta\to 0$, i.e.,
$p\to 1-q$, which makes the output distribution approach $\mu$.
In this regime $h\to 1$ and $\ell\to 1$, hence the maximal blanket mass satisfies
$\gamma\to 1$. Therefore the leading constant in \eqref{eq:err1-in-chilo} is
\[
C(\theta,d):=\frac{q}{1-q}\cdot\frac{1}{d\,\alpha^2},
\qquad\text{so that}\qquad
\mathsf{Err}_1\!\left(\mathrm{PrivUnit}(p,\theta),\widehat x\right)
=
C(\theta,d)\,d\,\chi_{\mathrm{lo}}^2\bigl(1+o(1)\bigr).
\]
This proves the first displayed claim of the proposition.

\paragraph{Step 6: Asymptotic lower bound on the best constant over $\theta$ as $d\to\infty$.}
To optimize over $\theta$ in high dimension, consider a sequence
$\theta=\theta_d$ with $\tau:=\theta_d\sqrt d=O(1)$.
By the classical normal approximation for spherical marginals,
$Z:=\sqrt d\,T$ converges in distribution to $\mathcal N(0,1)$, which implies
\[
q=\Pr(T<\theta_d)\to \Phi(\tau),
\qquad
1-q\to Q(\tau):=1-\Phi(\tau),
\]
and
\[
\alpha=\mathbb E[T\mid T\ge \theta_d]
=
\frac{1}{\sqrt d}\,\mathbb E[Z\mid Z\ge \tau]\,(1+o(1))
=
\frac{1}{\sqrt d}\,\lambda(\tau)\,(1+o(1)),
\]
where $\lambda(\tau):=\phi(\tau)/Q(\tau)$ and $\phi,\Phi$ are the standard
normal pdf and cdf. Plugging these into $C(\theta,d)$ yields
\[
C(\theta_d,d)
=
\frac{\Phi(\tau)}{Q(\tau)}\cdot\frac{1}{\lambda(\tau)^2}\,(1+o(1))
=
\frac{\Phi(\tau)\,Q(\tau)}{\phi(\tau)^2}\,(1+o(1))
=:C(\tau)\,(1+o(1)).
\]
It remains to minimize $C(\tau)=\Phi(\tau)Q(\tau)/\phi(\tau)^2$ over $\tau\in\mathbb R$.
The function $C$ is even since $\Phi(-\tau)=Q(\tau)$ and $\phi(-\tau)=\phi(\tau)$.
Moreover,
\[
C(0)=\frac{(1/2)(1/2)}{(1/\sqrt{2\pi})^2}=\frac{\pi}{2}.
\]
A direct differentiation of $\log C(\tau)$ shows that $\tau=0$ is the unique
global minimizer:
\[
\frac{d}{d\tau}\log C(\tau)
=
\frac{\phi(\tau)}{\Phi(\tau)}
-\frac{\phi(\tau)}{Q(\tau)}
+2\tau,
\]
which is strictly positive for $\tau>0$ and strictly negative for $\tau<0$.
Consequently,
\[
\inf_{\tau\in\mathbb R} C(\tau)=C(0)=\frac{\pi}{2}.
\]
Therefore,
\[
\liminf_{d\to\infty}\ \inf_{\theta\in[-1,1]} C(\theta,d)
\ \ge\
\inf_{\tau\in\mathbb R} C(\tau)
=
\frac{\pi}{2},
\]
which completes the proof.
\end{proof}



\subsection{Proposition~\ref{prop:privunit-constant-gap-d1}}
\label{app:privunit-constant-gap-d1}

\privunitconstantgapdOne*

\begin{proof}
Let $d=1$ and $\mathcal X=\mathbb S^0=\{-1,+1\}$.
For any $\theta\in(-1,1)$, the spherical cap
$\{u\in\mathbb S^0:\langle u,x\rangle\ge \theta\}$ degenerates: since
$\mathbb S^0=\{\pm1\}$ and $\langle u,x\rangle\in\{\pm1\}$, we have
$\langle u,x\rangle\ge\theta \iff \langle u,x\rangle=+1 \iff u=x$.
Hence, for any such $\theta$, $\mathrm{PrivUnit}(p,\theta)$ is equivalent to the
sign-flip (randomized response) mechanism
\[
Y=
\begin{cases}
x & \text{with prob. } p,\\
-x & \text{with prob. } 1-p,
\end{cases}
\qquad x\in\{\pm1\}.
\]
In particular, we may fix $\theta=0$ without loss of generality and write
$\mathrm{RR}(p)$ for this mechanism.

\paragraph{Unbiased estimation and $\mathsf{Err}_1$.}
Let $t:=2p-1\in(0,1)$ (we assume $p\ge 1/2$; this is the relevant high privacy
direction). Then $\mathbb E[Y\mid x]=tx$.
The estimator $\widehat x_1(Y):=Y/t$ is unbiased since
$\mathbb E[\widehat x_1(Y)\mid x]=\mathbb E[Y\mid x]/t=x$.
Moreover, since $Y^2=1$ a.s.,
\[
\mathsf{Err}_1\!\left(\mathrm{RR}(p),\widehat x_1\right)
=
\sup_{x\in\{\pm1\}}\mathbb E\!\left[\left(\frac{Y}{t}-x\right)^2\Bigm|x\right]
=
\sup_{x}\left(\frac{1}{t^2}\mathbb E[Y^2\mid x]-2\frac{1}{t}\mathbb E[xY\mid x]+1\right)
=
\frac{1}{t^2}-1.
\]

\paragraph{Computing $\chi_{\mathrm{lo}}$.}
Let $\mathcal R_x$ denote the law of $Y$ given input $x\in\{\pm 1\}$.
Under the zero-out convention we take $\mathcal R_{\perp}=\mathcal R_{\mathrm{BG}}$.
The maximal blanket mass is
\[
\gamma=\sum_{y\in\{\pm1\}}\inf_{x\in\{\pm1\}} \mathcal R_x(y).
\]
When $p\ge 1/2$, we have $\inf_x \mathcal R_x(+1)=1-p$ and $\inf_x \mathcal R_x(-1)=1-p$, hence
\[
\gamma=2(1-p)=1-t,
\qquad\text{and}\qquad
\mathcal R_{\mathrm{BG}}(+1)=\mathcal R_{\mathrm{BG}}(-1)=\tfrac12.
\]
For neighboring inputs $(x,\perp)$, the generalized amplification variable at
$\varepsilon=0$ is
\[
\ell_0(y;x,\perp,\mathcal R_{\mathrm{BG}})
=
\frac{\mathcal R_x(y)-\mathcal R_{\mathrm{BG}}(y)}{\mathcal R_{\mathrm{BG}}(y)}.
\]
Taking $x=+1$ (the case $x=-1$ is identical), we have
$\mathcal R_{+1}(+1)=p=(1+t)/2$ and $\mathcal R_{+1}(-1)=1-p=(1-t)/2$, so
\[
\ell_0(+1)=t,
\qquad
\ell_0(-1)=-t.
\]
Therefore, for $Y\sim \mathcal R_{\mathrm{BG}}$,
$\mathrm{Var}[\ell_0(Y)]=t^2$, and by the definition of $\chi_{\mathrm{lo}}$,
\[
\chi_{\mathrm{lo}}^2
=
\frac{1}{\frac{1}{\gamma}\mathrm{Var}_{Y\sim \mathcal R_{\mathrm{BG}}}[\ell_0(Y)]}
=
\frac{\gamma}{t^2}
=
\frac{1-t}{t^2}.
\]
Equivalently, $t$ solves the quadratic equation
\[
\chi_{\mathrm{lo}}^2 t^2 + t - 1 = 0,
\]
so (taking the positive root)
\begin{equation}\label{eq:t-in-chilo}
t
=
\frac{-1+\sqrt{1+4\chi_{\mathrm{lo}}^2}}{2\chi_{\mathrm{lo}}^2}.
\end{equation}

\paragraph{Expansion for $\chi_{\mathrm{lo}}\to\infty$.}
Using $\sqrt{1+4\chi_{\mathrm{lo}}^2}
=2\chi_{\mathrm{lo}}\sqrt{1+\frac{1}{4\chi_{\mathrm{lo}}^2}}
=2\chi_{\mathrm{lo}}\left(1+\frac{1}{8\chi_{\mathrm{lo}}^2}+O(\chi_{\mathrm{lo}}^{-4})\right)$,
\eqref{eq:t-in-chilo} yields
\[
t
=
\frac{1}{\chi_{\mathrm{lo}}}
-\frac{1}{2\chi_{\mathrm{lo}}^2}
+O(\chi_{\mathrm{lo}}^{-3}).
\]
Hence,
\[
\frac{1}{t^2}
=
\chi_{\mathrm{lo}}^2
\left(1+\frac{1}{\chi_{\mathrm{lo}}}+O(\chi_{\mathrm{lo}}^{-2})\right),
\]
and therefore
\[
\mathsf{Err}_1\!\left(\mathrm{RR}(p),\widehat x_1\right)
=
\left(\frac{1}{t^2}\right)-1
=
\chi_{\mathrm{lo}}^2
\left(1+\chi_{\mathrm{lo}}^{-1}+O(\chi_{\mathrm{lo}}^{-2})\right),
\qquad (\chi_{\mathrm{lo}}\to\infty),
\]
where the subtraction of $1$ is absorbed into the $O(\chi_{\mathrm{lo}}^{-2})$
term after factoring out $\chi_{\mathrm{lo}}^2$.
This proves the claimed expansion.
\end{proof}




\subsection{Theorem~\ref{thm:gaussian-blanket-mixture-minimax}}

\label{sec:proof-gaussian-blanket-mixture-minimax}

\mixgauss*


\begin{proof}
Throughout, write $A:=1-\gamma\in(0,1]$ and recall that the blanket distribution
is $\mathcal R_{\mathrm{BG}}=\mathcal N(0,\sigma_0^2 I_d)$.

\paragraph{Step 1: Exact formula for $\chi_{\mathrm{lo}}(\mathcal R)$.}
Fix $x\in\mathcal X$ and let $\phi_{\sigma_0}(y)$ denote the density of
$\mathcal N(0,\sigma_0^2 I_d)$. The released distribution under input $x$ is the
mixture
\[
\mathcal R_x=\gamma\,\mathcal N(0,\sigma_0^2 I_d)+A\,\mathcal N(x,\sigma_0^2 I_d),
\qquad
\mathcal R_\perp=\mathcal R_{\mathrm{BG}}=\mathcal N(0,\sigma_0^2 I_d).
\]
Hence, with respect to $\mathcal R_{\mathrm{BG}}$, the likelihood ratio is
\[
\frac{d\mathcal R_x}{d\mathcal R_{\mathrm{BG}}}(y)
=
\gamma + A\,
\frac{\phi_{\sigma_0}(y-x)}{\phi_{\sigma_0}(y)}
=
\gamma + A\exp\!\Big(\frac{\langle x,y\rangle}{\sigma_0^2}
-\frac{\|x\|_2^2}{2\sigma_0^2}\Big).
\]
For the zero-out neighbor pair $(x,\perp)$, the corresponding centered blanket-referenced difference equals
\[
\ell_0\!\left(y;x,\perp,\mathcal R_{\mathrm{BG}}\right)
=
\frac{\mathcal R_x(y)-\mathcal R_\perp(y)}{\mathcal R_{\mathrm{BG}}(y)}
=
\frac{d\mathcal R_x}{d\mathcal R_{\mathrm{BG}}}(y)-1
=
A\Big(\exp\!\big(\tfrac{\langle x,y\rangle}{\sigma_0^2}
-\tfrac{\|x\|_2^2}{2\sigma_0^2}\big)-1\Big).
\]
Under $Y\sim\mathcal R_{\mathrm{BG}}=\mathcal N(0,\sigma_0^2 I_d)$ we have
$\langle x,Y\rangle\sim \mathcal N(0,\sigma_0^2\|x\|_2^2)$, and therefore
\[
\mathbb E\Big[\exp\!\Big(\frac{\langle x,Y\rangle}{\sigma_0^2}
-\frac{\|x\|_2^2}{2\sigma_0^2}\Big)\Big]=1,
\qquad
\mathbb E\Big[\exp\!\Big(2\frac{\langle x,Y\rangle}{\sigma_0^2}
-\frac{\|x\|_2^2}{\sigma_0^2}\Big)\Big]=\exp\!\Big(\frac{\|x\|_2^2}{\sigma_0^2}\Big).
\]
It follows that
\[
\mathrm{Var}_{Y\sim\mathcal R_{\mathrm{BG}}}\!\left[
\ell_0\!\left(Y;x,\perp,\mathcal R_{\mathrm{BG}}\right)\right]
=
A^2\Big(\exp(\|x\|_2^2/\sigma_0^2)-1\Big).
\]
By monotonicity in $\|x\|_2$ and $\sup_{\|x\|_2\le 1}\|x\|_2=1$, the worst case
occurs at $\|x\|_2=1$, hence
\[
\sup_{x\simeq x'}\sqrt{\frac{1}{\gamma}\,
\mathrm{Var}_{Y\sim\mathcal R_{\mathrm{BG}}}\!\left[
\ell_0\!\left(Y;x,x',\mathcal R_{\mathrm{BG}}\right)\right]}
=
\sqrt{\frac{A^2}{\gamma}\Big(e^{1/\sigma_0^2}-1\Big)}.
\]
Recalling the definition of $\chi_{\mathrm{lo}}$, we obtain the exact identity
\[
\chi_{\mathrm{lo}}(\mathcal R)^2
=
\frac{\gamma}{A^2}\cdot \frac{1}{e^{1/\sigma_0^2}-1}
=
\frac{\gamma}{(1-\gamma)^2}\cdot \frac{1}{e^{1/\sigma_0^2}-1}.
\]

\paragraph{Step 2: Worst-case squared error of the unbiased estimator.}
Consider the linear estimator $\widehat x(Y)=Y/A$, which is unbiased.
For any $x\in\mathcal X$, since $\widehat x(Y)$ is unbiased for $x$,
\[
\mathbb E\!\left[\|\widehat x(Y)-x\|_2^2\right]
=
\mathrm{tr}\!\left(\mathrm{Cov}(\widehat x(Y))\right).
\]
The distribution $\mathcal R_x$ is a two-component Gaussian mixture with common covariance $\sigma_0^2 I_d$ and means $0$ and $x$. 
Thus
\[
\mathbb E[Y]=(1-\gamma)x=A x,
\qquad
\mathrm{Cov}(Y)=\sigma_0^2 I_d+\gamma A\,xx^\top.
\]
Here,
\[
\mathrm{Cov}(Y)
=
\mathbb E\!\left[\mathrm{Cov}(Y\mid B)\right]
+
\mathrm{Cov}\!\left(\mathbb E[Y\mid B]\right).
\]
Since \(\mathrm{Cov}(Y\mid B)=\sigma_0^2 I_d\) for both \(B=0,1\),
\[
\mathbb E\!\left[\mathrm{Cov}(Y\mid B)\right]=\sigma_0^2 I_d.
\]
and
\[
\mathrm{Cov}\!\left(\mathbb E[Y\mid B]\right)
=
\gamma(0-Ax)(0-Ax)^\top + A(x-Ax)(x-Ax)^\top
=
\gamma A^2 xx^\top + A\gamma^2 xx^\top
=
\gamma A\,xx^\top.
\]


Therefore,
\[
\mathrm{Cov}(Y)=\sigma_0^2 I_d+\gamma A\,xx^\top.
\]
Therefore,
\[
\mathrm{Cov}(\widehat x(Y))
=
\frac{1}{A^2}\,\mathrm{Cov}(Y)
=
\frac{\sigma_0^2}{A^2}I_d+\frac{\gamma}{A}\,xx^\top,
\]
and taking the trace yields the exact squared error
\[
\mathbb E\!\left[\|\widehat x(Y)-x\|_2^2\right]
=
\frac{d\,\sigma_0^2}{A^2}+\frac{\gamma}{A}\|x\|_2^2
\]
Maximizing over $\|x\|_2\le 1$ gives the worst-case single-user MSE
\begin{equation}\label{eq:gauss-mix-mse-exact}
\sup_{x\in\mathcal X}\ \mathbb E\!\left[\|\widehat x(Y)-x\|_2^2\right]
=
\frac{d\,\sigma_0^2}{A^2}+\frac{\gamma}{A}.
\end{equation}


\paragraph{Step 3: Tuning of $(\gamma,\sigma_0)$ under $\chi_{\mathrm{lo}}(\mathcal R)\ge \chi$.}
Fix $\chi>0$ and write $A:=1-\gamma\in(0,1)$ and $t:=1/\sigma_0^2>0$.
Imposing the equality constraint $\chi_{\mathrm{lo}}(\mathcal R)=\chi$ is without loss of generality for an upper bound (we
are free to pick any feasible parameters), and yields the exact relation
\begin{equation}\label{eq:exact-t}
e^{t}-1=\frac{\gamma}{A^2\chi^2}=\frac{1-A}{A^2\chi^2}
\qquad\Longleftrightarrow\qquad
t=\log\!\left(1+\frac{1-A}{A^2\chi^2}\right).
\end{equation}
Define
\[
u:=\frac{1-A}{A^2\chi^2}.
\]
Then $t=\log(1+u)$. In the strong-privacy regime we will choose $A\to 0$, hence
$u\to 0$ as $\chi\to\infty$.

\medskip
\noindent\textbf{Choice of parameters.}
Set
\begin{equation}\label{eq:A-choice}
A:=\chi^{-2/3},\qquad \gamma:=1-A,\qquad t:=\log(1+u),\qquad \sigma_0^2:=1/t,
\end{equation}
where $u=(1-A)/(A^2\chi^2)$ as above.
With this choice,
\begin{equation}\label{eq:u-expand}
u=\frac{1-A}{A^2\chi^2}
=\frac{1}{A^2\chi^2}-\frac{1}{A\chi^2}
=\chi^{-2/3}-\chi^{-4/3}.
\end{equation}
In particular, for all sufficiently large $\chi$, we have $0<u\le 1/2$, so the
Taylor expansion of $\log(1+u)$ with a controlled remainder applies.

\medskip
\noindent\textbf{A useful analytic bound.}
For $u\in(0,1/2]$, define
\[
R_{\log}(u):=\log(1+u)-\left(u-\frac{u^2}{2}\right).
\]
A standard remainder bound (e.g. from the Lagrange form of the Taylor remainder,
using that $|(\log(1+u))^{(3)}|=2/(1+u)^3\le 2$ on $[0,1/2]$) gives
\begin{equation}\label{eq:log-remainder}
|R_{\log}(u)|\le C_{\log}\,u^3
\qquad\text{for all }u\in(0,1/2],
\end{equation}
for some universal constant $C_{\log}>0$.
Consequently,
\begin{equation}\label{eq:t-factorized}
t=\log(1+u)=u\left(1-\frac{u}{2}+\rho(u)\right),
\qquad |\rho(u)|\le C_{\log}u^2.
\end{equation}

\medskip
\noindent\textbf{Expansion of the dominant term $\boldsymbol{1/(A^2 t)}$.}
Using \eqref{eq:t-factorized},
\[
\frac{1}{A^2 t}
=\frac{1}{A^2 u}\cdot \frac{1}{1-\frac{u}{2}+\rho(u)}.
\]
For $\chi$ large enough, $u$ is small and thus
$\left|-\frac{u}{2}+\rho(u)\right|\le 1/4$, so we may use the expansion
$\frac{1}{1+z}=1-z+O(z^2)$ with $z=-\frac{u}{2}+\rho(u)$ to obtain
\begin{equation}\label{eq:inv-factor}
\frac{1}{1-\frac{u}{2}+\rho(u)}
=
1+\frac{u}{2}+O(u^2),
\end{equation}
where the $O(u^2)$ term is uniform for all sufficiently large $\chi$.

Next, observe that
\begin{equation}\label{eq:1overA2u}
\frac{1}{A^2 u}
=\frac{1}{A^2}\cdot \frac{A^2\chi^2}{1-A}
=\frac{\chi^2}{1-A}.
\end{equation}
Since $A=\chi^{-2/3}\to 0$, we also have the geometric expansion
\begin{equation}\label{eq:inv-1-A}
\frac{1}{1-A}=1+A+O(A^2).
\end{equation}
Combining \eqref{eq:inv-factor}, \eqref{eq:1overA2u}, and \eqref{eq:inv-1-A}
yields
\begin{equation}\label{eq:dominant-expansion}
\frac{1}{A^2 t}
=
\chi^2\left(1+A+\frac{u}{2}+O(A^2+u^2+Au)\right).
\end{equation}
With our choice \eqref{eq:A-choice} and \eqref{eq:u-expand}, we have
$A=\chi^{-2/3}$ and $u=\chi^{-2/3}+O(\chi^{-4/3})$, so
\[
A+\frac{u}{2}
=
\chi^{-2/3}+\frac{1}{2}\chi^{-2/3}+O(\chi^{-4/3})
=
\frac{3}{2}\chi^{-2/3}+O(\chi^{-4/3}),
\]
and moreover $A^2+u^2+Au=O(\chi^{-4/3})$.
Plugging into \eqref{eq:dominant-expansion} gives the refined asymptotic
\begin{equation}\label{eq:dominant-final}
\frac{1}{A^2 t}
=
\chi^2\left(1+\frac{3}{2}\chi^{-2/3}+O(\chi^{-4/3})\right).
\end{equation}

\medskip
\noindent\textbf{Mixture penalty term.}
The second term in the exact worst-case MSE \eqref{eq:gauss-mix-mse-exact} is
\[
\frac{\gamma}{A}=\frac{1-A}{A}=\frac{1}{A}-1=\chi^{2/3}-1.
\]
Therefore, for fixed $d\ge 1$,
\begin{equation}\label{eq:mixture-relative}
\frac{\gamma/A}{d\chi^2}
=
O(\chi^{-4/3}),
\end{equation}
so it contributes only to the $O(\chi^{-4/3})$ remainder in the relative error.

\medskip
\noindent\textbf{Conclusion.}
Substituting \eqref{eq:dominant-final} and \eqref{eq:mixture-relative} into the
exact MSE expression \eqref{eq:gauss-mix-mse-exact} yields
\[
\sup_{\|x\|_2\le 1}\ \mathbb E\!\left[\|\widehat x(Y)-x\|_2^2\right]
=
d\chi^2\left(1+\frac{3}{2}\chi^{-2/3}+O(\chi^{-4/3})\right),
\]
with $(\gamma,\sigma_0)$ as in \eqref{eq:A-choice}. This proves the claimed
upper bound for $\mathsf{Err}_1$ under the constraint
$\chi_{\mathrm{lo}}(\mathcal R)\ge \chi$.



\end{proof}


\subsection{Theorem~\ref{thm:centrallimittheorem}}
\label{sec:proof-centrallimittheorem}

\centrallimittheorem*



\begin{proof}
Fix $\sigma>0$ and assume that $\{(\varepsilon_n,\delta_n)\}_{n\ge 1}$ lies in the
$\sigma$-high privacy regime (Definition~\ref{def:chi-high-privacy-regime}).

\paragraph{Step 1: Reduction to shuffle-index constrained problems.}
By Lemma~\ref{thm:sandwich-alpha-over-n}, for any $\eta>0$,
\begin{equation}\label{eq:clt-sandwich}
\mathsf{Err}^{\star}_{\mathrm{up}}(\sigma)
\ \le\
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
\mathsf{Err}^{\star}_{\mathrm{lo}}(\sigma+\eta).
\end{equation}

\paragraph{Step 2: Lower bound.}
Consider the single-user optimization problem~\eqref{eq:minimax-variance-chiup}
with constraint $\chi_{\mathrm{up}}(\mathcal R)\ge \sigma$.
By Theorem~\ref{thm:hcr-chiup-lower-bound}, for any feasible pair
$(\mathcal R,\widehat x)$ we have
\[
\mathsf{Err}_1(\mathcal R,\widehat x)
\ \ge\
d\,\chi_{\mathrm{up}}(\mathcal R)^2
\ \ge\
d\,\sigma^2.
\]
Taking the infimum over all feasible $(\mathcal R,\widehat x)$ yields
\begin{equation}\label{eq:clt-lb-errup}
\mathsf{Err}^{\star}_{\mathrm{up}}(\sigma)\ \ge\ d\,\sigma^2.
\end{equation}
Combining \eqref{eq:clt-sandwich} and \eqref{eq:clt-lb-errup} gives
\[
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})\ \ge\ d\,\sigma^2.
\]
\paragraph{Step 3: Upper bound.}
Fix $\eta=1$. We invoke the explicit upper bound proved in Corollary~\ref{cor:chi_lo_upperbound}: there
exist constants $\chi_0\ge 1$ and $C>0$ such that for all $\chi\ge \chi_0$,
\begin{equation}\label{eq:thm36-explicit}
\mathsf{Err}^{\star}_{\mathrm{lo}}(\chi)
\ \le\
d\,\chi^{2}\left(1+\frac{3}{2}\chi^{-2/3}+C\,\chi^{-4/3}\right).
\end{equation}
Using the right inequality in~\eqref{eq:clt-sandwich} (with $\eta=1$) yields
\begin{equation}\label{eq:clt-ub-explicit}
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
\mathsf{Err}^{\star}_{\mathrm{lo}}(\sigma+1).
\end{equation}

\medskip
\noindent\textbf{Case 1: $\sigma+1\ge \chi_0$.}
Combining \eqref{eq:clt-ub-explicit} with \eqref{eq:thm36-explicit} (applied at
$\chi=\sigma+1$) gives
\begin{equation}\label{eq:clt-ub-case1}
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
d\,(\sigma+1)^{2}\left(1+\frac{3}{2}(\sigma+1)^{-2/3}+C\,(\sigma+1)^{-4/3}\right).
\end{equation}
Define for $\sigma\ge \chi_0-1$,
\begin{equation}\label{eq:eta-def-case1}
\eta(\sigma)
:=
\frac{(\sigma+1)^{2}}{\sigma^{2}}\left(1+\frac{3}{2}(\sigma+1)^{-2/3}
+C\,(\sigma+1)^{-4/3}\right)-1.
\end{equation}
Then \eqref{eq:clt-ub-case1} rewrites as
\[
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
d\,\sigma^{2}\bigl(1+\eta(\sigma)\bigr),
\qquad\text{for all $n$ sufficiently large.}
\]
Moreover, since the bracketed factor in \eqref{eq:eta-def-case1} is at least~$1$
and $(\sigma+1)^2/\sigma^2\ge 1$, we have $\eta(\sigma)\ge 0$ for all
$\sigma\ge \chi_0-1$. Finally, as $\sigma\to\infty$,
\[
\eta(\sigma)
=
\left(\frac{(\sigma+1)^2}{\sigma^2}-1\right)
+
\frac{(\sigma+1)^2}{\sigma^2}\left(\frac{3}{2}(\sigma+1)^{-2/3}
+C(\sigma+1)^{-4/3}\right)
=
O(\sigma^{-1})+O(\sigma^{-2/3})
=
O(\sigma^{-2/3}).
\]

\medskip
\noindent\textbf{Case 2: $\sigma+1< \chi_0$.}
In this case, we simply define $\eta(\sigma)\ge 0$ large enough so that
\[
\mathsf{Err}^{\star}_{\mathrm{lo}}(\sigma+1)\ \le\ d\,\sigma^{2}\bigl(1+\eta(\sigma)\bigr).
\]
For example, it suffices to take
\[
\eta(\sigma):=\max\left\{0,\ \frac{\mathsf{Err}^{\star}_{\mathrm{lo}}(\sigma+1)}{d\,\sigma^{2}}-1\right\}.
\]
With this definition, the bound
\[
\mathsf{Err}^{\star}_{\mathrm{DP}}(\{(\varepsilon_n,\delta_n)\}_{n\ge 1})
\ \le\
d\,\sigma^{2}\bigl(1+\eta(\sigma)\bigr)
\]
holds for all $n$ sufficiently large by \eqref{eq:clt-ub-explicit}. Moreover,
this definition affects $\eta(\sigma)$ only on the bounded interval
$\sigma\in(0,\chi_0-1)$ and therefore does not change the asymptotic statement
$\eta(\sigma)=O(\sigma^{-2/3})$ as $\sigma\to\infty$.


\paragraph{Conclusion.}
Combining the lower and upper bounds established above completes the proof.
\end{proof}


\subsection{Proposition~\ref{prop:gaussian-risk-chiup}}
\label{app:gaussian}

\gaussianRiskChiUp*

\begin{proof}
  
Consider the Gaussian local randomizer
\[
\mathcal R_x = \mathcal N(x,\sigma_0^2 I_d),\qquad x\in\mathbb B_2^d,
\]
which corresponds to the case $\gamma=0$. A natural unbiased per-message
estimator is
\[
\widehat x(Y)=Y,
\qquad
\text{since }\ \mathbb E[Y\mid x]=x.
\]
Hence the (single-user) worst-case squared error is
\begin{equation}
\label{eq:gauss-err1-l2}
\mathsf{Err}_1(\mathcal R,\widehat x)
:=\sup_{x\in\mathbb B_2^d}\ \mathbb E\!\left[\|\widehat x(Y)-x\|_2^2\right]
=\mathbb E\|Z\|_2^2
=d\sigma_0^2,
\qquad
Z\sim\mathcal N(0,\sigma_0^2 I_d).
\end{equation}

\paragraph{Step 1: computing a concrete variance term for $\chi_{\mathrm{chua}}$.}
Recall
\[
\ell_0(y;x_1,x_1',\mathcal R_x)
=
\frac{\mathcal R_{x_1}(y)-\mathcal R_{x_1'}(y)}{\mathcal R_x(y)}.
\]
Write $\sigma^2:=\sigma_0^2$ and $\mathcal R_\mu=\mathcal
N(\mu,\sigma^2)$.

Let $U$ be any orthogonal matrix. Since $Y\sim\mathcal N(\mu,\sigma^2 I_d)$ implies
$UY\sim\mathcal N(U\mu,\sigma^2 I_d)$, and Gaussian density ratios are preserved
under the change of variables $y\mapsto Uy$, we have
\[
\ell_0(Y;x_1,x_1',\mathcal R_x)\ \stackrel{d}{=}\ \ell_0(UY;Ux_1,Ux_1',\mathcal R_{Ux}),
\]
and hence $\mathrm{Var}\!\left[\ell_0(Y;x_1,x_1',\mathcal R_x)\right]$ is invariant
under applying the same rotation to $(x_1,x_1',x)$.
Therefore, we may rotate coordinates so that $x_1=e_1$, $x_1'=0$, and $x=-e_1$.
Moreover, $\ell_0(y;e_1,0,\mathcal R_{-e_1})$ depends on $y$ only through the
one-dimensional projection $\langle y,e_1\rangle$, and for
$Y\sim\mathcal N(-e_1,\sigma^2 I_d)$ we have $\langle Y,e_1\rangle\sim\mathcal N(-1,\sigma^2)$.
Identifying this coordinate with $\mathbb R$, we may write $x_1=1$, $x_1'=0$, and $x=-1$ without loss of generality.


Using the Gaussian density ratio identity
\[
\frac{\phi_{\mu_1,\sigma^2}(y)}{\phi_{\mu_2,\sigma^2}(y)}
=
\exp\!\left(\frac{(\mu_1-\mu_2)y}{\sigma^2}
-\frac{\mu_1^2-\mu_2^2}{2\sigma^2}\right),
\]
we obtain
\[
\frac{\mathcal R_1(y)}{\mathcal R_{-1}(y)}
=\exp\!\left(\frac{2y}{\sigma^2}\right),
\qquad
\frac{\mathcal R_0(y)}{\mathcal R_{-1}(y)}
=\exp\!\left(\frac{y}{\sigma^2}+\frac{1}{2\sigma^2}\right),
\]
and therefore
\begin{equation}
\label{eq:ell0-gauss}
\ell_0(y)
=
\ell_0(y;1,0,\mathcal R_{-1})
=
\exp\!\left(\frac{2y}{\sigma^2}\right)
-
\exp\!\left(\frac{y}{\sigma^2}+\frac{1}{2\sigma^2}\right).
\end{equation}

Let $Y\sim\mathcal R_x=\mathcal N(-1,\sigma^2)$. Using the Gaussian MGF
$\mathbb E[e^{tY}]=\exp(t\mu+\tfrac12 t^2\sigma^2)$ with $\mu=-1$, one checks
$\mathbb E[\ell_0(Y)]=0$, and hence $\mathrm{Var}[\ell_0(Y)]=\mathbb
E[\ell_0(Y)^2]$. Expanding the square in \eqref{eq:ell0-gauss} and taking
expectations term-by-term yields
\begin{equation}
\label{eq:var-ell0-gauss}
\mathrm{Var}_{Y\sim\mathcal N(-1,\sigma^2)}[\ell_0(Y)]
=
e^{4/\sigma^2}-2e^{2/\sigma^2}+e^{1/\sigma^2}.
\end{equation}

\[
V(\sigma^2)
:=
e^{4/\sigma^2}-2e^{2/\sigma^2}+e^{1/\sigma^2},
\]
Then, by definition of $\chi_{\mathrm{chua}}$,
\[
\chi_{\mathrm{chua}}(\mathcal R)^2
=
\frac{1}{\mathrm{Var}_{Y\sim \mathcal R_x}\!\left[\ell_0(Y;x_1,x_1',\mathcal R_x)\right]}
=
\frac{1}{V(\sigma^2)}.
\]

\paragraph{Step 2: asymptotic expansion as $\sigma_0\to\infty$.}
Let $a:=1/\sigma^2$. Using $e^{ca}=1+ca+\frac{c^2}{2}a^2+\frac{c^3}{6}a^3+\frac{c^4}{24}a^4+O(a^5)$,
we expand \eqref{eq:var-ell0-gauss}:
\begin{align}
V(\sigma^2)
&=
a+\frac{9}{2}a^2+\frac{49}{6}a^3+\frac{75}{8}a^4+O(a^5).
\label{eq:V-series-in-a}
\end{align}
Inverting the series gives
\begin{align}
\chi_{\mathrm{chua}}^2(\sigma^2)
=\frac{1}{V(\sigma^2)}
&=
\frac{1}{a}\Bigl(1-\frac{9}{2}a+\frac{145}{12}a^2-27a^3+O(a^4)\Bigr)
\nonumber\\
&=
\sigma^2-\frac{9}{2}+\frac{145}{12}\frac{1}{\sigma^2}-\frac{27}{\sigma^4}
+O\!\left(\frac{1}{\sigma^6}\right).
\label{eq:chiup-tilde-series-in-sigma}
\end{align}

\paragraph{Step 3: expressing $\sigma_0^2$ (hence $\mathsf{Err}_1$) as a series in $\chi_{\mathrm{chua}}$.}
Reverting the expansion \eqref{eq:chiup-tilde-series-in-sigma} yields, as
$\chi_{\mathrm{chua}}\to\infty$,
\begin{align}
\sigma^2
&=
\chi_{\mathrm{chua}}^2
+\frac{9}{2}
-\frac{145}{12}\,\chi_{\mathrm{chua}}^{-2}
+\frac{651}{8}\,\chi_{\mathrm{chua}}^{-4}
+O\!\left(\chi_{\mathrm{chua}}^{-6}\right).
\label{eq:sigma2-in-chiup-tilde}
\end{align}

\paragraph{Conclusion (error expansion).}
Combining \eqref{eq:gauss-err1-l2} and \eqref{eq:sigma2-in-chiup-tilde}, we obtain
\[
\mathsf{Err}_1(\mathcal R,\widehat x)
=
d\,\sigma_0^2
=
d\,\chi_{\mathrm{chua}}^2
+\frac{9}{2}d
-\frac{145}{12}d\,\chi_{\mathrm{chua}}^{-2}
+O\!\left(d\,\chi_{\mathrm{chua}}^{-4}\right),
\qquad
(\sigma_0\to\infty).
\]
\end{proof}


\section{Regularity conditions for the local randomizer}
\label{sec:regularity-conditions}

\begin{assumption}[Regularity conditions for the local randomizer]
\label{assump:regularity}
Consider the local randomizer $\mathcal R:\mathcal X_\perp\to\mathcal Y$ and recall that we set $\mathcal R_\perp:=\mathcal R_{\mathrm{BG}}$ under zero-out adjacency.
We assume that there exists $\rho_0>0$ such that, for every pair
$x_1\neq x_1'\in\mathcal X_\perp$ and every reference distribution
$
  \mathcal R_{\mathrm{ref}}\in
  \bigl\{\mathcal R_{\mathrm{BG}}\bigr\}
  \,\cup\,
  \bigl\{\mathcal R_x : x\in\mathcal X\bigr\},
$
the following conditions hold uniformly over all $\varepsilon\le\rho_0$.


\begin{enumerate}
  \item[\textup{(1)}]
  \textbf{Uniform moment bounds.}
  For every integer $k\ge 1$,
  $
    \mathbb E_{Y\sim \mathcal{R}_{\mathrm{ref}}}
    \bigl[\,|\ell_{\varepsilon}(Y;x_1,x_1^\prime,\mathcal R_{\mathrm{ref}})|^k\,\bigr]
    <\infty.
  $

\item[\textup{(2)}]
\textbf{Non-degenerate variance.}
The variance
$
  \sigma^2 := \mathrm{Var}_{Y\sim \mathcal{R}_{\mathrm{ref}}}\bigl(\ell_{0}(Y;x_1,x_1^\prime,\mathcal R_{\mathrm{ref}})\bigr)
$
is strictly positive when $\mathcal R_{x_1} \neq \mathcal R_{x_1^\prime}$. Moreover, the following conditions hold:
$
  \int \frac{\mathcal R_{x_1}(y)^2}{\mathcal R_{\mathrm{ref}}(y)}\,dy < \infty
$ and
$
  \int \frac{\mathcal R_{x_1'}(y)^2}{\mathcal R_{\mathrm{ref}}(y)}\,dy < \infty.
$
  \item[\textup{(3)}]
  \textbf{Structural condition.}
  Either of the following holds.
  \begin{enumerate}
\item[\textup{(Cont)}]

$\ell_{\varepsilon}(Y;x_1,x_1',\mathcal{R}_{\mathrm{ref}})$ has a nontrivial absolutely continuous component with respect to Lebesgue
measure whose support contains a fixed nondegenerate bounded interval
$I\subset\mathbb{R}$ independent of
$\varepsilon$.
    \item[\textup{(Bound)}]
    There exists a constant $C<\infty$ such that
    $
      |\ell_{\varepsilon}(Y;x_1,x_1^\prime,\mathcal R_{\mathrm{ref}})|
      \le C
      \quad\text{almost surely}.
    $
  \end{enumerate}
\end{enumerate}
\end{assumption}

Assumption~\ref{assump:regularity} is mild: any nontrivial local randomizer that satisfies pure LDP automatically satisfies these conditions, and even when pure LDP does not hold, if the privacy amplification random variable $\ell_0(Y;x_1,x_1',\mathcal R_{\mathrm{ref}})$ is non-degenerate (i.e., not almost surely constant), then one can enforce the bounded case~\textup{(Bound)} in~(3) by truncating the output space to a large but bounded interval (i.e., by slightly modifying the local randomizer). 


\section{Computing the shuffled $(\varepsilon,\delta)$ guarantee}
\label{app:delta-computation}
Lemma 5.3 of Balle et al.~\cite{ballePrivacyBlanketShuffle2019} implies that the shuffled blanket-mixed Gaussian mechanism is
$(\varepsilon,\delta(\varepsilon))$-DP with
\[
\delta(\varepsilon)\ \le\ 
\frac{1}{n\gamma}\;
\mathbb E\Bigg[
\Bigg(\sum_{i=1}^{M_0}\ell_{\varepsilon}(Y_i)\Bigg)_{+}
\Bigg]
\]
where
\[\qquad
M_0\sim\mathrm{Bin}(n,\gamma),\;\;
Y_1,Y_2,\ldots \stackrel{\mathrm{i.i.d.}}{\sim} \mathcal R^{\mathrm{BMG}}_{\mathrm{BG}},
\]
and $(a)_+ := \max\{a,0\}$.

In the zero-out adjacency model, the neighboring inputs are
$x\in\mathcal X$ and $\perp$, and $\mathcal{R}^{\mathrm{BMG}}_\perp$ is the blanket
distribution.
\begin{align}
\nonumber &\mathcal R^{\mathrm{BMG}}_{\mathrm{BG}} = \mathcal R^{\mathrm{BMG}}_{\perp} = \mathcal N(0,\sigma_0^2 I_d),\\
\nonumber &\mathcal R^{\mathrm{BMG}}_x = \gamma\,\mathcal N(0,\sigma_0^2 I_d) + (1-\gamma)\,\mathcal N(x,\sigma_0^2 I_d).
\end{align}
Hence, for any $\varepsilon>0$
\begin{align}
&\ell_{\varepsilon}(y)
:=\frac{\mathcal R^{\mathrm{BMG}}_x(y)-e^{\varepsilon}\mathcal R^{\mathrm{BMG}}_{\perp}(y)}{\mathcal R^{\mathrm{BMG}}_{\mathrm{BG}}(y)}\nonumber\\
&=\gamma+(1-\gamma)\exp\!\left(
\frac{\langle y,x\rangle}{\sigma_0^2}-\frac{\|x\|_2^2}{2\sigma_0^2}
\right)-e^{\varepsilon}.
\end{align}

Therefore, we can compute the distribution of $\ell_\varepsilon(Y)$, which enables the rigorous numerical upper bounds using the FFT-based accountant of \citet{takagiAnalysisShufflingPure2026}, which computes the required convolution terms efficiently with
explicit truncation/discretization/wrap-around error bounds.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

% This document was modified from the file originally made available by
% Pat Langley and Andrea Danyluk for ICML-2K. This version was created
% by Iain Murray in 2018, and modified by Alexandre Bouchard in
% 2019 and 2021 and by Csaba Szepesvari, Gang Niu and Sivan Sabato in 2022.
% Modified again in 2023 and 2024 by Sivan Sabato and Jonathan Scarlett.
% Previous contributors include Dan Roy, Lise Getoor and Tobias
% Scheffer, which was slightly modified from the 2010 version by
% Thorsten Joachims & Johannes Fuernkranz, slightly modified from the
% 2009 version by Kiri Wagstaff and Sam Roweis's 2008 version, which is
% slightly modified from Prasad Tadepalli's 2007 version which is a
% lightly changed version of the previous year's version by Andrew
% Moore, which was in turn edited from those of Kristian Kersting and
% Codrina Lauth. Alex Smola contributed to the algorithmic style files.