We remark that the role of \textit{augmented} non-malleability is more subtle in the quantum secure model. In the classical setting (\cref{definition:augmented-nmcs}), the tampering functions are deterministic, and therefore the left share $X$ (before tampering) uniquely determines the entire ``view" of the left adversary after tampering. In contrast, in the quantum secure model, the entangled state that the split-state adversaries share may apriori collapse and correlate with \textit{both} post-tampered shares $X', Y'$ - thus not immediately captured by just $X$.

\begin{figure}[h]
\centering

\resizebox{12cm}{6cm}{

\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);
%\node at (1,4.5) {$R$};
%\node at (14.5,4.3) {$R'$};
\draw (4,4.5) -- (5,4.5);
\draw (5,4.5) -- (11,4.5);

\draw (3.5,5.5) -- (5,5.5);
\draw (5,5.5) -- (11,5.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
\node at (14.5,4.7) {$R$};
\node at (14.6,4.1) {$E'_2$};

%\node at (1.5,1.5) {$S$};
%\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
%\draw (3,-0.5) rectangle (4.5,3.5);
\node at (12.5,5.3) {$\nmext$};

%\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (4.78,-0.8) -- (4.78,6.5);
\draw [dashed] (9.7,-0.8) -- (9.7,6.5);
%\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (14.3,-0.8) -- (14.3,6.5);

\node at (6.8,1.6) {$\ket{\psi}_{W_1W_2}$};
\node at (4.64,-0.8) {$\sigma$};
\node at (9.5,-0.8) {$\hat{\rho}$};
%\node at (10.2,-0.8) {${\rho}$};
\node at (14.13,-0.8) {$\rho$};

\node at (3.1,3) {$X$};
\node at (7.8,3) {$X'$};
\draw (3,2.8) -- (6.3,2.8);
%\draw (7,2.8) -- (8.5,2.8);
%\draw (9.5,2.8) -- (11,2.8);
\draw (7.3,2.8) -- (11,2.8);
\node at (14.5,2.6) {$R'$};
\draw (14,2.4) -- (15,2.4);

\node at (3.1,0.4) {$Y$};
\node at (7.8,0.0) {$Y'$};
\draw (3,0.2) -- (6.3,0.2);
%\draw (7,0.2) -- (8.5,0.2);
%\draw (9.5,0.2) -- (11,0.2);
\draw (7.3,0.2) -- (11,0.2);
\draw (3.5,2.8) -- (3.5,5.5);
\draw (4,0.2) -- (4,4.5);

%\draw (4,0.2) -- (4,4.5);
%\draw (3.5,2.8) -- (3.5,5.5);
%\draw (11,4) rectangle (14,6);
%\draw (4.5,5.5) -- (5,5.5);
%\draw (5,5.5) -- (11,5.5);
%\draw (14,5) -- (14.7,5);
\draw (14,5) -- (14.7,5);

\draw (7.3,0.7) -- (8.8,0.7);
\draw (8.8,0.7) -- (8.8,3.8);
\draw (8.8,3.8) -- (14.8,3.8);

\draw (6.3,2) rectangle (7.3,3.5);
\node at (6.8,2.8) {$U$};
\draw (6.3,0) rectangle (7.3,1);
\node at (6.8,0.5) {$V$};

\node at (6.5,-0.4) {$\mathcal{A}=(U,V,\psi)$};
\draw (5.2,-0.8) rectangle (8.2,4);

\draw (5.8,1.5) ellipse (0.3cm and 1cm);
\node at (5.8,2) {$E_1$};
\draw (6,2.2) -- (6.3,2.2);
\node at (7.8,1.9) {$E'_1$};
\draw (7.3,2.2) -- (7.5,2.2);
\node at (5.8,1) {$E_2$};
\draw (6,0.7) -- (6.3,0.7);
\node at (7.7,0.9) {$E'_2$};
\draw (7.3,0.7) -- (7.6,0.7);
%\draw (9,2.8) circle (0.5);
%\node at (9,2.8) {$\mathcal{M}$};
%\draw (9,0.2) circle (0.5);
%\node at (9,0.2) {$\mathcal{M}$};

%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

%\draw (11,-0.5) rectangle (14,3.2);
%\node at (12.5,1.5) {$\cdec$};
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};
\draw (11,4) rectangle (14,6);
\draw (11,-0.5) rectangle (14,3.2);
%\node at (11.5,3.6) {$\cdec$};

%\draw (8.4,-0.6) rectangle (14.1,3.5);
\node at (12.5,1.5) {${\nmext}$};

\end{tikzpicture} }
\caption{Tampering experiment for quantum secure $2$-source non-malleable extractors.}\label{fig:splitstate5}
\end{figure}

\suppress{

\begin{figure}
\centering
\resizebox{12cm}{5cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);

\draw (2,4.3) -- (11,4.3);
\node at (1.8,4.3) {$\hat{M}$};
\node at (11.2,4.3) {$\hat{M}$};
\node at (1.8,1.5) {$M$};
\node at (11,1.5) {$M'$};

\draw (1.8,2.8) ellipse (0.3cm and 1.8cm);

%\draw (1.2,4.5) -- (5,4.5);
%\draw (5,4.5) -- (15,4.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%	\node at (14.5,4.7) {$S$};

%\node at (1.5,1.5) {$S$};
\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (3,-0.5) rectangle (4.5,3.5);
\node at (3.8,1.5) {$\enc$};

%	\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (2.78,-0.8) -- (2.78,5.5);
%	\draw [dashed] (8.3,-0.8) -- (8.3,5.5);
%	\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (10.3,-0.8) -- (10.3,5.5);

%	\node at (6.2,1.6) {$\ket{\psi}_{NM}$};
\node at (2.64,-0.8) {$\sigma$};
%	\node at (8.1,-0.8) {$\hat{\rho}$};
%	\node at (10.2,-0.8) {${\rho}$};
\node at (10.13,-0.8) {$\eta$};

\node at (4.7,3) {$X$};
\node at (8.25,3) {$X'$};

\draw (4.5,2.8) -- (6,2.8);
\draw (7,2.8) -- (8.6,2.8);
\draw (10,1.5) -- (10.7,1.5);
%	\node at (14.5,2.6) {$S'$};
%\draw (14,2.4) -- (15,2.4);

\node at (4.7,0.4) {$Z$};
\node at (8.25,0) {$Z'$};
\draw (4.5,0.2) -- (6,0.2);
\draw (7,0.2) -- (8.6,0.2);
%	\draw (9.5,0.2) -- (11,0.2);

\node at (4.7,1.8) {$Y$};
\node at (8.25,1.8) {$Y'$};
\draw  (4.5,1.6) -- (5,1.6);
\draw [dashed] (5,1.6) -- (6,1.6);
\draw (7,1.6) -- (8.6,1.6);
\draw (6,1.1) rectangle (7,1.9);
\node at (6.5,1.5) {$V$};
% \node at (7.5,1.3) {$E'_2$};
% \node at (5.5,1.4) {$E_2$};
%\draw (5.8,1.4) -- (6,1.4);
\draw (5,1.6) -- (6,1.6);

\draw (6,2.1) rectangle (7,2.9);
\node at (6.5,2.5) {$U$};
\draw (6,0.1) rectangle (7,0.9);
\node at (6.5,0.5) {$W$};

\node at (6.5,-0.4) {$\mathcal{A}=(U,V,W)$};
\draw (5,-0.8) rectangle (8,3.8);

%\draw (5.5,1.5) ellipse (0.3cm and 1.1cm);
%\node at (5.5,2.2) {$E_1$};
%\draw (5.7,2.2) -- (6,2.2);
%\node at (7.5,2.2) {$E'_1$};
%\draw (7,2.2) -- (7.2,2.2);
%\node at (5.5,0.8) {$E_3$};
%\draw (5.7,0.7) -- (6,0.7);
%\node at (7.5,0.6) {$E'_3$};
%\draw (7.0,0.7) -- (7.2,0.7);

%\draw (9,2.8) circle (0.5);
%	\node at (9,2.8) {$\mathcal{M}$};
%	\draw (9,0.2) circle (0.5);
%	\node at (9,0.2) {$\mathcal{M}$};
%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (8.6,-0.5) rectangle (10,3.2);
\node at (9.2,1.5) {$\dec$};
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture} }
\caption{$\lo^t:$ $t$-split model against unentangled quantum adversaries for $t=3$.}\label{fig:3splitstatenoentanglment}
\end{figure}

\subsubsection{Quantum Non-Malleable Codes and Augmented Non-Malleable Codes}

We now recollect the definition of NMCs from~[19] for quantum messages, referred to as \emph{quantum non-malleable codes}. For concreteness we state a definition for the $\lo^3_{(e_1,e_2,e_3)}$ adversary model, which can be generalized to any adversary model easily.

\begin{figure}[h]
\centering
\resizebox{12cm}{5cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);

\draw (2,4.3) -- (11,4.3);
\node at (1.8,4.3) {$\hat{M}$};
\node at (11.2,4.3) {$\hat{M}$};
\node at (1.8,1.5) {$M$};
\node at (11,1.5) {$M'$};

\draw (1.8,2.8) ellipse (0.3cm and 1.8cm);

%\draw (1.2,4.5) -- (5,4.5);
%\draw (5,4.5) -- (15,4.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%	\node at (14.5,4.7) {$S$};

%\node at (1.5,1.5) {$S$};
\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (3,-0.5) rectangle (4.5,3.5);
\node at (3.8,1.5) {$\enc$};

%	\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (2.78,-0.8) -- (2.78,5.5);
%	\draw [dashed] (8.3,-0.8) -- (8.3,5.5);
%	\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (10.3,-0.8) -- (10.3,5.5);

%	\node at (6.2,1.6) {$\ket{\psi}_{NM}$};
\node at (2.64,-0.8) {$\sigma$};
%	\node at (8.1,-0.8) {$\hat{\rho}$};
%	\node at (10.2,-0.8) {${\rho}$};
\node at (10.13,-0.8) {$\eta$};

\node at (4.7,3) {$X$};
\node at (8.25,3) {$X'$};

\draw (4.5,2.8) -- (6,2.8);
\draw (7,2.8) -- (8.6,2.8);
\draw (10,1.5) -- (10.7,1.5);
%	\node at (14.5,2.6) {$S'$};
%\draw (14,2.4) -- (15,2.4);

\node at (4.7,0.4) {$Z$};
\node at (8.25,0) {$Z'$};
\draw (4.5,0.2) -- (6,0.2);
\draw (7,0.2) -- (8.6,0.2);
%	\draw (9.5,0.2) -- (11,0.2);

\node at (4.7,1.8) {$Y$};
\node at (8.25,1.8) {$Y'$};
\draw  (4.5,1.6) -- (5,1.6);
\draw [dashed] (5,1.6) -- (6,1.6);
\draw (7,1.6) -- (8.6,1.6);
\draw (6,1.1) rectangle (7,1.9);
\node at (6.5,1.5) {$V$};
\node at (7.5,1.3) {$E'_2$};
\node at (5.5,1.4) {$E_2$};
\draw (5.8,1.4) -- (6,1.4);
\draw (7,1.4) -- (7.2,1.4);

\draw (6,2.1) rectangle (7,2.9);
\node at (6.5,2.5) {$U$};
\draw (6,0.1) rectangle (7,0.9);
\node at (6.5,0.5) {$W$};

\node at (6.5,-0.4) {$\mathcal{A}=(U,V,W,\ket{\psi}_{})$};
\draw (5,-0.8) rectangle (8,3.8);

\draw (5.5,1.5) ellipse (0.3cm and 1.1cm);
\node at (5.5,2.2) {$E_1$};
\draw (5.7,2.2) -- (6,2.2);
\node at (7.5,2.2) {$E'_1$};
\draw (7,2.2) -- (7.2,2.2);
\node at (5.5,0.8) {$E_3$};
\draw (5.7,0.7) -- (6,0.7);
\node at (7.5,0.6) {$E'_3$};
\draw (7.0,0.7) -- (7.2,0.7);

%\draw (9,2.8) circle (0.5);
%	\node at (9,2.8) {$\mathcal{M}$};
%	\draw (9,0.2) circle (0.5);
%	\node at (9,0.2) {$\mathcal{M}$};
%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (8.6,-0.5) rectangle (10,3.2);
\node at (9.2,1.5) {$\dec$};
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture} }
\caption{$\lo^t_{(e_1, \ldots, e_t)}:$ $t$-split tampering model with shared entanglement for $t=3$. The shared entanglement $\psi$ is stored in registers $E_1, E_2$ and $E_3$ such that $\vert E_i \vert \leq e_i$ for $i \in [3]$.}\label{fig:splitstate211d}
\end{figure}

Let $\sigma_M$ be an arbitrary state in a message register $M$ and $\sigma_{M\hat{M}}$ be its canonical purification.
Our coding scheme is given by an encoding Completely Positive Trace-Preserving (CPTP) map
$\enc : \cL( \cH_M) \to \cL(\cH_{X}\otimes \cH_Y\otimes\cH_{Z})$ and a decoding CPTP map $\dec  : \cL(\cH_{X}\otimes\cH_{Y} \otimes\cH_{Z}) \to  \cL(\cH_{M})$. Here, $\cH_{X}, \cH_{Y}, \cH_{Z}$ denote the Hilbert spaces for the three shares. The most basic property we require of this coding scheme $(\enc,\dec)$ is correctness, including preserving entanglement with external systems:
\begin{equation*}
\dec(\enc(\sigma_{M\hat{M}}))=\sigma_{M\hat{M}}.
\end{equation*}

Now, suppose we tamper with the code using a tampering adversary $\cA$ in $\lo^3_{(e_1,e_2,e_3)}$. Recall from \cref{def:lotsharedentanglement} that such adversaries are specified by three tampering maps, $U:\cL(\cH_X\otimes \cH_{E_1})\to\cL(\cH_{X'}\otimes\cH_{E'_1})$, $V:\cL(\cH_Y\otimes \cH_{E_2})\to\cL(\cH_{Y'}\otimes \cH_{E'_2})$ and $W:\cL(\cH_Z\otimes \cH_{E_3})\to\cL(\cH_{Z'}\otimes \cH_{E'_3})$ along with a quantum state $\ket\psi_{E_1 E_2E_3}$ such that $\vert E_i \vert \leq e_i, \ \forall i \in [3]$ which captures the pre-shared entanglement between the non-communicating quantum tampering adversaries. After the tampering channel, the decoding procedure $\dec$ is applied to the corrupted codeword $\tau_{X' Y'Z'}$ and stored in register $M'$.
\cref{fig:splitstate211d} presents a diagram of this tampering model.
\begin{equation*}
\eta = \dec( ( U \otimes V \otimes W)  \left(\enc( \sigma_{M \hat{M}}) \otimes \ketbra{\psi} \right)  )
\end{equation*}
be the final state after applying the tampering adversary $\cA$ followed by the decoding procedure. The non-malleability of the coding scheme $(\enc,\dec)$ is defined as follows.

\begin{definition}[Quantum Non-Malleable Code against $\lo^3_{(e_1,e_2,e_3)}$~[19]]\label{def:qnmcodesfinaldef}
See \cref{fig:splitstate211d} for the tampering experiment. We say that the coding scheme
$(\enc, \dec)$ is an \emph{$\eps$-secure quantum non-malleable code} against $\lo^3_{(e_1,e_2,e_3)}$ if for every $\lo^3_{(e_1,e_2,e_3)}$ tampering adversary $\cA=(U,V,W,\ket\psi_{E_1 E_2E_3})$ and for every quantum message $\sigma_M$ (with canonical purification $\sigma_{M\hat{M}}$) it holds that
\begin{equation}\label{eq:splitnmc}
\eta_{M'\hat{M}} \approx_\eps p_{\cA} \sigma_{M \hat{M}}+(1-p_{\cA})\gamma^{\cA}_{M'}\otimes \sigma_{\hat{M}},
\end{equation}
where $p_{\cA}\in[0,1]$ and $\gamma^{\cA}_{M'}$ depend only on the tampering adversary $\cA=(U,V,W,\ket\psi_{E_1 E_2E_3})$.
\end{definition}

An important restriction to the definition above is known as ``average-case" non-malleability:

\begin{remark}
[[19]] If \cref{eq:splitnmc} is only guaranteed to hold if $\sigma_{M}$ is the maximally mixed state, then $(\Enc, \Dec)$ is referred to as an \emph{average-case $\eps$-secure quantum non-malleable code}.
\end{remark}

In our reductions, we require guarantees on the correlations between the recovered message, and the registers of individual split-state adversaries (even after tampering). We introduce the following notion of augmented quantum non-malleable codes, in an analog to its classical counterpart (\cref{definition:augmented-nmcs}).

\begin{definition}[Augmented Quantum Non-Malleable Code against $\lo^3_{(e_1,e_2,e_3)}$]\label{def:qnmcodesfinaldefaug}
See \cref{fig:splitstate211d} for the tampering experiment. We say that the coding scheme
$(\enc, \dec)$ is an \emph{$\eps$-secure augmented quantum non-malleable code} against $\lo^3_{(e_1,e_2,e_3)}$ if there exists $i \in [3]$ such that for every $\lo^3_{(e_1,e_2,e_3)}$ tampering adversary $\cA=(U,V,W,\ket\psi_{E_1 E_2E_3})$ and message $\sigma_M$ (with canonical purification $\sigma_{M\hat{M}}$), it holds that
\begin{equation}\label{eq:splitnmcaug}
\eta_{M'\hat{M}E'_i} \approx_\eps p_{\cA} \sigma_{M \hat{M}} \otimes \zeta^{\cA}_{E'_i} +(1-p_{\cA})\gamma^{\cA}_{M'E'_i}\otimes \sigma_{\hat{M}},
\end{equation}
where $p_{\cA}\in[0,1]$, $\gamma^{\cA}_{M'E'_i}$ and $\zeta^{\cA}_{E'_i}$ depend only on the tampering adversary $\cA=(U,V,W,\ket\psi_{E_1 E_2E_3})$.
\end{definition}

In other words, the $i$th adversaries ``view" $E'_i$ is simulatable jointly with the message.

\subsubsection{Quantum Tamper-Detection Codes}

Finally, we formally define the notion of quantum tamper-detection codes. Following the previous subsection, for concreteness we present an explicit definition for $\lo^t_{(e_1,e_2, \ldots, e_t)}$ tampering adversaries with $t=3$, which can be easily generalized to the different tampering models of \cref{subsection:formal-tampering}.

\begin{definition}[Quantum Tamper-Detection Code against $\lo^3_{(e_1,e_2, e_3)}$]\label{def:qtdcodesfinaldef}
See \cref{fig:splitstate211d} for the tampering experiment. We say that the coding scheme
$(\enc, \dec)$ is an \emph{$\eps$-secure quantum tamper-detection code} against $\lo^3_{(e_1,e_2, e_3)}$ if for every $\lo^3_{(e_1,e_2, e_3)}$ adversary $\cA=(U,V,W,\ket\psi_{E_1 E_2E_3})$ and for every quantum message $\sigma_M$ (with canonical purification $\sigma_{M\hat{M}}$)
it holds that
\begin{equation}\label{eq:splittdc}
\eta_{M'\hat{M}} \approx_\eps p_{\cA} \sigma_{M \hat{M}}+(1-p_{\cA}) \bot_{M'}\otimes \sigma_{\hat{M}},
\end{equation}
where $p_{\cA}\in[0,1]$ depend only on the tampering adversary $\cA$ and $ \bot_{M'}$ denotes a special abort symbol stored in register $M'$ to denote tamper detection.
\end{definition}

\subsection{Secret Sharing Schemes and their Variants}
\label{subsection:prelim-ss}

In this subsection we present basic definitions of secret sharing schemes, in addition to known constructions in the literature that we require to instantiate our compilers. We begin in \cref{subsubsection:prelim-threshold-ss} by introducing threshold secret sharing, proceeded by leakage-resilient secret sharing in \Cref{subsubsection:prelim-lrss}, and non-malleable secret sharing in \Cref{subsubsection:prelim-nmss}. Finally, in \Cref{subsubsection:prelim-tamper-detecting-ss} we formally introduce the tamper detecting secret sharing schemes we construct in this work.

\subsubsection{Threshold Secret Sharing Schemes}
\label{subsubsection:prelim-threshold-ss}

Informally, in a $t$-out-of-$p$ secret sharing scheme, any $t$ honest shares suffice to reconstruct the secret, but no $t-1$ shares offer any information about it.

\begin{definition}
[$(p, t, \epspriv, \epsilon_c)$-Secret Sharing Scheme]\label{definition:secret-sharing} Let $\mathcal{M}$ be a finite set of secrets, where $|\mathcal{M}| \geq 2$. Let $[p] = \{1, 2, \cdots , p\}$ be a set of identities (indices) of $p$ parties. A sharing channel $\Enc$ with domain of secrets $\mathcal{M}$ is a $(p, t, \epspriv, \epsilon_c)$ \emph{threshold secret sharing scheme} if the following two properties hold:
\begin{enumerate}
\item \textbf{Correctness}: the secret can be reconstructed by any set of parties $T\subset [p], |T|\geq t$. That is, for every such $T$, there exists a reconstruction channel $\Dec_T$ such that
\begin{equation}
\forall m\in \mathcal{M}: \text{ } \mathbb{P}[\Dec_T\circ \Enc(m)_T\neq m]\leq \epsilon_c
\end{equation}
\item \textbf{Statistical Privacy}: Any collusion of $|T|\leq t-1$ parties has “almost” no information about the underlying secret. That is, for every distinguisher $D$ with binary output:
\begin{equation}
\forall m_0, m_1\in \mathcal{M}: \text{ } |\mathbb{P}[D(\Enc(m_0)_T)=1] - \mathbb{P}[D(\Enc(m_1)_T)=1]|\leq \epspriv
\end{equation}
\end{enumerate}
\end{definition}

We point out that we use the same syntactic definition of secret sharing for schemes which hide classical messages into classical or quantum ciphers. However, when the cipher is classical, we refer to the encoding/decoding channels as $\share$ and $\rec$ (reconstruction) functions, as opposed to quantum channels $(\Enc, \Dec)$. The block-length of the secret sharing scheme is the total qubit $+$ bit-length of all the shares, and its rate as the ratio of message length (in bits) to block-length.

To instantiate our constructions, we use Shamir’s  standard threshold secret sharing scheme:

\begin{fact}
[[70]] For any number of parties $p$ and threshold $t$ such that $t\leq p$, there exists a $t$-out-of-$p$ secret sharing scheme $(\share, \rec)$ for classical messages of length $b$ with share size at most $\max(p, b)$, where both the sharing and reconstruction procedures run in time poly$(p, b)$.
\end{fact}

\subsubsection{Leakage-Resilient Secret Sharing Schemes}
\label{subsubsection:prelim-lrss}

Integral in our constructions are classical secret sharing schemes which offer privacy guarantees even if unauthorized subsets are allowed to leak information about their shares to each other in an attempt to distinguish the message. Moreover, we depart from standard classical leakage models in that the leaked information itself could be a quantum state, even if the shares are classical. The definition of leakage-resilient secret sharing formalizes this idea as follows:

\begin{definition}
[Leakage-Resilient Secret Sharing]\label{def:lrss} Let $(\share, \rec)$ be a secret sharing scheme with randomized sharing function $\Share:\mathcal{M}\rightarrow \{\{0, 1\}^{l'}\}^p$, and let $\mathcal{F}$ be a family of leakage channels. Then $\share$ is said to be $(\mathcal{F}, \epsilon_{lr})$ leakage-resilient if, for every channel $\Lambda\in \mathcal{F}$,
\begin{equation}
\forall m_0, m_1\in \mathcal{M}: \text{ } \Lambda(\Share(m_0)) \approx_{\epsilon_{lr}}  \Lambda(\Share(m_1))
\end{equation}
\end{definition}

As an example, the standard local leakage model in the context of classical secret sharing schemes allows bounded leakage queries $\{f_i: \{0, 1\}^{l'} \rightarrow \{0, 1\}^\mu\}_{i\in K}$, on each share corresponding to an arbitrary set of indices $K\subset [n]$, and further allows full share queries corresponding to an unauthorised subset $T\subset [n]$:

\begin{equation}
\mathsf{Leak}(\share(m)) = \share(m)_T, \{f_i(\share(m)_i)\}_{i\in K}.
\end{equation}

In our constructions, we unfortunately require a slight modification to this setting, where the leakage parties $K$ are an unauthorized subset, but are allowed to \textit{jointly} leak a small quantum state (dependent on their shares) to $T$. We formally introduce this model as follows:

\begin{definition}
[Quantum $k$-Local Leakage Model]\label{def:k-local-leakage}
For any integer sizes $p, t, k$ and leakage length (in qubits) $\mu$, we define the $(p, t, k, \mu)$-local leakage model to be the collection of channels specified by
\begin{equation}
\mathcal{F}_{k, \mu}^{p, t} =\bigg\{ (T, K, \Lambda): T, K\subset [p],|T|< t, |K|\leq k, \text{ and }\Lambda:\{0, 1\}^{l'\cdot |K|}\rightarrow \cL(\mathcal{H})\bigg\},
\end{equation}
\noindent where $\log \dim(\mathcal{H}) = \mu$. A leakage query $(T, K, \Lambda)\in \mathcal{F}_{k, \mu}^{p, t}$ on a secret $m$ is the density matrix:
\begin{equation}
(\mathbb{I}_{T}\otimes \Lambda_K)(\Share(m)_{T \cup K})
\end{equation}
\end{definition}

\noindent In other words, the parties in $K$ perform a quantum channel on their (classical) shares and send the $\mu$ qubit output state to $T$. To the extent of our knowledge, in the literature we do not know of $\lrss$ constructions in this model (even with classical leakage). However, in \Cref{section:lrss} we show that simple modifications to a construction of $\lrss$ against local leakage by [30] provides such guarantees.

\begin{theorem}[\Cref{theorem:lrss-local-leakage}, restatement]\label{theorem:lrss-local-leakage-prelim}
For every $\mu, k, t, p, l\in \mathbb{N}$ such that $k<t, t+k\leq p,$ and $p\leq l$, there exists an $(p, t, 0, 0)$ threshold secret sharing scheme on messages of $l$ bits and shares of size $l+\mu +o(l, \mu)$ bits, which is perfectly correct and private and $p\cdot 2^{-\Tilde{\Omega}(\sqrt[3]{\frac{l+\mu}{p}})}$ leakage-resilient against $\mathcal{F}_{k, \mu}^{p, t}$.
\end{theorem}

\subsubsection{Non-Malleable Secret Sharing Schemes}
\label{subsubsection:prelim-nmss}

[45] introduced the notion of a non-malleable secret sharing scheme (NMSS). An NMSS is a secret sharing scheme which is robust to certain types of tampering on the shares.

\begin{definition}
[$(p, t, \epspriv, \epsilon_c, \epsilon_\NM)$ Non-Malleable Secret Sharing Scheme] Let $(\Enc, \Dec)$ be a $(p, t, \epspriv, \epsilon_c)$ secret sharing scheme, and let $\mathcal{F}$ be a family of tampering channels. Then, we refer to $(\Enc, \Dec)$ as a $(p, t, \epspriv, \epsilon_c, \epsilon_\NM)$ \emph{non-malleable secret sharing scheme} against $\mathcal{F}$ if, for all $\Lambda\in \mathcal{F}$ and authorized subset $T\subset [p]$ of size $|T|\geq t$, there exists $p_\Lambda\in [0, 1]$ and a distribution $\mathcal{D}_\Lambda$ such that
\begin{equation}
\forall  m\in \mathcal{M}, \quad \Dec_T\circ \Lambda\circ \Enc(m) \approx_{\epsilon_\NM} p_\Lambda\cdot m + (1-p_\Lambda)\cdot \mathcal{D}_\Lambda
\end{equation}
\end{definition}

In other words, the recovered secret after tampering is a convex combination of the original secret, or a fixed distribution over secrets. We leverage a construction of non-malleable secret sharing schemes against \textit{joint tampering functions} by [45].

\begin{definition}
[Joint Tampering Functions $\mathcal{F}_{p, t}^{\text{joint}}$]\label{definitions:joint-tampering} For any $t$-out-of-$p$ secret sharing scheme, the adversary chooses any $t$-out-of-$p$ shares to obtain an authorized set $T$, partitions the set $T = A\cup B$ into any two non-empty disjoint subsets which have different cardinalities, and jointly tampers with shares in each of the two subsets arbitrarily and independently using deterministic functions $f_A, f_B$.
\end{definition}

\begin{theorem}
[[45]]\label{theorem:nmss-goyal} For every number of parties $p$, threshold $t\geq 3$, and sufficiently large block-length $b$, there exists a $(p, t, 0, 0,  2^{-b^{\Omega(1)}})-\nmss$ against $\mathcal{F}_{p, t}^{\text{joint}}$ of rate $p^{-O(1)}$.
\end{theorem}

\subsubsection{Tamper Detecting Secret Sharing Schemes}
\label{subsubsection:prelim-tamper-detecting-ss}

Below we formalize two tamper detection properties for the secret sharing schemes that we consider in this section. The first of the two is known as ``weak" tamper detection, and informally can be understood as the ability to \textit{either} recover the message or reject after tampering, with high probability. However, the probability that either of these two events occurs may depend on $m$:

\begin{definition}[Weak Tamper-Detecting Secret Sharing Schemes]\label{def:weak-td}
Let a family of CPTP maps $(\Enc, \Dec)$ be a $(p, t, \epspriv, \epsilon_c)$ secret sharing scheme over $k$ bit messages and $\mathcal{F}$ a family of tampering channels. We refer to $(\Enc, \Dec)$ as $(\mathcal{F}, r, \epsilon_\td)$ \emph{weak tamper-detecting} if, for every subset $R\subset [p]$ of size $|R|\geq r$ and tampering channel $\Lambda\in \mathcal{F}$,
\begin{equation}
\forall m\in \{0, 1\}^k, \quad  \mathbb{P}[\Dec_R\circ\Lambda\circ \Enc(m)\notin \{m, \bot\}]\leq \epsilon_\td \text{ }
\end{equation}
\end{definition}

Note that in the above, we implicitly consider \textit{ramp} secret sharing schemes, where the threshold for privacy, reconstruction under honest shares, and reconstruction under tampered shares, are different. In a (generic) tamper-detecting secret sharing scheme, we stipulate that the distribution over the recovered message is near convex combination of the original $m$ and $\bot$, which doesn't depend on $m$:

\begin{definition}[Tamper-Detecting Ramp Secret Sharing Schemes]
Let a family of CPTP maps $(\Enc, \Dec)$ be a $(p, t, \epspriv, \epsilon_c)$ secret sharing scheme over $k$ bit messages and $\mathcal{F}$ a family of tampering channels. We refer to $(\Enc, \Dec)$ as $(\mathcal{F}, r, \epsilon_\td)$ \emph{tamper-detecting} if, for every subset $R\subset [p]$ of size $|R|\geq r$ and tampering channel $\Lambda\in \mathcal{F}$, there exists a constant $p_\Lambda\in [0, 1]$ such that
\begin{equation}
\forall m\in \{0, 1\}^k, \quad  \Dec_R\circ\Lambda\circ \Enc(m) \approx_{\epsilon_\td} p_\Lambda \cdot m + (1-p_\Lambda)\cdot \bot\text{ }
\end{equation}
\end{definition}

\subsection{Bipartite and Multipartite \texorpdfstring{$\locc$}{LOCC} Data Hiding Schemes}
\label{subsection:prelim-data-hiding}

%\subsection{$\locc$ Data Hiding Schemes}

In this subsection we present basic definitions of multi-partite quantum measurements restricted to local operations and quantum communication, as well as formal definitions of quantum data hiding schemes.

\subsubsection{Bipartite Data Hiding}

\begin{definition}\label{definition:locc-distance}
Let $\rho, \sigma$ be two apriori equiprobable bipartite mixed states, and define the distance $\|\rho-\sigma\|_{\locc}  = 4\cdot (p-\frac{1}{2})$, where $p$ is the probability of correctly distinguishing the states, maximised over all decision procedures that can be implemented using only local operations and classical communication ($\locc$).
\end{definition}

\begin{remark}
Notions of distance based on restricted classes of measurements define induced norms on operators (below) only when the set of measurements $\mathbb{M}$ is a closed, convex subset of the operator interval $\{M: 0\leq M\leq \mathbb{I}\}$ containing $\mathbb{I}$ and such that $\mathbb{I}-M\in \mathbb{M}$. See [65] for a detailed description.
\begin{equation}
\|X\|_{\mathbb{M}} = \max_{M\in \mathbb{M}}\Tr (2M-\mathbb{I})X
\end{equation}
\end{remark}

The set of $\locc$ measurements is \emph{not} topologically closed [32], and therefore the distance in \Cref{definition:locc-distance} is not a norm. Nevertheless, it does satisfy the triangle inequality.

\begin{definition}[$\locc$ Data Hiding Schemes [72, 52]]\label{definition:locc-datahiding}
A bipartite $(\epsilon, \delta)$-$\locc$ data hiding scheme is a pair of quantum channels $(\Enc, \Dec)$ where $\Enc:\{0, 1\}^k\rightarrow \cL(\mathcal{H}\otimes \mathcal{H})$ and $\Dec:\cL(\mathcal{H}\otimes \mathcal{H})\rightarrow \{0, 1\}^k$ satisfying:

\begin{enumerate}
\item \textbf{Correctness}: $\forall m\in \{0, 1\}^k:\mathbb{P}\big[\Dec\circ \Enc(m) \neq m\big] \leq \delta$.

\item \textbf{Security}: $\forall m_0, m_1\in \{0, 1\}^k:$ $\|\Enc(m_0)-\Enc(m_1)\|_{\locc}\leq \epsilon$
\end{enumerate}
\end{definition}

To instantiate our code construction, we use two pre-existing constructions of bipartite data hiding schemes. The first of which is an inefficient, high-rate result by [52]:

\begin{theorem}
For every sufficiently large integer $n$, there exists a bipartite $(2^{-\Omega(\frac{n}{\log n})}, 2^{-\Omega(\frac{n}{\log n})})$-$\locc$ data hiding scheme encoding $n/2-o(n)$ bits into $n$ qubits.
\end{theorem}

And the second is an efficient construction by [41], which furthermore is \textit{separable}.

\begin{theorem}
For every $k, \lambda = \Omega(\log k)\in \mathbb{N}$, there exists a 2-out-of-2 $(2^{-\Omega(\lambda)}, 2^{-\Omega(\lambda)})$ $\locc$ data hiding scheme encoding $k$ bits into $n = 2\cdot k\cdot \lambda^2$ qubits. Moreover, the data hiding states are separable states.
\end{theorem}

\suppress{
Since the parameters in their construction are not immediately spelled out, we pick parameters as follows. To encode a single bit in their hiding scheme, we use a bipartite system comprised of $K=\lambda$ copies of the $\log d = \lambda$ qubit data hiding scheme, with recovery and hiding error $2^{-\Omega(\lambda)}$. To encode $k$ bits, we repeat the protocol independently $k$ times. Since the scheme is separable, the error is additive [37].}

\subsubsection{Data Hiding with an Access Structure}

The study of multi-partite data hiding schemes, endowed with some access structure $\mathcal{A}$, can be traced to [41, 35, 51]. Recall an access structure $\mathcal{A}$ is simply a family of subsets of $[p]$, where $p$ denotes the number of parties/registers in the data hiding scheme. A subset of parties $T\in \mathcal{A}$ implies that the parties in $T$, using quantum communication between each other, can recover the secret.

However, if $T\notin \mathcal{A}$, then the data hiding scheme offers a notion of privacy which strengthens the standard secret-sharing definition: no unauthorized party $T$ can learn information about the secret even if they are allowed arbitrary classical communication with their complement $[p]\setminus T$, in addition to quantum communication within $T$. Here, the parties in $[p]\setminus T$ are restricted to $\locc$ themselves.

\begin{definition}
Fix a number $p$ of parties and a subset $T\subset [p]$ of them. We refer to the set of CPTP channels $\locc_T^p$ as the set of operations implementable using local operations and quantum communication within $T$, as well as local operations and classical communication between $T$, and each individual $u\in [p]\setminus T$. When no quantum communication is allowed, we refer to the set of channels as $\locc^p$.
\end{definition}

Following \Cref{section:4ss-nmc-locc}, given any two apriori equiprobable density matrices $\rho, \sigma$ supported on an $p$ partite Hilbert space, we denote $\frac{1}{2}\|\rho-\sigma \|_{\locc_T^p}$ as the optimal bias in distinguishing between the two using binary outcome distinguishers $\Lambda\in \locc_T^p$.

\begin{definition}
[$(p, t, \epsilon_\locc, \epsilon_c)$-$\locc$ Secret Sharing Scheme]\label{definition:data-hiding-secret-sharing} A pair of channels $(\Enc, \Dec)$ is an $(p, t, \epsilon_\locc, \epsilon_c)$-$\locc$ secret sharing scheme if it satisfies
\begin{enumerate}
\item \textbf{Correctness}: The secret can be reconstructed by any set of parties $T\subset [p], |T|\geq t$ using quantum communication within $T$. That is, for every $T$ there exists a reconstruction channel $\Dec_T$ such that for all messages $m$:
\begin{equation}
\mathbb{P}[\Dec_T\circ \Enc_T(m)\neq m]\leq \epsilon_c
\end{equation}

\item \textbf{Security}: Any collusion of $|T|\leq t-1$ parties has ``almost" no information about the underlying secret, even if the remaining $[p]\setminus T$ parties can aid them using arbitrary classical communication. That is, for every pair of messages $m_0, m_1$,
\begin{equation}
\|\Enc(m_0) - \Enc(m_1)\|_{\locc_T^p} \leq \epsilon_\locc.
\end{equation}
\end{enumerate}
\end{definition}

\newpage
\section{From Non-Malleability to Tamper Detection against \texorpdfstring{$\lo$}{Lo}}
\label{section:tsplit-td}

We dedicate this section to our two black-box reductions that construct tamper-detection codes (TDCs) from non-malleable codes (NMCs) in the split state model. We refer the reader to \cref{subsection:formal-tampering} for formal definitions of the relevant tampering models, namely the unentangled $t$-split-state model $\lo^t$, and the bounded storage model $\lo^t_a$. Our first result shows that any non-malleable code in the unentangled split-state model implies a tamper-detection code in the unentangled split-state model, but with one extra share.

\begin{theorem}\label{theorem:tsplit-reduction}
Let the coding scheme $(\Enc^t, \Dec^t)$ be a quantum NMC against $\lo^t$, with message length $k$ qubits, blocklength $n$, and error $\epsilon$. Then, for every $0 < \lambda < k$, there exists a quantum TDC against tampering adversaries $\lo^{t+1}$ of message length $k-\lambda$, blocklength $n+\lambda$, and error $\epsilon+  2^{1-\lambda}$.
\end{theorem}

Our second result shows the reduction above can be made robust against adversaries with a bounded amount of entanglement, highlighting that tamper detection is not solely an artifact of the unentangled model. The challenge in extending our ideas lies in the fact that quantum NMCs are, a priori, not composable. Their definition offers no guarantees on any entanglement that the adversaries may have with the quantum message, both before or after tampering. Consequently, adversaries with shared entanglement may correlate their attack on the additional $(t+1)$st share, with their attack on the NMC.

To address this challenge, we introduce the concept of an ``augmented" quantum NMC, drawing an analogy to their classical counterparts. In a standard split-state NMC, the decoded message is either perfectly recovered or entirely fixed. In an augmented NMC, the decoded message, in conjunction with the left share, is either recovered and remains independent or are jointly fixed. We formalized this notion in the quantum setting, accounting for any pre-shared entanglement, in \cref{def:qnmcodesfinaldefaug}. We can now state our reduction in the ``bounded storage model", denoted as $\lo^t_{(e_1, \cdots, e_t)}$.

\begin{theorem}\label{theorem:tsplit-bounded-storage}
Let the coding scheme $(\Enc^t, \Dec^t)$ be an quantum NMC against $\lo^t_{(e_1,e_2, \ldots, e_t)}$, with message length $k$ qubits, blocklength $n$, and error $\epsilon$, which is \emph{augmented} at the first share.

Then, for every $0\leq \lambda < k$ and $0\leq a\leq \min(\lambda, e_1)$ there exists a quantum TDC against $\lo^{(t+1)}_{(e_1-a, \ldots, e_t, e_{t+1}=a)}$, of message length $k-\lambda$, blocklength $n+\lambda$, and error $\epsilon+2^{1+a-\lambda}$.
\end{theorem}

In particular, if $(\Enc^t, \Dec^t)$ is secure against arbitrary pre-shared entanglement $\lo^t_*$, then the result is secure against $\lo^t_{(*, *, \cdots, a)}$. We defer instantiations of the reductions above, as well as explicit constructions of the augmented quantum NMCs to \Cref{section:2ss-nm}.

\subsection{Quantum Tamper-Detection Codes against \texorpdfstring{$\lo$}{Lo}}
\label{subsection:reduction}

Let the coding scheme $(\Enc^t, \Dec^t)$ be a quantum non-malleable code (NMC) against $\lo^t$, with message length $k$ qubits, blocklength $n$, and error $\epsilon$. In \cref{alg:tamper-detection}, for every integer $0 < \lambda < k$, we define a quantum tamper-detection code $(\Enc, \Dec)$ against $\lo^{t+1}$:

%Then, for every $0 < \lambda < k$, there exists a quantum tamper detection code (TDC) against $\lo^{t+1}$ with a message length of $k-\lambda$, codeword length of $n+\lambda$, rate of $(k-\lambda)/n$, and error of $\epsilon+2^{-\lambda}$. The encoding scheme, denoted as $\enc$, for the quantum TDC against $\lo^{t+1}$ is provided in \cref{alg:tamper-detection}.

\begin{algorithm}[H]
\setstretch{1.35}
\caption{$\Enc$: A quantum TDC defined on $t+1$ registers.}
\label{alg:tamper-detection}
\KwInput{Any input state $\sigma_{M}$ (with canonical purification register $\hat{M}$) such that $\vert M \vert =k- \lambda$ and an integer $\lambda$.}
%\KwOutput{The product state $\rho^m_L\otimes \rho^r_R$ for some $m\in \{0, 1\}$ correlated with $b$}

\begin{algorithmic}[1]

\State Prepare $\lambda$ EPR pairs, $\Phi^{\otimes \lambda} \equiv \Phi_{E \hat{E}}$, on a bipartite register $E, \hat{E}$.

\item Encode $\sigma_M$ and the EPR halves in register $E$ into the quantum NMC, $\Enc^t$.

\item Output the $t$-splits, and the remaining EPR halves in $\hat{E}$ in the $(t+1)$st split.
\begin{equation}
\Enc(\sigma_{M}) = \left((\Enc^t)_{ME}\otimes \mathbb{I}_{\hat{E}}\right) (\sigma_M\otimes \Phi^{}_{E\hat{E}})
\end{equation}
\end{algorithmic}

\end{algorithm}

\begin{algorithm}[H]
\setstretch{1.35}
\caption{$\Dec$.}
\label{alg:tamper-detection-decoder}
\KwInput{Any code-state $\Lambda\circ \Enc(\sigma_{M})$ on $(t+1)$ shares, tampered by a channel $\Lambda\in \lo^{t+1}$.}
%\KwOutput{The product state $\rho^m_L\otimes \rho^r_R$ for some $m\in \{0, 1\}$ correlated with $b$}

\begin{algorithmic}[1]

\State Decode the quantum NMC in the first $t$ shares using $\Dec^t$, resulting in registers $M'$ and $E'$.

\item  Perform an $\epr$ test on registers $E'\hat{E}$. This entails a binary outcome measurement with two possible outcomes: ${\Pi = \Phi_{E\hat{E}}, \Bar{\Pi} = \id_{E \hat{E}} - \Phi_{E\hat{E}}}$.

\item An acceptance decision is made if the outcome is $\Pi = \Phi_{E\hat{E}}$. In this case, the operation $\swap$ (stands for 'Replace') outputs the register $M'$.

\item If the outcome is $ \bar{\Pi}$, the operation $\swap$ outputs a special symbol $\bot$ in register $M'$.
\end{algorithmic}

\end{algorithm}

\subsubsection{Proof of~\cref{theorem:tsplit-reduction}}

Let us denote the tampering adversary $\lo^{(t+1)}$ as $\mathcal{A} = (\Lambda_1, \Lambda_2, \ldots, \Lambda_{t+1})$, and its restriction to the first $t$ shares as $\mathcal{A}^t = (\Lambda_1, \Lambda_2, \ldots, \Lambda_{t})$. We depict the tampering process of  $\mathcal{A}$ on our code $(\enc , \dec)$ in  \cref{fig:tsplitstatenoentanglment,fig:t1splitstatenoentanglment}. These two figures describe the same tampering experiment, but only differ in that in \cref{fig:t1splitstatenoentanglment}, we have delayed the action of $\Lambda_{t+1}$ to introduce an intermediate state $\tau$. $\tau$ represents the state of the system after $\mathcal{A}^t$ has tampered with the first $t$ shares and we have decoded the non-malleable code, but before the action of $\Lambda_{t+1}$.

%Consider the tampering processes depicted in \cref{fig:tsplitstatenoentanglment,fig:t1splitstatenoentanglment}. \Cref{fig:tsplitstatenoentanglment} illustrates the tampering process of $(\enc , \dec)$ against $\mathcal{A}$. It's important to note that both tampering processes are equivalent, with the only difference being that

\begin{figure}[H]
\centering
\resizebox{12cm}{5cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);

\draw (2,4.3) -- (12.5,4.3);
\node at (1.8,4.3) {$\hat{M}$};
\node at (12.7,4.3) {$\hat{M}$};
\node at (1.8,1.5) {$M$};

\node at (10.5,2.7) {$M'$};
\draw (11.2,1.5) rectangle (12,3.5);
\node at (11.6,2.5) {$\swap$};
\draw (11.6,0.5) -- (11.6,1.5);
\draw (12,2.5) -- (12.4,2.5);
\node at (12.5,2.7) {$M'$};
\node at (10.8,0.3) {$O$};
\node at (12.5,-1.8) {$\eta$};
\draw [dashed] (12.3,-1.8) -- (12.3,5.5);

\draw (1.8,2.8) ellipse (0.3cm and 1.8cm);
\draw (2.7,-0.2) ellipse (0.15cm and 1cm);
\node at (2.7,0.5) {$E$};
\node at (2.7,-0.7) {$\hat{E}$};

\draw (2.8,0.6) -- (3,0.6);
\draw (2.8,-0.7) -- (6,-0.7);
\draw (7,-0.7) -- (9.8,-0.7);
%\draw (5,4.5) -- (15,4.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%	\node at (14.5,4.7) {$S$};

%\node at (1.5,1.5) {$S$};
\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (3,-0.5) rectangle (4.5,3.5);
\node at (3.8,1.5) {$\enc^t$};

%	\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (2.28,-1.8) -- (2.28,5.5);
%	\draw [dashed] (8.3,-0.8) -- (8.3,5.5);
%	\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (11,-1.8) -- (11,5.5);

%	\node at (6.2,1.6) {$\ket{\psi}_{NM}$};
\node at (2.14,-1.8) {$\sigma$};
%	\node at (8.1,-0.8) {$\hat{\rho}$};
%	\node at (10.2,-0.8) {${\rho}$};
\node at (11.1,-1.8) {$\nu$};

\node at (4.7,3) {$X$};
\node at (8.25,3) {$X'$};

\draw (4.5,2.8) -- (6,2.8);
\draw (7,2.8) -- (8.6,2.8);
\draw (9.5,2.5) -- (11.2,2.5);
\draw (9.5,1) -- (9.8,1);
\node at (9.65,0.8) {$E'$};
%\draw (14,2.4) -- (15,2.4);

\node at (4.7,0.4) {$X_t$};
\node at (8.25,0) {$X_t'$};
\draw (4.5,0.2) -- (6,0.2);
\draw (7,0.2) -- (8.6,0.2);
%	\draw (9.5,0.2) -- (11,0.2);

% \node at (4.7,1.8) {$X_2$};
%\node at (8.25,1.8) {$X_2'$};
%\draw  (4.5,1.6) -- (5,1.6);
\draw [dashed] (6.5,1.2) -- (6.5,1.8);
\draw [dashed] (4.7,1) -- (4.7,2.5);
\draw [dashed] (8.3,1) -- (8.3,2.5);
% \draw (7,1.6) -- (8.6,1.6);
%\draw (6,1.1) rectangle (7,1.9);
\draw (6,-0.1) rectangle (7,-0.9);
% \node at (6.5,1.5) {$V$};
% \node at (7.5,1.3) {$E'_2$};
% \node at (5.5,1.4) {$E_2$};
%\draw (5.8,1.4) -- (6,1.4);
%\draw (5,1.6) -- (6,1.6);

\draw (6,2.1) rectangle (7,2.9);
\node at (6.5,2.5) {$\Lambda_1$};
\draw (6,0.1) rectangle (7,0.9);
\node at (6.5,0.5) {$\Lambda_t$};
\node at (6.5,-0.5) {$\Lambda_{t+1}$};

\node at (6.5,-1.4) {$\mathcal{A}=(\Lambda_1, \cdots, \Lambda_{t+1})$};
\draw (4.9,-2) rectangle (8.1,3.8);

%\draw (5.5,1.5) ellipse (0.3cm and 1.1cm);
%\node at (5.5,2.2) {$E_1$};
%\draw (5.7,2.2) -- (6,2.2);
%\node at (7.5,2.2) {$E'_1$};
%\draw (7,2.2) -- (7.2,2.2);
%\node at (5.5,0.8) {$E_3$};
%\draw (5.7,0.7) -- (6,0.7);
%\node at (7.5,0.6) {$E'_3$};
%\draw (7.0,0.7) -- (7.2,0.7);

%\draw (9,2.8) circle (0.5);
%	\node at (9,2.8) {$\mathcal{M}$};
%	\draw (9,0.2) circle (0.5);
%	\node at (9,0.2) {$\mathcal{M}$};
%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (8.6,-0.5) rectangle (9.5,3.2);
\draw (9.8,-1) rectangle (10.5,2);
\node at (9,1.5) {$\dec^t$};
\node at (10.15,0.5) {$\epr$};
\node at (8.25,-0.9) {$\hat{E}'$};
\draw (10.5,0.5) -- (11.6,0.5);
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture} }
\caption{Quantum TDC against $\lo^{t+1}$.}\label{fig:tsplitstatenoentanglment}
\end{figure}

\begin{figure}[H]
\centering
\resizebox{12cm}{5cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);

\draw (2,4.3) -- (12.4,4.3);
\node at (1.8,4.3) {$\hat{M}$};
\node at (12.5,4.3) {$\hat{M}$};
\node at (1.8,1.5) {$M$};
%\node at (11.5,2.5) {$M'$};

\node at (10.5,2.7) {$M'$};
\draw (11.2,1.5) rectangle (12,3.5);
\node at (11.6,2.5) {$\swap$};
\draw (11.6,0.5) -- (11.6,1.5);
\draw (12,2.5) -- (12.4,2.5);
\node at (12.5,2.7) {$M'$};
\node at (11.3,0.3) {$O$};
\node at (12.5,-1.8) {$\eta$};
\draw [dashed] (12.3,-1.8) -- (12.3,5.5);

\draw (1.8,2.8) ellipse (0.3cm and 1.8cm);
\draw (2.7,-0.2) ellipse (0.15cm and 1cm);
\node at (2.7,0.5) {$E$};
\node at (2.7,-0.7) {$\hat{E}$};

\draw (2.8,0.6) -- (3,0.6);
\draw (2.8,-0.7) -- (7,-0.7);
\draw (7,-0.7) -- (8.9,-0.7);
%\draw (5,4.5) -- (15,4.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%	\node at (14.5,4.7) {$S$};

%\node at (1.5,1.5) {$S$};
\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (3,-0.5) rectangle (4.5,3.5);
\node at (3.8,1.5) {$\enc^t$};

%	\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (2.28,-1.8) -- (2.28,5.5);
\draw [dashed] (8.7,-1.8) -- (8.7,5.5);
%	\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (11.1,-1.8) -- (11.1,5.5);

%	\node at (6.2,1.6) {$\ket{\psi}_{NM}$};
\node at (2.14,-1.8) {$\sigma$};
\node at (8.7,-1.8) {${\tau}$};
%	\node at (10.2,-0.8) {${\rho}$};
\node at (11.2,-1.8) {$\nu$};

\node at (4.7,3) {$X_1$};
\node at (7.25,3) {$X_1'$};

\draw (4.5,2.8) -- (6,2.8);
\draw (7,2.8) -- (7.6,2.8);
\draw (8.5,2.5) -- (11.2,2.5);
\draw (8.5,1) -- (10.3,1);
\node at (8.95,0.8) {$E'$};
%\draw (14,2.4) -- (15,2.4);

\node at (4.7,0.4) {$X_t$};
\node at (7.25,0) {$X_t'$};
\draw (4.5,0.2) -- (6,0.2);
\draw (7,0.2) -- (7.6,0.2);
%	\draw (9.5,0.2) -- (11,0.2);

% \node at (4.7,1.8) {$X_2$};
%\node at (8.25,1.8) {$X_2'$};
%\draw  (4.5,1.6) -- (5,1.6);
\draw [dashed] (6.5,1.2) -- (6.5,1.8);
\draw [dashed] (4.7,1) -- (4.7,2.5);
\draw [dashed] (7.3,1) -- (7.3,2.5);
% \draw (7,1.6) -- (8.6,1.6);
%\draw (6,1.1) rectangle (7,1.9);
\draw (8.9,-0.1) rectangle (9.7,-0.9);
% \node at (6.5,1.5) {$V$};
% \node at (7.5,1.3) {$E'_2$};
% \node at (5.5,1.4) {$E_2$};
%\draw (5.8,1.4) -- (6,1.4);
%\draw (5,1.6) -- (6,1.6);

\draw (6,2.1) rectangle (7,2.9);
\node at (6.5,2.5) {$\Lambda_1$};
\draw (6,0.1) rectangle (7,0.9);
\node at (6.5,0.5) {$\Lambda_t$};
\node at (9.3,-0.5) {$\Lambda_{t+1}$};

\node at (6.5,-1.4) {$\mathcal{A}=(\Lambda_1, \cdots, \Lambda_{t+1})$};
%\draw (4.9,-2) rectangle (8.1,3.8);

%\draw (5.5,1.5) ellipse (0.3cm and 1.1cm);
%\node at (5.5,2.2) {$E_1$};
%\draw (5.7,2.2) -- (6,2.2);
%\node at (7.5,2.2) {$E'_1$};
%\draw (7,2.2) -- (7.2,2.2);
%\node at (5.5,0.8) {$E_3$};
%\draw (5.7,0.7) -- (6,0.7);
%\node at (7.5,0.6) {$E'_3$};
%\draw (7.0,0.7) -- (7.2,0.7);

%\draw (9,2.8) circle (0.5);
%	\node at (9,2.8) {$\mathcal{M}$};
%	\draw (9,0.2) circle (0.5);
%	\node at (9,0.2) {$\mathcal{M}$};
%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (7.6,-0.2) rectangle (8.5,3.2);
\draw (10.3,-1) rectangle (11,2);
\node at (8,1.5) {$\dec^t$};
\node at (10.65,0.5) {$\epr$};
\node at (10,-0.9) {$\hat{E}'$};
\draw (11,0.5) -- (11.6,0.5);
\draw (9.7,-0.4) -- (10.3,-0.4);
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture} }
\caption{Analysis of quantum TDC against $\lo^{t+1}$.}\label{fig:t1splitstatenoentanglment}
\end{figure}

\suppress{The decoding scheme, denoted as $\dec$, for the quantum TDC against $\lo^{t+1}$ operates as follows:
\begin{itemize}
\item The decoder initiates the decoding process by employing $\Dec^t$ to decode the quantum NMC, resulting in registers $M'$ and $E'$.
\item Subsequently, an $\epr$ test is performed on registers $E'\hat{E}$. This entails a binary outcome measurement with two possible outcomes: ${\Pi = \Phi_{E\hat{E}}, \Bar{\Pi} = \id_{E \hat{E}} - \Phi_{E\hat{E}}}$.
\item An acceptance decision is made if the outcome is $\Pi = \Phi_{E\hat{E}}$ (corresponding to outcome '1' in a binary result). In this case, the operation $\swap$ (stands for 'Replace') outputs the register $M'$.
\item If the outcome is not $\Pi = \Phi_{E\hat{E}}$, the operation $\swap$ outputs a special symbol, denoted as $\bot_{}$, in register $M'$.
\end{itemize}

\noindent Since the state $\tau$ is derived after tampering against $\lo^t$, the security of the quantum NMC against $\lo^t$ guarantees:
\[ \tau_{\hat{M}M'E' \hat{E}} \approx_{\eps} p_{\mathcal{A}^t} \sigma_{M \hat{M}} \otimes \Phi_{E \hat{E}} + (1-p_{\mathcal{A}^t}) \gamma_{M'E'} \otimes \sigma_{\hat{M}} \otimes \Phi_{\hat{E}},\]

\suppress{Since the state $\tau$ is derived after tampering against $\lo^t$,provides assurance regarding the properties of the state $\tau$ in \cref{fig:t1splitstatenoentanglment}. Specifically,
\[ \tau_{\hat{M}M'E' \hat{E}} \approx_{\eps} p_{\mathcal{A}^t} \sigma_{M \hat{M}} \otimes \Phi_{E \hat{E}} + (1-p_{\mathcal{A}^t}) \gamma_{M'E'} \otimes \sigma_{\hat{M}} \otimes \Phi_{\hat{E}},\]}

\noindent where $(p_{\mathcal{A}^t}, \gamma_{M'E'})$ depend only on tampering adversary $\mathcal{A}^t$. The data processing inequality \cref{fact:data} now tells us that the Bell basis measurement in $\epr$ is either completely independent of the the message $M$, or acts on a product state:
\begin{equation}\label{eq:qtdclo}
\nu_{\hat{M}M'O} \approx_{\eps} p_{\mathcal{A}^t} \sigma_{ \hat{M}M} \otimes  \epr ( \Lambda_{t+1} (\Phi_{E \hat{E}} ) )  + (1-p_{\mathcal{A}^t}) \sigma_{\hat{M}} \otimes   \epr(\gamma_{M'E'} \otimes  \Lambda_{t+1} (\Phi_{\hat{E}}) ).
\end{equation}

To proceed, we state two claims, \cref{claim:epr1} and \cref{claim:epr2}, which enable us to analyze the two terms in the convex combination above. In \cref{claim:epr1}, we point out the (trivial) observation that if the non-malleable code recovers the message $\sigma_{\hat{M}M}$, then the Bell basis measurement is independent of $\sigma$:

\begin{claim}\label{claim:epr1}
$\epr ( \Lambda_{t+1} (\Phi_{E \hat{E}} ) ) = p_{\Lambda_{t+1}} \ketbra{1} + (1-p_{\Lambda_{t+1}}) \ketbra{0}$,  where $p_{\Lambda_{t+1}} $, depends only on $\Lambda_{t+1}$.
\end{claim}

In \cref{claim:epr2}, we formalize the fact that the Bell basis measurement rejects product states with high probability. We state its proof in \cref{sec:epr2}.

\begin{claim}\label{claim:epr2}
$  \epr(\gamma_{M'E'} \otimes  \Lambda_{t+1} (\Phi_{\hat{E}}) ) \approx_{2\cdot 2^{-\lambda}} \zeta_{M'} \otimes \ketbra{0} $, for some density matrix $\zeta_{M'} $.
\end{claim}
By combining~\cref{claim:epr1}, \cref{claim:epr2} and \cref{eq:qtdclo}, we are guaranteed the decoder outputs a convex combination of the original message $\sigma_{\hat{M}M}$ or the Bell basis measurement rejects:
\[   \nu_{\hat{M}M'O} \approx_{\eps +2\cdot 2^{-\lambda}} p_{\mathcal{A}^t} p_{\Lambda_{t+1}} \sigma_{ \hat{M}M} \otimes  \ketbra{1} +p_{\mathcal{A}^t} (1-p_{\Lambda_{t+1}})  \sigma_{ \hat{M}M} \otimes  \ketbra{0}  + (1-p_{\mathcal{A}^t}) \sigma_{\hat{M}} \otimes  \zeta_{M'} \otimes \ketbra{0}. \]

\noindent We can now conclude using the data processing \cref{fact:data}:
\[  \Dec\circ \Lambda\circ\Enc(\sigma_{\hat{M}M}) =  \eta_{\hat{M}M'} \approx_{\eps +2\cdot 2^{-\lambda}} p_{\mathcal{A}^t} p_{\Lambda_{t+1}} \sigma_{ \hat{M}M} +(1-p_{\mathcal{A}^t} p_{\Lambda_{t+1}} ) \sigma_{\hat{M}} \otimes  \bot_{M'} , \]
\noindent which implies~\cref{theorem:tsplit-reduction}, since the probability $ p_{\mathcal{A}^t} p_{\Lambda_{t+1}} $ depends only on the tampering adversary $\mathcal{A}$.

\subsubsection{Proof of~\cref{claim:epr2}}\label{sec:epr2}

We point out that $\phi_{M'E' \hat{E} }=\gamma_{M'E'} \otimes  \Lambda_{t+1} (\Phi_{\hat{E}}) $ is a product state, and therefore can be written as a convex combination of pure states of rank $1$ across the cut $(M'E')/\hat{E}$. Using \cref{claim:tss-bellbasis} below, we prove $\epr( \phi_{M'E' \hat{E} } )$ outputs outcome $0$ with probability at least $1-2^{-\lambda}$.

\begin{claim}\label{claim:tss-bellbasis} Let
$ \Phi_{E \hat{E}} \equiv \Phi^{\otimes \lambda} $ denote
$\lambda$ EPR pairs on a bipartite register $E, \hat{E}$. Let $\tau_{E\hat{E}}$ be a pure state of Schmidt rank $R$. Then, measuring $\tau$ with the binary measurement $\{ \Phi_{E\hat{E}} , \id_{E\hat{E}}  -\Phi_{E\hat{E}}  \}$ outputs the $\Phi_{E\hat{E}}$ with negligible probability, i.e.,
\begin{equation*}
\Tr[\Phi^{\otimes \lambda}\tau]\leq R\cdot 2^{- \lambda}.
\end{equation*}

\noindent Similarly, if $\tau_{E\hat{E}}$ were a mixed state with Schmidt number $R$, then $\Tr[\Phi^{\otimes \lambda}\tau]\leq R\cdot 2^{- \lambda}.$
\end{claim}

Recall that the Schmidt rank/number (\Cref{def:schmidt-number}) is non-increasing under local operations, and so if $\phi_{M'E' \hat{E} }$ has rank 1 across the cut $(M'E')/\hat{E}$, the RDM $\phi_{E'\hat{E}}$ has Schmidt number $1$. \cref{claim:epr2} follows.

\begin{proof}

[of \Cref{claim:tss-bellbasis}] Let us first consider a pure state $\ket{\phi}$ of rank $R$, and let $\ket{\phi} = \sum_{i=1}^R \alpha_i \ket{u_i}_E\otimes \ket{v_i}_{\hat{E}}$, $ \Phi_{E \hat{E}} \equiv \ket{\Phi}^{\otimes \lambda} = 2^{-\lambda/2} \sum_j  \ket{j}_E\otimes \ket{j}_{\hat{E}}$ define Schmidt decompositions. Then, by the triangle and the Cauchy-Schwartz inequalities:
\begin{gather}
\Tr[\Phi^{\otimes \lambda}\phi]^{1/2} = |\bra{\Phi}^{\otimes \lambda}\ket{\phi}| \leq \sum_i^R |\alpha_i|\cdot |\bra{\Phi}^{\otimes \lambda}\ket{u_i}\otimes \ket{v_i}|\leq \\ \leq \max_{\ket{u}\otimes \ket{v}} |\bra{\Phi}^{\otimes \lambda}\ket{u}\otimes \ket{v}| \cdot R^{1/2}\cdot \bigg(\sum_i |\alpha_i|^2\bigg)^{1/2} \leq R^{1/2}\cdot \max_{\ket{u}\otimes \ket{v}} |\bra{\Phi}^{\otimes \lambda}\ket{u}\otimes \ket{v}|
\end{gather}
\noindent In turn,
\begin{gather}
|\bra{\Phi}^{\otimes \lambda}\ket{u}\otimes \ket{v}| =  2^{-\lambda/2}\cdot \bigg|\sum_j \bra{j}\ket{u}\cdot  \bra{j}\ket{v}\bigg| \leq  2^{-\lambda/2}\bigg(\sum_j \cdot |\bra{j}\ket{u}|^2\bigg)^{1/2} \bigg(\sum_j  |\bra{j}\ket{v}|^2\bigg)^{1/2} \leq 2^{-\lambda/2},
\end{gather}
\noindent which gives us the desired bound. If $\tau$ is a mixed state of Schmidt number $R$, then it can be written as a convex combination of pure states of Schmidt rank $\leq R$, which concludes the claim.
\end{proof}

\suppress{

Note $\gamma_{M'E'} \otimes  \Lambda_{t+1} (\Phi_{\hat{E}}) $ can be written as a convex combination of pure states $\ket{\phi}_{M'E'\hat{E}} $ of Schmidt rank $1$, i.e. $\ket{\phi}_{M'E'\hat{E}}  = \ket{\phi}_{M'E'}  \otimes \ket{\phi}_{\hat{E}} $. Using \cref{claim:tss-bellbasis}, we have that $\epr( \phi_{M'E' \hat{E} } )$ outputs outcome $0$ with probability atleast $1-2^{-\lambda}$. Using gentle measurement lemma~\cref{fact:gentle_measurement} along with \cref{fact:traceconvex}, we have the desired~\cref{claim:epr2}.

\begin{claim}\label{claim:tss-bellbasis} Let
$ \Phi_{E \hat{E}} \equiv \Phi^{\otimes \lambda} $ denote
$\lambda$ EPR pairs on a bipartite register $E, \hat{E}$. Let $\phi_{E\hat{E}A}$ be a quantum state  of Schmidt rank $R$ such that  $\phi_{E\hat{E}A} = \sum_i^R \alpha_i \ket{u_i}_E\otimes \ket{v_i}_{\hat{E}A}$, where $\{ \ket{u_i}_E\}$,  $\{\ket{v_i}_{\hat{E}A}\}$ are orthogonal. Then, measuring the state $\phi$ in $\{ \Phi_{E\hat{E}} , \id_{E\hat{E}}  -\Phi_{E\hat{E}}  \}$ binary measurement outputs the outcome corresponding to  $\Phi_{E\hat{E}}$ with negligible probability, i.e.,
\begin{equation*}
\Tr[\Phi^{\otimes \lambda}\phi]\leq R\cdot 2^{- \lambda}.
\end{equation*}
\end{claim}

\subsubsection{Proof of~\cref{claim:tss-bellbasis}}

Let $ \ket{\phi} = \sum_{i=1}^R \alpha_i \ket{u_i}_E\otimes \ket{v_i}_{\hat{E}A}$, $ \Phi_{E \hat{E}} \equiv \ket{\Phi}^{\otimes \lambda} = 2^{-\lambda/2} \sum_j  \ket{j}_E\otimes \ket{j}_{\hat{E}}$ define Schmidt decompositions of $\phi$ and ${\Phi}^{\otimes \lambda}$. Consider,
\begin{align*}
\Tr[\Phi^{\otimes \lambda }\phi]^{1/2} & = \| \bra{\Phi}^{\otimes \lambda }\ket{\phi}  \|_2 \\
& \leq \sum_{i=1}^R  \vert \alpha_i \vert \cdot
\|\bra{\Phi}^{\otimes \lambda}\ket{u_i}_E\otimes \ket{v_i}_{\hat{E}A}\|_2  \\
& \leq \bigg(\sum_{i=1}^R  \|\bra{\Phi}^{\otimes \lambda}\ket{u_i} \otimes \ket{v_i}_{}\|_2^2  \bigg)^{1/2}   \cdot \bigg(\sum_{i=1}^R \vert \alpha_i \vert^2\bigg)^{1/2} \\
& \leq  R^{1/2} \max_i \| \bra{\Phi}^{\otimes \lambda}\ket{u_i} \otimes \ket{v_i}_{}\|_2    \\
& =  R^{1/2} \max_i  2^{-\lambda/2}\cdot \bigg \| \sum_j \bra{j}\ket{u_i}\cdot  \bra{j}\ket{v_i}\bigg \|_2 \\
& \leq  R^{1/2} \max_i  2^{-\lambda/2}\cdot   \sum_j \vert \bra{j}\ket{u_i} \vert \cdot  \|\bra{j}\ket{v_i} \|_2 \\
& \leq  R^{1/2} \max_i  2^{-\lambda/2}\cdot  \bigg( \sum_j \vert \bra{j}\ket{u_i}  \vert^2 \bigg)^{1/2}  \cdot  \bigg( \sum_j  \| \bra{j}\ket{v_i}  \|_2^2 \bigg)^{1/2}  \\
& \leq  R^{1/2}  2^{-\lambda/2}.
\end{align*}

\subsection{Augmented Non-Malleable Codes and the Bounded Storage Model}

To extend our reduction to the bounded storage model, the sole modification to our construction lies in picking an \textit{augmented} non-malleable code $(\Enc_t, \Dec_t)$  against $\lo^{t}_{(e_1,e_2, \ldots e_t)}$ tampering adversaries.

%Suppose we now run the tamper-detection reduction in \Cref{alg:tamper-detection}, but with $(\Enc_t, \Dec_t)$ as an augmented non-malleable code against $\lo^{t+1}_{(e_1,e_2, \ldots e_t)}$ tampering adversaries.

\begin{figure}[h]
\centering
\resizebox{12cm}{5cm}{
\begin{tikzpicture}
\draw (5.6,1) ellipse (0.2cm and 1.5cm);
\node at (5.6,2) {$E_1$};
\node at (5.6,0.7) {$E_t$};

\draw (5.8,0.7) -- (6,0.7);
\draw (7.4,0.7) -- (7,0.7);
\node at (7.4,0.5) {$E'_t$};
%      \node at (14.5,3.7) {$R$};
\draw (5.7,2.2) -- (6,2.2);
\draw (7.4,2.2) -- (7,2.2);
\node at (7.4,2) {$E'_1$};

\node at (5.2,-0.2) {$E_{t+1}$};
\draw (5.65,-0.4) -- (6,-0.4);
\draw (7,-0.4) -- (7.4,-0.4);
\node at (7.4,-0.2) {$E'_{t+1}$};
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);

\draw (2,4.3) -- (12.2,4.3);
\node at (1.8,4.3) {$\hat{M}$};
\node at (12.5,4.3) {$\hat{M}$};
\node at (1.8,1.5) {$M$};
%\node at (11.5,2.5) {$M'$};

\node at (10.5,2.7) {$M'$};
\draw (11.2,1.5) rectangle (12,3.5);
\node at (11.6,2.5) {$\swap$};
\draw (11.6,0.5) -- (11.6,1.5);
\draw (12,2.5) -- (12.4,2.5);
\node at (12.5,2.7) {$M'$};
\node at (11.4,0.3) {$O$};
\node at (12.5,-1.8) {$\eta$};
\draw [dashed] (12.3,-1.8) -- (12.3,5.5);

\draw (1.8,2.8) ellipse (0.3cm and 1.8cm);
\draw (2.7,-0.2) ellipse (0.15cm and 1cm);
\node at (2.7,0.5) {$E$};
\node at (2.7,-0.7) {$\hat{E}$};

\draw (2.8,0.6) -- (3,0.6);
\draw (2.8,-0.7) -- (6,-0.7);
\draw (7,-0.7) -- (9.8,-0.7);
%\draw (5,4.5) -- (15,4.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%	\node at (14.5,4.7) {$S$};

%\node at (1.5,1.5) {$S$};
\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (3,-0.5) rectangle (4.5,3.5);
\node at (3.8,1.5) {$\enc^t$};

%	\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (2.28,-1.8) -- (2.28,5.5);
%	\draw [dashed] (8.3,-0.8) -- (8.3,5.5);
%	\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (11,-1.8) -- (11,5.5);

%	\node at (6.2,1.6) {$\ket{\psi}_{NM}$};
\node at (2.14,-1.8) {$\sigma$};
%	\node at (8.1,-0.8) {$\hat{\rho}$};
%	\node at (10.2,-0.8) {${\rho}$};
\node at (11.1,-1.8) {$\nu$};

\node at (4.7,3) {$X_1$};
\node at (8.25,3) {$X'_1$};

\draw (4.5,2.8) -- (6,2.8);
\draw (7,2.8) -- (8.6,2.8);
\draw (9.5,2.5) -- (11.2,2.5);
\draw (9.5,1) -- (9.8,1);
\node at (9.65,0.8) {$E'$};
%\draw (14,2.4) -- (15,2.4);

\node at (4.7,0.4) {$X_t$};
\node at (8.25,0) {$X_t'$};
\draw (4.5,0.2) -- (6,0.2);
\draw (7,0.2) -- (8.6,0.2);
%	\draw (9.5,0.2) -- (11,0.2);

% \node at (4.7,1.8) {$X_2$};
%\node at (8.25,1.8) {$X_2'$};
%\draw  (4.5,1.6) -- (5,1.6);
\draw [dashed] (6.5,1.2) -- (6.5,1.8);
\draw [dashed] (4.7,1) -- (4.7,2.5);
\draw [dashed] (8.3,1) -- (8.3,2.5);
% \draw (7,1.6) -- (8.6,1.6);
%\draw (6,1.1) rectangle (7,1.9);
\draw (6,-0.1) rectangle (7,-0.9);
% \node at (6.5,1.5) {$V$};
% \node at (7.5,1.3) {$E'_2$};
% \node at (5.5,1.4) {$E_2$};
%\draw (5.8,1.4) -- (6,1.4);
%\draw (5,1.6) -- (6,1.6);

\draw (6,2.1) rectangle (7,2.9);
\node at (6.5,2.5) {$\Lambda_1$};
\draw (6,0.1) rectangle (7,0.9);
\node at (6.5,0.5) {$\Lambda_t$};
\node at (6.5,-0.5) {$\Lambda_{t+1}$};

\node at (6.5,-1.4) {$\mathcal{A}=(\Lambda_1, \cdots, \Lambda_{t+1})$};
\draw (4.9,-2) rectangle (8.1,3.8);

%\draw (5.5,1.5) ellipse (0.3cm and 1.1cm);
%\node at (5.5,2.2) {$E_1$};
%\draw (5.7,2.2) -- (6,2.2);
%\node at (7.5,2.2) {$E'_1$};
%\draw (7,2.2) -- (7.2,2.2);
%\node at (5.5,0.8) {$E_3$};
%\draw (5.7,0.7) -- (6,0.7);
%\node at (7.5,0.6) {$E'_3$};
%\draw (7.0,0.7) -- (7.2,0.7);

%\draw (9,2.8) circle (0.5);
%	\node at (9,2.8) {$\mathcal{M}$};
%	\draw (9,0.2) circle (0.5);
%	\node at (9,0.2) {$\mathcal{M}$};
%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (8.6,-0.5) rectangle (9.5,3.2);
\draw (9.8,-1) rectangle (10.5,2);
\node at (9,1.5) {$\dec^t$};
\node at (10.15,0.5) {$\epr$};
\node at (8.25,-0.9) {$\hat{E}'$};
\draw (10.5,0.5) -- (11.6,0.5);
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture} }
\caption{Quantum tamper-detection code against $\lo^{t+1}_{(e_1-a,e_2,\ldots, e_{t+1}=a))}$.}\label{fig:t3splitstatenoentanglment}
\end{figure}

Let us denote a tampering adversary $\lo^{(t+1)}_{(e_1-a,e_2, \ldots, e_{t+1}=a)}$ as $\mathcal{A} = (\Lambda_1, \Lambda_2, \ldots, \Lambda_{t+1}, \ketbra{\psi}_{E_1 E_2 \ldots E_{t+1}})$, and its ``truncation" to the first $t$ shares as $\mathcal{A}^t= (\Lambda_1, \Lambda_2, \ldots , \Lambda_{t} , \ketbra{\psi}_{E_1 \ldots E_{t+1}})$. In \Cref{fig:t3splitstatenoentanglment}, we depict the tampering experiment on the code in the bounded storage model. We are now in a position to prove our reduction.

\subsubsection{Proof of~\cref{theorem:tsplit-bounded-storage}}

To begin our proof, we similarly view the tampering process in \Cref{fig:t3splitstatenoentanglment} through the equivalent process in \Cref{fig:t2splitstatenoentanglment}. Note that they only differ in that in \cref{fig:t2splitstatenoentanglment} we have delayed the action of $\Lambda_{t+1}$ to consider an intermediate state $\tau$. Informally $\tau$ amounts to the system after $\mathcal{A}^t$ and the non-malleable code has been decoded, but before $\Lambda_{t+1}$.

%Consider the tampering processes in \cref{fig:t3splitstatenoentanglment,fig:t2splitstatenoentanglment}. \cref{fig:t3splitstatenoentanglment} corresponds to the tampering process of the $(\enc , \dec)$ against $\mathcal{A}$. Note both the tampering processes are equivalent except that in \cref{fig:t2splitstatenoentanglment}, we have delayed the action of $\Lambda_{t+1}$ to consider an intermediate state $\tau$ as stated in \cref{fig:t2splitstatenoentanglment}.

\begin{figure}[h]
\centering
\resizebox{12cm}{5cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);

\draw (5.6,1) ellipse (0.2cm and 1.5cm);
\node at (5.6,2) {$E_1$};
\node at (5.6,0.7) {$E_t$};

\draw (5.8,0.7) -- (6,0.7);
\draw (7.4,0.7) -- (7,0.7);
\node at (7.4,0.5) {$E'_t$};
%      \node at (14.5,3.7) {$R$};
\draw (5.7,2.2) -- (6,2.2);
\draw (7.4,2.2) -- (7,2.2);
\node at (7.4,2) {$E'_1$};

\node at (5.1,-0.2) {$E_{t+1}$};
\draw (5.65,-0.4) -- (8.9,-0.4);
\draw (9.7,-0.2) -- (10,-0.2);
%\draw (7,-0.4) -- (7.4,-0.4);
\node at (9.9,0.1) {$E'_{t+1}$};

\draw (2,4.3) -- (12.4,4.3);
\node at (1.8,4.3) {$\hat{M}$};
\node at (12.6,4.3) {$\hat{M}$};
\node at (1.8,1.5) {$M$};
%	\node at (11.5,2.5) {$M'$};

\node at (10.5,2.7) {$M'$};
\draw (11.2,1.5) rectangle (12,3.5);
\node at (11.6,2.5) {$\swap$};
\draw (11.6,0.5) -- (11.6,1.5);
\draw (12,2.5) -- (12.4,2.5);
\node at (12.5,2.7) {$M'$};
\node at (11.4,0.3) {$O$};
\node at (12.5,-1.8) {$\eta$};
\draw [dashed] (12.3,-1.8) -- (12.3,5.5);

\draw (1.8,2.8) ellipse (0.3cm and 1.8cm);
\draw (2.7,-0.2) ellipse (0.15cm and 1cm);
\node at (2.7,0.5) {$E$};
\node at (2.7,-0.7) {$\hat{E}$};

\draw (2.8,0.6) -- (3,0.6);
\draw (2.8,-0.7) -- (7,-0.7);
\draw (7,-0.7) -- (8.9,-0.7);
%\draw (5,4.5) -- (15,4.5);
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%	\node at (14.5,4.7) {$S$};

%\node at (1.5,1.5) {$S$};
\draw (2,1.5) -- (3,1.5);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (3,-0.5) rectangle (4.5,3.5);
\node at (3.8,1.5) {$\enc^t$};

%	\draw  (2,1.5) -- (2,4.5);
\draw [dashed] (2.28,-1.8) -- (2.28,5.5);
\draw [dashed] (8.7,-1.8) -- (8.7,5.5);
%	\draw [dashed] (10,-0.8) -- (10,5.5);
\draw [dashed] (11.1,-1.8) -- (11.1,5.5);

%	\node at (6.2,1.6) {$\ket{\psi}_{NM}$};
\node at (2.14,-1.8) {$\sigma$};
\node at (8.7,-1.8) {${\tau}$};
%	\node at (10.2,-0.8) {${\rho}$};
\node at (11.2,-1.8) {$\nu$};

\node at (4.7,3) {$X_1$};
\node at (7.25,3) {$X_1'$};

\draw (4.5,2.8) -- (6,2.8);
\draw (7,2.8) -- (7.6,2.8);
\draw (8.5,2.5) -- (11.2,2.5);
\draw (8.5,1) -- (10.3,1);
\node at (8.95,0.8) {$E'$};
%\draw (14,2.4) -- (15,2.4);

\node at (4.7,0.4) {$X_t$};
\node at (7.25,0) {$X_t'$};
\draw (4.5,0.2) -- (6,0.2);
\draw (7,0.2) -- (7.6,0.2);
%	\draw (9.5,0.2) -- (11,0.2);

% \node at (4.7,1.8) {$X_2$};
%\node at (8.25,1.8) {$X_2'$};
%\draw  (4.5,1.6) -- (5,1.6);
\draw [dashed] (6.5,1.2) -- (6.5,1.8);
\draw [dashed] (4.7,1) -- (4.7,2.5);
\draw [dashed] (7.3,1) -- (7.3,1.7);
% \draw (7,1.6) -- (8.6,1.6);
%\draw (6,1.1) rectangle (7,1.9);
\draw (8.9,-0.1) rectangle (9.7,-0.9);
% \node at (6.5,1.5) {$V$};
% \node at (7.5,1.3) {$E'_2$};
% \node at (5.5,1.4) {$E_2$};
%\draw (5.8,1.4) -- (6,1.4);
%\draw (5,1.6) -- (6,1.6);

\draw (6,2.1) rectangle (7,2.9);
\node at (6.5,2.5) {$\Lambda_1$};
\draw (6,0.1) rectangle (7,0.9);
\node at (6.5,0.5) {$\Lambda_t$};
\node at (9.3,-0.5) {$\Lambda_{t+1}$};

\node at (6.5,-1.4) {$\mathcal{A}=(\Lambda_1, \ldots, \Lambda_{t+1})$};
%\draw (4.9,-2) rectangle (8.1,3.8);

%\draw (5.5,1.5) ellipse (0.3cm and 1.1cm);
%\node at (5.5,2.2) {$E_1$};
%\draw (5.7,2.2) -- (6,2.2);
%\node at (7.5,2.2) {$E'_1$};
%\draw (7,2.2) -- (7.2,2.2);
%\node at (5.5,0.8) {$E_3$};
%\draw (5.7,0.7) -- (6,0.7);
%\node at (7.5,0.6) {$E'_3$};
%\draw (7.0,0.7) -- (7.2,0.7);

%\draw (9,2.8) circle (0.5);
%	\node at (9,2.8) {$\mathcal{M}$};
%	\draw (9,0.2) circle (0.5);
%	\node at (9,0.2) {$\mathcal{M}$};
%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (7.6,-0.2) rectangle (8.5,3.2);
\draw (10.3,-1) rectangle (11,2);
\node at (8,1.5) {$\dec^t$};
\node at (10.65,0.5) {$\epr$};
\node at (10,-0.9) {$\hat{E}'$};
\draw (11,0.5) -- (11.6,0.5);
\draw (9.7,-0.4) -- (10.3,-0.4);
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture} }
\caption{Analysis of Quantum tamper-detection code against $\lo^{t+1}_{(e_1,e_2,\ldots, e_{t+1}=a))}$.}\label{fig:t2splitstatenoentanglment}
\end{figure}

By bundling together the (augmented) first register $E_1$ with the entanglement in the new register $E_{t+1}$, note that $|E_1E_{t+1}| \leq a + (e_1-a)= e_1$. The security of the augmented quantum non-malleable code against $\lo^{t}_{(e_1, e_2, \ldots, e_t)}$ ensures the following about state $\tau$:
\[ \tau_{\hat{M}M'E' \hat{E}E_{t+1}E'_1} \approx_{\eps} p_{\mathcal{A}^t} \sigma_{M \hat{M}} \otimes \Phi_{E \hat{E}} \otimes \zeta_{E_{t+1}E'_1} + (1-p_{\mathcal{A}^t}) \gamma_{M'E'E_{t+1}E'_1} \otimes \sigma_{\hat{M}} \otimes \Phi_{\hat{E}},\]
where $ p_{\mathcal{A}^t}, \gamma_{M'E'E_{t+1}E'_1}$ and $ \zeta_{E_{t+1}E'_1}$ depend only on adversary $\mathcal{A}^t$. Using data processing \cref{fact:data}, we have
\begin{equation}\label{eq:qtdclo1}
\nu_{\hat{M}M'O} \approx_{\eps} p_{\mathcal{A}^t} \sigma_{ \hat{M}M} \otimes  \epr ( \Tr_{E'_{t+1}}\left( \Lambda_{t+1} (\Phi_{E \hat{E}} \otimes \zeta_{E_{t+1}} ) \right)  )  + (1-p_{\mathcal{A}^t}) \sigma_{\hat{M}} \otimes   \epr( \Tr_{E'_{t+1}}\left( \Lambda_{t+1} (\gamma_{M'E'E_{t+1}} \otimes \Phi_{\hat{E}}) \right) ).
\end{equation}

To proceed, we state two claims, \cref{claim:epr3} and \cref{claim:epr4}, which enable us to analyze the two terms in the convex combination above. In \cref{claim:epr3}, we point out the (trivial) observation that if the non-malleable code recovers the message $\sigma_{\hat{M}M}$, then the Bell basis measurement is independent of $\sigma$:

\begin{claim}\label{claim:epr3}
$ \epr ( \Tr_{E'_{t+1}}\left( \Lambda_{t+1} (\Phi_{E \hat{E}} \otimes \zeta_{E_{t+1}} ) \right)  )  = p_{{t+1}} \ketbra{1} + (1-p_{{t+1}}) \ketbra{0}$,  where $p_{{t+1}} $, depends only on $(\Lambda_{t+1} ,\zeta_{E_{t+1}} )$.
\end{claim}

In turn, \cref{claim:epr4} formalizes that the Bell basis measurement rejects states of low Schmidt rank.

\begin{claim}\label{claim:epr4}

$\epr( \Tr_{E'_{t+1}}\left( \Lambda_{t+1} (\gamma_{M'E'E_{t+1}} \otimes \Phi_{\hat{E}}) \right) ) \approx_{2^{1+a-\lambda}} \kappa_{M'} \otimes \ketbra{0} $, where $\kappa_{M'} $ is some density matrix, so long as the size of the $(t+1)$st register is $\vert E_{t+1} \vert \leq a.$
\end{claim}

Once again by combining \cref{claim:epr3}, \cref{claim:epr4} and \cref{eq:qtdclo1}, we are guaranteed the decoder outputs a convex combination of the original message $\sigma_{\hat{M}M}$ or the Bell basis measurement rejects:
\[   \nu_{\hat{M}M'O} \approx_{\eps +2^{1+a-\lambda}} p_{\mathcal{A}^t} p_{{t+1}} \sigma_{ \hat{M}M} \otimes  \ketbra{1} +p_{\mathcal{A}^t} (1-p_{{t+1}})  \sigma_{ \hat{M}M} \otimes  \ketbra{0}  + (1-p_{\mathcal{A}^t}) \sigma_{\hat{M}} \otimes  \kappa_{M'} \otimes \ketbra{0}. \]

\noindent Again by the data processing \cref{fact:data},
\[   \eta_{\hat{M}M'} \approx_{\eps + 2^{1+a-\lambda}} p_{\mathcal{A}^t} p_{{t+1}} \sigma_{ \hat{M}M} +(1-p_{\mathcal{A}^t} p_{{t+1}} ) \sigma_{\hat{M}} \otimes  \bot_{M'} . \]

Which implies the desired theorem if we note that $ p_{\mathcal{A}^t} p_{{t+1}} $ depends only on tampering adversary $\mathcal{A}$. This follows since $p_{{t+1}} $ depends only on $(\Lambda_{t+1} ,\zeta_{E_{t+1}} )$ and $\zeta_{E_{t+1}} $ depends only on $\mathcal{A}^t$. It only remains to prove \cref{claim:epr4}:

\begin{proof}

[of \cref{claim:epr4}] Our goal is to prove the Bell basis measurement on the state $ \Tr_{E'_{t+1}}\left( \Lambda_{t+1} (\gamma_{M'E'E_{t+1}} \otimes \Phi_{\hat{E}}) \right)$ rejects with high probability. Note that the Schmidt number of this state across the $(E', E_{t+1})$ cut is at most the Schmidt number of $\gamma_{M'E'E_{t+1}} \otimes \Phi_{\hat{E}}$ across the $(M'E', E_{t+1}\hat{E})$, since the partial trace and $\Lambda_{t+1}$ are local operations, and local operations do not increase Schmidt number \cref{prop:schimidt}.

However, the Schmidt number of $\gamma_{M'E'E_{t+1}} \otimes \Phi_{\hat{E}}$ across the cut $(M'E', E_{t+1}\hat{E})$ is at most the Schmidt number of $\gamma_{M'E'E_{t+1}}$ across the $(M'E',E_{t+1})$ cut, which is in turn $\leq 2^a$ since the size of $|E_{t+1}|\leq a$. Applying \Cref{claim:tss-bellbasis} gives us the desired bound.
\end{proof}

%Consider the Schmidt rank of $\gamma_{M'E'E_{t+1}}$ across the $(M'E',E_{t+1})$ cut. Since $E_{t+1}$ is the register of the pre-shared entanglement held by the $(t+1)$-st split, and the size of $\vert E_{t+1} \vert \leq a$ we must have that $\gamma_{M'E'E_{t+1}}$ is a mixture of states of Schmidt rank at most $2^a$. Since the adversarial tampering $\Lambda_{t+1}$ is on registers $E_{t+1}\hat{E}$ and $\gamma_{M'E'E_{t+1}} \otimes \Phi_{\hat{E}}$, the state $(\mathbb{I}_{M'E'}\otimes \Lambda_{t+1})(\gamma_{M'E'E_{t+1}}\otimes \Phi_{\hat{E}})$ is a mixture of states of Schmidt rank $\leq 2^a$. \mycomment{cite the fact under locc schmidt rank doesnt grow}  Applying \Cref{claim:tss-bellbasis} and using gentle measurement lemma~\cref{fact:gentle_measurement} along with \cref{fact:traceconvex}, we have the desired~\cref{claim:epr4}.

\suppress{Since both the decoding algorithm $\Dec_t$ and the tampering channel on the additional EPR pair halves commute, let us for now consider the quantum state after the adversarial tampering and decoding the non-malleable code. Let $R$ be the register held by the adversary under augmented security. Then, by \Cref{definition:augmented-quantum-nm},
\begin{gather}
\bigg( [(\Dec_t\otimes \mathbb{I}_R) \circ \Lambda \circ \Enc_t] \otimes \mathbb{I}_{\hat{E}} \bigg)(\psi_{M}\otimes \Phi_{E\hat{E}}) \approx_\epsilon p\cdot \psi_{M} \otimes \Phi_{E\hat{E}} \otimes \sigma_{R} + (1-p)\gamma_{MER} \otimes \Phi_{\hat{E}}
\end{gather}

We can take $R$ to further contain all the entanglement which is held by the $(t+1)$ adversary, \textit{before receiving the share}. Recall the $(t+1)$st adversaries tampering channel only acts on $R\hat{E}$, and thereby once again in the first term above, $\psi_{M}$ is recovered regardless of the Bell basis measurement. }

%The second term is slightly more subtle, as the Schmidt rank of $\gamma_{MER}$ across the $ME/R$ cut maybe much larger than that of the original $a$ EPR pairs. Let $R_{t+1}\subset R$ be the register of the pre-shared entanglement held by the $(t+1)$ adversary. We have $H(R_{t+1})_{\rho_{ME\hat{E}R}}\leq a$, since the adversarial channel doesn't act on $R_{t+1}$, and $R_{t+1}$ has Schmidt rank at most $2^a$ across the $(R_{t+1}, R\setminus R_{t+1})$ cut initially by assumption. By the Alicki-Fannes inequality, $|H(R_{t+1})_{\rho_{ME\hat{E}R}} - H(R_{t+1})_{\Tilde{\rho}_{ME\hat{E}R}}|\leq \epsilon\cdot a+h(\epsilon)$. By the concavity of entropy,

% H(R_{t+1})_{\Tilde{\rho}_{ME\hat{E}R}} \geq  p\cdot H(R_{t+1})_{\sigma_{R}} + (1-p)\cdot H(R_{t+1})_{\gamma_{MER}}\Rightarrow H(R_{t+1})_{\gamma_{MER}}\leq \frac{\epsilon\cdot a+h(\epsilon)}{1-p}
% \end{equation}
%\thiago{missing additional Alicki fannes terms - note, this will not be tight enough, as will give error which is a function of size of $R_{t+1}$! Works for bounded storage, but not bounded entanglement}
% Now, reasoning similar to the proof of \Cref{theorem:tsplit-reduction} directly applies, with rank $\leq 2^{a}$ is the rank of the

% Since in \Cref{alg:tamper-detection}

\newpage
\section{Tamper Detection in the Bounded Storage Model}
\label{section:bounded-storage}

In this section, we present and analyze our quantum tamper detection code in the $3$-split-state model $\lo^3_{(e_1, e_2, e_3)}$, where the adversaries are allowed a finite pre-shared quantum state to assist in tampering with their shares of the code (see \Cref{def:lotsharedentanglement}). In particular, we show security even when $e_1, e_2$ are both unbounded, that is, only the entanglement of one of the parties is restricted.

\begin{theorem}[\cref{theorem:results-main}, restatement]
For every integer $k$, $a\leq \lambda$, there exists an efficient tamper-detection code against $\lo^3_{(a, *, *)}$ for $k$ qubit messages with error $2^{-(k+\lambda)^{\Omega(1)}} + 6\cdot 2^{a-\lambda}$ and rate $(11 + 12\frac{\lambda}{k})^{-1}$.
\end{theorem}

Our construction combines quantum secure non-malleable extractors and families of unitary 2 designs. We refer the reader to \Cref{subsubsection:prelim-nmext} and \Cref{subsection:prelim-2-designs} respectively for formal definitions of the ingredients. We dedicate \cref{subsection:tdc-components} for a description of our construction, and \cref{subsection:tdc-analysis} for its analysis.

\suppress{

\begin{figure}
\centering
\resizebox{12cm}{6cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);
\draw (0,6.3) ellipse (0.3cm and 2.5cm);
\draw (1,5.9) ellipse (0.3cm and 1.2cm);
\draw (3,3.9) rectangle (4.4,5.4);
\draw (11.6,3.9) rectangle (12.5,5.4);
\node at (0,4.5) {$M$};
\node at (1,6.4) {$\hat{E}$};
\node at (1,5.1) {$E$};
\draw (1.2,5.1) -- (3,5.1);

%\draw (0.8,0.5) ellipse (0.3cm and 1.5cm);
%\node at (0.8,-0.7) {$\hat{R}$};
\node at (3.6,4.6) {$C_R$};
\node at (12.1,4.6) {$C^\dagger_{R'}$};
\node at (0,8) {$\hat{M}$};
\node at (15.6,8) {$\hat{M}$};

\draw (0.2,8) -- (15.5,8);
\draw (1.3,6.5) -- (6.3,6.5);
\draw (7.3,6.5) -- (13,6.5);

%\node at (14.5,4.3) {$S'$};
\draw (0.2,4.5) -- (3,4.5);
\draw (4.4,4.5) -- (6.3,4.5);
\draw (7.3,4.5) -- (11.6,4.5);
\draw (12.5,4.5) -- (15.5,4.5);
\draw (12.5,5) -- (13,5);
\node at (12.7,4.8) {$E'$};
\draw (13,4.7) rectangle (14,6.8);
\node at (13.5,5.6) {$\mathsf{EPR}$};
\draw (14,5.6) -- (14.3,5.6);
\node at (14.3,5.4) {$O$};
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
\node at (15.3,4.7) {$M'$};
\node at (0.8,2) {$Y$};
\node at (0.8,1) {$X$};
%\node at (1.5,1.5) {$S$};
\node at (3.4,1.2) {$R$};
\draw (1,1) -- (1.8,1);
\draw (1,2) -- (1.8,2);
\draw (3.2,1.5) -- (4,1.5);
\draw (4,1.5) -- (4,3.9);
\draw (1.2,0.2) -- (4.6,0.2);
\draw (1.2,2.8) -- (4.6,2.8);
\draw (1.2,0.2) -- (1.2,1);
\draw (1.2,2) -- (1.2,2.8);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (1.8,0.5) rectangle (3.2,2.5);
\draw (1.6,-0.5) rectangle (4.8,7.4);
\node at (3.3,7.6) {$\enc$};
\node at (2.5,1.5) {$\nmcenc$};

\draw (9.4,-0.5) rectangle (14.5,7.2);
\node at (11.5,7.4) {$\dec$};

\node at (4.6,6.3) {$\hat{E}$};
%\draw  (2.2,1.5) -- (2.2,3.9);

\draw [dashed] (1.4,-1.4) -- (1.4,8.5);
\draw [dashed] (4.98,-1.4) -- (4.98,8.5);
\draw [dashed] (9.1,-1.4) -- (9.1,8.5);
%\draw [dashed] (10,-1.4) -- (10,7.2);
\draw [dashed] (15,-1.4) -- (15,8.5);
%\draw [dashed] (14.3,-0.8) -- (14.3,5.5);

%\draw (0.9,-1) -- (15,-1);

\node at (6.9,1.6) {$\ket{\psi}_{W_1W_2W_3}$};
\node at (1.25,-1.4) {$\sigma$};
\node at (4.8,-1.4) {$\sigma_1$};
\node at (8.9,-1.4) {$\sigma_2$};
%\node at (10.2,-1.4) {$\sigma_3$};
\node at (14.8,-1.4) {$\sigma_3$};
%\node at (14.13,-0.8) {$\rho$};

\node at (4.6,4.7) {$Z$};
\node at (8.5,4.7) {$Z'$};
\node at (4.6,3) {$Y$};
\node at (8.5,3) {$Y'$};
\node at (8.5,6.2) {$\hat{E}'$};
\draw (4.5,2.8) -- (6.3,2.8);
%\draw (7,2.8) -- (8.5,2.8);
%\draw (9.5,2.8) -- (10.5,2.8);
\draw (7.3,2.8) -- (10,2.8);

\node at (11.7,2.6) {$R'$};
\draw (11.5,2.4) -- (12,2.4);
\draw (12,2.4) -- (12,3.9);

\node at (4.6,0.4) {$X$};
\node at (8.5,0.0) {$X'$};
\draw (4.5,0.2) -- (6.3,0.2);
%\draw (7,0.2) -- (8.5,0.2);
%\draw (9.5,0.2) -- (10.5,0.2);
\draw (7.3,0.2) -- (10,0.2);

\draw (6.3,5.5) rectangle (7.3,7);
\node at (6.8,6.2) {$T$};
\draw (6.3,2) rectangle (7.3,5);
\node at (6.8,3.5) {$V$};
\draw (6.3,0) rectangle (7.3,1);
\node at (6.8,0.5) {$U$};

\node at (6.5,-0.4) {$\mathcal{A}=(U,V,T,\psi)$};
\draw (5.2,-0.8) rectangle (8.2,7.3);

\draw (5.8,3.1) ellipse (0.3cm and 2.8cm);
\node at (5.8,5.3) {$W_3$};
\draw (5.9,5.7) -- (6.3,5.7);
\draw (7.3,5.7) -- (7.45,5.7);
\node at (7.7,5.7) {$W'_3$};
\node at (5.8,2) {$W_2$};
\draw (6,2.2) -- (6.3,2.2);
\node at (7.7,2) {$W'_2$};
\draw (7.3,2.2) -- (7.5,2.2);
\node at (5.8,1) {$W_1$};
\draw (6,0.7) -- (6.3,0.7);
\node at (7.7,0.9) {$W'_1$};
\draw (7.3,0.7) -- (7.45,0.7);

%\draw (9,2.8) circle (0.5);
%\node at (9,2.8) {$\mathcal{M}$};
%\draw (9,0.2) circle (0.5);
%\node at (9,0.2) {$\mathcal{M}$};

%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (10,-0.2) rectangle (11.5,3.5);
\node at (10.8,1.5) {${\nmcdec}$};
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture}}

\caption{
3-split tamper-detection code tampering experiment.
%Split-state NMC for quantum messages.
\end{figure}

\subsection{Code Construction}
\label{subsection:tdc-components}

\subsubsection{Ingredients}

Let $\delta, \delta'>0$ be constants, $k = (1/2 -\delta -5\delta')n/5$, and $\lambda = \delta' \cdot n$.
We combine

\begin{enumerate}
\item $\nmext:\{0, 1\}^n\times \{0, 1\}^{\delta \cdot n}\rightarrow \{0, 1\}^{(1/2-\delta)n}$, a quantum secure two source non-malleable extractor with error $\epsilon_\nmext =2^{-n^{\Omega_\delta(1)}} $ from \cref{lem:qnmcodesfromnmext}.

\item  The family of $2$-design unitaries $C_R$ from \cref{lem:subclifford}.

\end{enumerate}

\subsubsection{Our candidate TDC}

Our candidate construction of quantum TDC against $\lo^3_{(e_1 = \infty,e_2 =\infty,e_3)}$ is given in \cref{fig:3splitstatetdc} along with the tampering process. We describe it explicitly in the following \cref{alg:algorithm3qtdc}. The decoding scheme, denoted as $\dec$, for the quantum TDC operates as in \Cref{alg:algorithm3qtdc_dec}.

\begin{algorithm}[h]
\setstretch{1.35}
\caption{$\Enc$: Quantum TDC against $\lo^3_{(e_1=\infty,e_2=\infty,e_3)}$ (see \cref{fig:3splitstatetdc}).}
\label{alg:algorithm3qtdc}
\KwInput{ A $k$ qubit quantum message $\sigma_{M}$ (with canonical purification $\hat{M}$). }
%\KwOutput{The product state $\rho^m_L\otimes \rho^r_R$ for some $m\in \{0, 1\}$ correlated with $b$}

\begin{algorithmic}[1]

\State Sample classical registers $X, Y$ uniformly and independently of size $n, \delta n$ respectively. Evaluate $R= \nmext(X,Y)$.

\State Prepare $\lambda =\delta' n$ EPR pairs, $\Phi^{\otimes \lambda}$, on a bipartite register $E, \hat{E}$.

\State Consider $X$ as the first share and $(Y,E)$ as the second share.

\State Let $C_R$ be the Clifford unitary picked using sampling process $\samp$ in \cref{lem:subclifford}. Apply $C_R$ on registers $(\hat{E},M)$ to generate $Z$. This is possible since $\vert R \vert = (1/2-\delta)n=5(k+\delta'n)$ from our choice of parameters. Consider $Z$ as the third share.

\item Output shares $X, (Y, {E}), Z$.
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[h]
\setstretch{1.35}
\caption{$\Dec$: }
\label{alg:algorithm3qtdc_dec}
\KwInput{ Any tampered code-state $\Lambda\circ \Enc(\sigma_{M})$ on 3 shares $(X, YE, Z)$.}
%\KwOutput{The product state $\rho^m_L\otimes \rho^r_R$ for some $m\in \{0, 1\}$ correlated with $b$}

\begin{algorithmic}[1]

\State The decoder first computes $R'= \nmext(X',Y')$.

\State Subsequently $C^\dagger_{R'}$ is applied on register $Z'$ to obtain $\hat{E}' , M'$.

\State Perform an $\epr$ test on registers $E'\hat{E}'$. This entails a binary outcome projective measurement $({\Pi = \Phi_{E\hat{E}}, \Bar{\Pi} = \id_{E \hat{E}} - \Phi_{E\hat{E}}})$.

\item An acceptance decision is made if the outcome is $\Pi = \Phi_{E\hat{E}}$. In this case, the ``replace" operation $\swap$ outputs the register $M'$.

\item If the outcome is not $\Pi$, the operation $\swap$ outputs a special symbol $\bot$ in register $M'$.

\end{algorithmic}

\end{algorithm}

\subsection{Analysis}
\label{subsection:tdc-analysis}

We represent the ``tampering experiment" in \Cref{fig:3splitstatetdc}, where a message is encoded into $\Enc$, tampered with a channel in the bounded storage model, and then decoded.

\begin{figure}[H]
\centering
\resizebox{12cm}{6cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);
\draw (0,7.4) ellipse (0.2cm and 1cm);
\draw (1,5.5) ellipse (0.3cm and 1.2cm);
\draw (3,5.9) rectangle (4.4,7.4);
\draw (11.6,5.4) rectangle (12.5,7.4);
\node at (0,6.9) {$M$};
\draw (0.2,6.9) -- (3,6.9);
\node at (1,6.4) {$\hat{E}$};
\node at (12.7,6.25) {$\hat{E}'$};
\node at (1,4.7) {$E$};
\draw (1.2,4.5) -- (4.5,4.5);
\node at (16.2,7.1) {$M'$};

%\draw (0.8,0.5) ellipse (0.3cm and 1.5cm);
%\node at (0.8,-0.7) {$\hat{R}$};
\node at (3.6,6.6) {$C_R$};
\node at (12.1,6.1) {$C^\dagger_{R'}$};
\node at (0,8) {$\hat{M}$};
\node at (16.2,8) {$\hat{M}$};

\draw (0.2,8) -- (16,8);
\draw (1.2,6.5) -- (3,6.5);
\draw (4.4,6.5) -- (6.3,6.5);
\draw (7.3,6.5) -- (11.6,6.5);
\draw (12.5,6.5) -- (13,6.5);
\draw (12.5,7.1) -- (14.2,7.1);

%\node at (14.5,4.3) {$S'$};
%\draw (0.2,4.5) -- (3,5.5);
\draw (4.4,4.5) -- (6.3,4.5);
\draw (7.3,4.5) -- (13,4.5);
%\draw (12.5,4.5) -- (15.5,4.5);
%\draw (12.5,5) -- (13,5);
\node at (12.7,4.7) {$E'$};
\draw (13,4.2) rectangle (14,6.8);
\node at (14.8,6.8) {$\mathsf{Rep}$};
\draw (14.2,6) rectangle (15.4,7.4);
\draw (15.4,6.6) -- (16,6.6);

\node at (13.5,5.4) {$\mathsf{EPR}$};
\draw (14,5.6) -- (14.6,5.6);
\draw (14.6,6) -- (14.6,5.6);
\node at (14.8,5.4) {$O$};
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%\node at (15.3,4.7) {$M'$};
\node at (0.8,2) {$Y$};
\node at (0.8,1) {$X$};
%\node at (1.5,1.5) {$S$};
\node at (3.4,1.2) {$R$};
\draw (1,1) -- (1.8,1);
\draw (1,2) -- (1.8,2);
\draw (3.2,1.5) -- (4,1.5);
\draw (4,1.5) -- (4,5.9);
\draw (1.2,0.2) -- (4.6,0.2);
\draw (1.2,2.8) -- (4.6,2.8);
\draw (1.2,0.2) -- (1.2,1);
\draw (1.2,2) -- (1.2,2.8);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (1.8,0.5) rectangle (3.2,2.5);
\draw (1.6,-0.5) rectangle (4.8,7.6);
\node at (3.3,7.8) {$\enc$};
\node at (2.5,1.5) {$\nmcenc$};

\draw (9.4,-0.5) rectangle (15.6,7.6);
\node at (11.5,7.8) {$\dec$};

\node at (4.6,6.3) {$Z$};
%\draw  (2.2,1.5) -- (2.2,3.9);

\draw [dashed] (1.4,-1.4) -- (1.4,8.5);
\draw [dashed] (4.98,-1.4) -- (4.98,8.5);
\draw [dashed] (9.1,-1.4) -- (9.1,8.5);
%\draw [dashed] (10,-1.4) -- (10,7.2);
\draw [dashed] (15.8,-1.4) -- (15.8,8.5);
%\draw [dashed] (14.3,-0.8) -- (14.3,5.5);

%\draw (0.9,-1) -- (15,-1);

\node at (6.9,1.6) {$\ket{\psi}_{W_1W_2W_3}$};
\node at (1.25,-1.4) {$\sigma$};
\node at (4.8,-1.4) {$\sigma_1$};
\node at (8.9,-1.4) {$\sigma_2$};
%\node at (10.2,-1.4) {$\sigma_3$};
\node at (15.6,-1.4) {$\eta$};
%\node at (14.13,-0.8) {$\rho$};

\node at (4.6,4.7) {$E$};
\node at (8.5,4.7) {$E'$};
\node at (4.6,3) {$Y$};
\node at (8.5,3) {$Y'$};
\node at (8.5,6.2) {$Z'$};
\draw (4.5,2.8) -- (6.3,2.8);
%\draw (7,2.8) -- (8.5,2.8);
%\draw (9.5,2.8) -- (10.5,2.8);
\draw (7.3,2.8) -- (10,2.8);

\node at (11.7,2.6) {$R'$};
\draw (11.5,2.4) -- (12,2.4);
\draw (12,2.4) -- (12,5.4);

\node at (4.6,0.4) {$X$};
\node at (8.5,0.0) {$X'$};
\draw (4.5,0.2) -- (6.3,0.2);
%\draw (7,0.2) -- (8.5,0.2);
%\draw (9.5,0.2) -- (10.5,0.2);
\draw (7.3,0.2) -- (10,0.2);

\draw (6.3,5.5) rectangle (7.3,7);
\node at (6.8,6.2) {$T$};
\draw (6.3,2) rectangle (7.3,5);
\node at (6.8,3.5) {$V$};
\draw (6.3,0) rectangle (7.3,1);
\node at (6.8,0.5) {$U$};

\node at (6.5,-0.4) {$\mathcal{A}=(U,V,T,\psi)$};
\draw (5.2,-0.8) rectangle (8.2,7.3);

\draw (5.8,3.1) ellipse (0.3cm and 2.8cm);
\node at (5.8,5.3) {$W_3$};
\draw (5.9,5.7) -- (6.3,5.7);
\draw (7.3,5.7) -- (7.45,5.7);
\node at (7.7,5.7) {$W'_3$};
\node at (5.8,2) {$W_2$};
\draw (6,2.2) -- (6.3,2.2);
\node at (7.7,2) {$W'_2$};
\draw (7.3,2.2) -- (7.5,2.2);
\node at (5.8,1) {$W_1$};
\draw (6,0.7) -- (6.3,0.7);
\node at (7.7,0.9) {$W'_1$};
\draw (7.3,0.7) -- (7.45,0.7);

%\draw (9,2.8) circle (0.5);
%\node at (9,2.8) {$\mathcal{M}$};
%\draw (9,0.2) circle (0.5);
%\node at (9,0.2) {$\mathcal{M}$};

%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (10,-0.2) rectangle (11.5,3.5);
\node at (10.8,1.5) {${\nmcdec}$};
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture}}

\caption{
A quantum TDC against $\lo^3_{(e_1=\infty, e_2=\infty, e_3)}$ along with  tampering process.
%Split-state NMC for quantum messages.
\end{figure}

In this section, we prove two key results about our code construction. Our main result is that the code described above is a secure tamper-detection code in the bounded storage model:

\begin{theorem}[Tamper Detection]\label{theorem:tdc-loa}
Consider \cref{fig:3splitstatetdc}.  $(\Enc, \Dec)$ as shown in \cref{fig:3splitstatetdc} is a quantum TDC against $\lo^3_{(\infty, \infty, e_3)}$ with error $\eps' \leq 2 \eps_{\nmext}  +6\cdot 2^{e_3- \lambda}$.
\end{theorem}

The proof of which we defer to \Cref{subsubsection:proof-of-tdc-loa}. By instantiating \cref{theorem:tdc-loa} with the ingredients above, we obtain the following explicit construction.
\begin{corollary}
For any constant $0 < \gamma < 1/12$, there exists an efficient quantum TDC of blocklength $n$ and rate $\frac{1-12\cdot \gamma}{11}$ secure against $\lo^3_{(\infty, \infty, \gamma \cdot n)}$ with error $2^{-n^{\Omega(1)}}$.
\end{corollary}

We further prove that our construction inherits quite strong secret sharing properties, which we extensively leverage in our future applications to ramp secret sharing.

\begin{theorem}[3-out-of-3 Secret Sharing]\label{corr:2nmssq}
$(\enc,\dec)$ from \cref{theorem:tdc-loa} is also a $3$-out-of-$3$ secret sharing scheme with error $\epsilon'$. In fact, any two shares of the quantum TDC are $\epsilon'$-close to the maximally mixed state.
\end{theorem}
\begin{proof}

Note that $\enc(.)$ in \cref{fig:3splitstatetdc} first samples an independent $(X,Y)$ and then generates $R= \nmext(X,Y)$. It also independently prepares $\lambda = \delta' n $ EPR pairs $\Phi_{E \hat{E}}$. It follows from the strong-extraction property of $\nmext$ (see \cref{lem:qnmcodesfromnmext}) that
\[ RX \approx_{\eps_\nmext} U_R \otimes U_X \quad ; \quad RY \approx_{\eps_\nmext} U_R \otimes U_Y .\]

Recall that the three shares are $(X, YE, Z = C_R(\hat{E} M) C^\dagger_R)$. Thus for every message ${\sigma_{M\hat{M}}}$, using the fact that Cliffords are 1-Designs (\cref{fact:notequal}), and the approximate sampler $\samp$ from \cref{lem:subclifford}, we have
\begin{equation}\label{eqfd}
(\enc( \sigma))_{\hat{M}ZX}  \approx_{\eps_\nmext+2^{1-\lambda}} \sigma_{\hat{M}} \otimes  U_{Z} \otimes U_X \quad ; \quad  (\enc( \sigma))_{\hat{M}ZYE}  \approx_{\eps_\nmext+2^{1-\lambda}} \sigma_{\hat{M}} \otimes  U_{Z} \otimes U_Y \otimes U_E.
\end{equation}
Since $|Z|>\lambda=\delta' n $. Moreover, since $(X,Y)$ are sampled independently, we also have
\begin{equation}\label{eqfdsfvf}
(\enc( \sigma))_{\hat{M}XYE}  =\sigma_{\hat{M}} \otimes  U_{X} \otimes U_Y \otimes U_E .
\end{equation}
\end{proof}

\subsubsection{Proof of \Cref{theorem:tdc-loa}}
\label{subsubsection:proof-of-tdc-loa}

To show that $(\enc,\dec)$ is an $\eps'$-secure quantum TDC, it suffices to show that for every $\mathcal{A}=(U,V,T,\psi_{W_1W_2W_3})$ it holds that (in \cref{fig:3splitstatetdc})
\begin{equation}\label{eq:finalgoal}
\eta_{\hat{M}M'} \approx_{\eps'} p_{\mathcal{A}} \sigma_{\hat{M}M}  + (1-p_\mathcal{A}) (\sigma_{\hat{M}} \otimes  {\bot}_{M'}),
\end{equation}where $p_{\mathcal{A}}$ depends only on the tampering adversary $\cA$. To do so, we proceed similarly to \Cref{section:tsplit-td}, where we ``delayed" the tampering channel on the extra $(t+1)$st share. In \cref{fig:3splitstatetdc1} below, we represent the same tampering experiment as \cref{fig:3splitstatetdc}, except for the the delayed action of the tampering map $T$. We show that \cref{eq:finalgoal} holds in \cref{fig:3splitstatetdc1}, which completes the proof.

\begin{figure}[H]
\centering
\resizebox{12cm}{6cm}{
\begin{tikzpicture}
%\draw (1,1.2) ellipse (0.3cm and 2.5cm);
%        \node at (1,3.3) {$R$};
%          \node at (5.2,3.7) {$R$};
%      \node at (14.5,3.7) {$R$};
%      \draw (1.2,3.5) -- (3,3.5);
%       \draw (5,3.5) -- (15,3.5);
%\draw (10,3.5) -- (15,3.5);
%\node at (1,-0.8) {$\hat{R}$};
%\node at (14.5,-0.8) {$\hat{R}$};
%\draw (1.2,-1) -- (15,-1);

%\draw (1,5) ellipse (0.2cm and 1cm);
%\node at (1,5.5) {$\hat{S}$};
%\node at (14.5,5.5) {$\hat{S}$};
%\draw (1.2,5.7) -- (15,5.7);
\draw (0,7.4) ellipse (0.2cm and 1cm);
\draw (1,5.5) ellipse (0.3cm and 1.2cm);
\draw (9,5.9) rectangle (9.8,7.4);
\draw (11.6,5.4) rectangle (12.5,7.4);
\node at (0,6.9) {$M$};
\draw (0.2,6.9) -- (9,6.9);
\node at (1,6.4) {$\hat{E}$};
\node at (12.7,6.25) {$\hat{E}'$};
\node at (1,4.7) {$E$};
\draw (1.2,4.5) -- (4.5,4.5);
\node at (16.2,7.1) {$M'$};

%\draw (0.8,0.5) ellipse (0.3cm and 1.5cm);
%\node at (0.8,-0.7) {$\hat{R}$};
\node at (9.3,6.6) {$C_R$};
\node at (12.1,6.1) {$C^\dagger_{R'}$};
\node at (0,8) {$\hat{M}$};
\node at (16.2,8) {$\hat{M}$};

\node at (10.6,6.2) {$T$};

\draw (0.2,8) -- (16,8);
\draw (1.2,6.5) -- (9,6.5);
%\draw (4.4,6.5) -- (6.3,6.5);
\draw (11,6.5) -- (11.6,6.5);
\draw (9.8,6.5) -- (10.1,6.5);
\draw (12.5,6.5) -- (13,6.5);
\draw (12.5,7.1) -- (14.2,7.1);

%\node at (14.5,4.3) {$S'$};
%\draw (0.2,4.5) -- (3,5.5);
\draw (4.4,4.5) -- (6.3,4.5);
\draw (7.3,4.5) -- (13,4.5);
%\draw (12.5,4.5) -- (15.5,4.5);
%\draw (12.5,5) -- (13,5);
\node at (12.7,4.7) {$E'$};
\draw (13,4.2) rectangle (14,6.8);
\node at (14.8,6.8) {$\mathsf{Rep}$};
\draw (14.2,6) rectangle (15.4,7.4);
\draw (15.4,6.6) -- (16,6.6);

\node at (13.5,5.4) {$\mathsf{EPR}$};
\draw (14,5.6) -- (14.6,5.6);
\draw (14.6,6) -- (14.6,5.6);
\node at (14.8,5.4) {$O$};
%\draw (10,4.5) -- (15,4.5);
%\node at (5.2,4.7) {$S$};
%\node at (15.3,4.7) {$M'$};
\node at (0.8,2) {$Y$};
\node at (0.8,1) {$X$};
%\node at (1.5,1.5) {$S$};
\node at (3.4,1.2) {$R$};
\draw (1,1) -- (1.8,1);
\draw (1,2) -- (1.8,2);
\draw (3.2,1.5) -- (4,1.5);
\draw (4,1.5) -- (4,5.5);
\draw (4,5.5) -- (5.2,5.5);
\draw [dashed] (5.2,5.5) -- (6.5,5.5);
\draw (6.5,5.5) -- (9.3,5.5);
\draw (9.3,6) -- (9.3,5.5);

\draw (1.2,0.2) -- (4.6,0.2);
\draw (1.2,2.8) -- (4.6,2.8);
\draw (1.2,0.2) -- (1.2,1);
\draw (1.2,2) -- (1.2,2.8);
%\node at (2.0,0) {$\ketbra{0^{n}}$};
%\draw (2.8,0) -- (3,0);
\draw (1.8,0.5) rectangle (3.2,2.5);
%\draw (1.6,-0.5) rectangle (4.8,7.6);
%\node at (3.3,7.8) {$\enc$};
\node at (2.5,1.5) {$\nmcenc$};

%\draw (9.4,-0.5) rectangle (15.6,7.6);
\node at (11.5,7.8) {$\dec$};

%\node at (4.6,6.3) {$Z$};
%\draw  (2.2,1.5) -- (2.2,3.9);

\draw [dashed] (1.4,-1.4) -- (1.4,8.5);
%\draw [dashed] (4.98,-1.4) -- (4.98,8.5);
\draw [dashed] (8.9,-1.4) -- (8.9,8.5);
\draw [dashed] (10,-1.4) -- (10,8.5);
\draw [dashed] (11.1,-1.4) -- (11.1,8.5);
\draw [dashed] (12.8,-1.4) -- (12.8,8.5);
\draw [dashed] (15.8,-1.4) -- (15.8,8.5);
%\draw [dashed] (14.3,-0.8) -- (14.3,5.5);

%\draw (0.9,-1) -- (15,-1);

\node at (6.9,1.6) {$\ket{\psi}_{W_1W_2W_3}$};
\node at (1.25,-1.4) {$\sigma$};
%\node at (4.8,-1.4) {$\sigma_1$};
\node at (8.9,-1.4) {$\tau$};
\node at (10.2,-1.4) {$\nu$};
\node at (11.3,-1.4) {$\chi$};
\node at (12.6,-1.4) {$\mu$};
\node at (15.6,-1.4) {$\eta$};
%\node at (14.13,-0.8) {$\rho$};

\node at (4.6,4.7) {$E$};
\node at (8.5,4.7) {$E'$};
\node at (4.6,3) {$Y$};
\node at (7.5,3) {$Y'$};
\node at (11.3,6.7) {$Z'$};
\draw (4.5,2.8) -- (6.3,2.8);
%\draw (7,2.8) -- (8.5,2.8);
%\draw (9.5,2.8) -- (10.5,2.8);
\draw (7.3,2.8) -- (8,2.8);

\node at (11.7,2.6) {$R'$};
\draw (8.7,2.4) -- (12,2.4);
\draw (12,2.4) -- (12,5.4);

\node at (4.6,0.4) {$X$};
\node at (7.5,0.0) {$X'$};
\draw (4.5,0.2) -- (6.3,0.2);
%\draw (7,0.2) -- (8.5,0.2);
%\draw (9.5,0.2) -- (10.5,0.2);
\draw (7.3,0.2) -- (8,0.2);

\draw (10.1,5.5) rectangle (11,7);
%\node at (6.8,6.2) {$T$};
\draw (6.3,2) rectangle (7.3,5);
\node at (6.8,3.5) {$V$};
\draw (6.3,0) rectangle (7.3,1);
\node at (6.8,0.5) {$U$};

\node at (6.5,-0.4) {$\mathcal{A}=(U,V,T,\psi)$};
%\draw (5.2,-0.8) rectangle (8.2,7.3);

\draw (5.8,3.1) ellipse (0.3cm and 2.8cm);
\node at (5.8,5.3) {$W_3$};
\draw (5.9,5.7) -- (10.1,5.7);
\draw (11,5.7) -- (11.25,5.7);
\node at (11.3,5.7) {$W'_3$};
\node at (5.8,2) {$W_2$};
\draw (6,2.2) -- (6.3,2.2);
\node at (7.7,2) {$W'_2$};
\draw (7.3,2.2) -- (7.5,2.2);
\node at (5.8,1) {$W_1$};
\draw (6,0.7) -- (6.3,0.7);
\node at (7.7,0.9) {$W'_1$};
\draw (7.3,0.7) -- (7.45,0.7);

%\draw (9,2.8) circle (0.5);
%\node at (9,2.8) {$\mathcal{M}$};
%\draw (9,0.2) circle (0.5);
%\node at (9,0.2) {$\mathcal{M}$};

%\draw (8,-0.5) rectangle (10,1.2);
%\draw (8,1.5) rectangle (10,3.2);
%\node at (9,1.5) {$2\mhyphen\nmext$};

\draw (8,-0.2) rectangle (8.7,3.5);
\node at (8.3,-0.5) {${\nmcdec}$};
%\node at (12.5,1.6) {$ \mathcal{M}= \{ \ketbra{0^{2n}},$};
%\node at (12.5,1) {$ \id- \ketbra{0^{2n}} \}$};

\end{tikzpicture}}

\caption{
Analysis of quantum TDC against $\lo^3_{(e_1=\infty, e_2=\infty, e_3)}$.
%Split-state NMC for quantum messages.
\end{figure}

\begin{proof}
Consider the state ${\tau}$ in~\cref{fig:3splitstatetdc1}. Note ${\tau}_{\hat{M}M} \equiv \sigma_{\hat{M}M}$ is a pure state (thus independent of other registers in ${\tau}$) and
\[{\tau} = (\nmext_{X'Y'} \otimes \nmext_{XY})  \left( (U \otimes V)  (\sigma \otimes \ketbra{\psi}_{W_1W_2W_3}) \right). \]

Our analysis will proceed by cases, depending on whether the $X$ and $Y$ registers are modified by the tampering experiment in \cref{fig:3splitstatetdc1} (i.e., $XY\neq X' Y'$) or not.
To this end, we consider two different conditionings of $\tau$ based on these two cases. Let $\tau^1$ be the state if the tampering adversary ensures $(XY=X'Y')$ and $\tau^0$ be the state conditioned on $(XY \ne X'Y')$.

Using \cref{lem:qnmcodesfromnmext}, state $\tau$ can be written as convex combination of two states $\tau^1$ and $\tau^0$ such that:
\begin{equation}\label{eq:2classical198}
(\tau)_{{R}R'W_2'W_3E'\hat{E}M\hat{M}}= p_{\sm} (\tau^1)_{{R}R'W_2'W_3E' \hat{E}M\hat{M}} + (1-p_{\sm}) (\tau^0)_{{R}R'W_2'W_3E' \hat{E}M\hat{M}},
\end{equation}
where $p_\sm$ depends only on the adversary $\mathcal{A}'=(U,V,\psi_{W_1W_2W_3})$. In case $(XY=X'Y')$, the key is recovered $\Pr({R} =R')_{\tau^1}=1$. \cref{lem:qnmcodesfromnmext} guarantees the non-malleability of the secret key $R$:
\begin{multline}\label{eq:2classical1}
p_{\sm} \Vert (\tau^1)_{{R}W_2'W_3E' \hat{E}M\hat{M}} -  U_{\vert R \vert} \otimes (\tau^1)_{W_2'W_3E' \hat{E}M\hat{M}} \Vert_1 + \\ (1-p_{\sm})\Vert (\tau^0)_{{R}R'W_2'W_3E' \hat{E}M\hat{M}} -  U_{\vert R \vert} \otimes (\tau^0)_{R'W_2'W_3E' \hat{E}M\hat{M}} ) \Vert_1  \leq \eps_{\nmext}.
\end{multline}

Suppose $\Upsilon$ denotes the CPTP map from registers ${R}R'W_3E' \hat{E}M\hat{M}$ to $M'\hat{M}$ (i.e. $\Upsilon$ maps state $\tau$ to $\eta$) in~\cref{fig:3splitstatetdc1}. We present two claims (proved in the next subsections) which allow us to conclude the proof. The first one stipulates that if the key is not recovered, the Bell basis measurement rejects with high probability:

\begin{claim}[Key \textit{not} recovered]\label{claim:dfskjboca}
$ \Upsilon(U_{\vert R \vert} \otimes (\tau^0)_{R'W_2'W_3E' \hat{E}M\hat{M}})
\approx_{2 \cdot  2^{ \vert W_3 \vert - \vert E \vert  }} \sigma_{\hat {M}}  \otimes \bot_{M'}$ .
\end{claim}

In the second, if the key is recovered, then the 2-design functions as an authentication code. In this manner, we either recover the original message, or reject:

\begin{claim}[Key recovered]\label{claim:nekjbs2}
$ \Upsilon(U_{\vert R \vert} \otimes (\tau^1)_{W_2'W_3E' \hat{E}M\hat{M}})
\approx_{ \frac{2}{(4^{\vert E \vert + \vert M \vert}-1)} + \frac{2}{2^{\vert E \vert}} }  p\sigma_{\hat {M}M}  + (1-p) \sigma_{\hat {M}}  \otimes \bot_{M'}$ . Furthermore, $p$ depends only on adversary $\mathcal{A} = (U,V,T, \ket{\psi}_{W_1W_2W_3})$.
\end{claim}

We are now in a position to conclude the proof. First, leveraging \cref{eq:2classical1}
\begin{gather}
\eta_{M'\hat{M}} =\Upsilon( (\tau)_{{R}R'W_3E' \hat{E}M\hat{M}})\nonumber = p_{\sm}  \Upsilon((\tau^1)_{{R}R'W_3E' \hat{E}M\hat{M}})
+ (1-p_{\sm})  \Upsilon((\tau^0)_{{R}R'W_3E' \hat{E}M\hat{M}}) \\
\approx_{\eps_{\nmext}} p_{\sm}  \Upsilon(U_{\vert R \vert} \otimes (\tau^1)_{W_2'W_3E' \hat{E}M\hat{M}} ) + (1-p_{\sm}) \Upsilon(U_{\vert R \vert} \otimes (\tau^0)_{R'W_2'W_3E' \hat{E}M\hat{M}} )
\end{gather}
Next, by applying \cref{claim:nekjbs2}, proceeded by \cref{claim:dfskjboca}:
\begin{gather}
\approx_{ \frac{2}{(4^{\vert E \vert + \vert M \vert}-1)} + \frac{2}{2^{\vert E \vert}} } p_{\sm}\cdot (p\cdot \sigma_{M\hat{M}}+  (1-p) (\bot_{{M'}} \otimes \sigma_{\hat{M}}))+ (1-p_{\sm}) \Upsilon(U_{\vert R \vert} \otimes (\tau^0)_{R'W_2'W_3E' \hat{E}M\hat{M}} )\\
\approx_{2 \cdot \frac{2^{\vert W_3 \vert}}{ 2^{\vert E \vert}} } p_{\sm}\cdot p\cdot \sigma_{M\hat{M}}+  p_{\sm}  (1-p) (\bot_{{M'}} \otimes \sigma_{\hat{M}})  + (1-p_{\sm}) \bot_{M'} \otimes \sigma_{\hat{M}}
\end{gather}

The total error is thus $\leq \eps_\nmext + 6\cdot 2^{|W_3|-|E|}$. The observation that $p_\sm$ and $p$ depend only on the adversary $\mathcal{A} = (U,V,T ,\ket{\psi}_{W_1W_2W_3})$ completes the proof.

\end{proof}

\subsubsection{Proof of \cref{claim:dfskjboca}}

\begin{proof}
Let $\nu^0, \chi^0, \mu^0$ be the intermediate states and $\eta^0$ be the final state when we run the CPTP map $\Upsilon$ on $U_{\vert R \vert} \otimes \tau^0_{R'W_2'W_3E' \hat{E}M\hat{M}}$ (see \Cref{fig:3splitstatetdc1}). Since, $\tau^0_{R'W_2'W_3E' \hat{E}M\hat{M}} = \tau^0_{R'W_2'W_3E' \hat{E}}  \otimes \sigma_{M\hat{M}}$, using~\cref{fact:notequal} (Cliffords are 1-Designs) it follows that in the state $\nu^0$ the two registers $E$ and $\hat{E}$ are decoupled:

\begin{equation}
\nu^0_{R'W_2'W_3E' \hat{M} \hat{E}M} = \tau^0_{R'W_2'W_3E'  } \otimes \sigma_{\hat{M}} \otimes U_{\hat{E}M}
\end{equation}

We fix $R'=r'$ and argue that we output $\bot_{M'}$ with high probability for every such fixing. Let
$\tau^{0,r'} \defeq \tau^{0} \vert (R'=r')$ and similarly define $\nu^{0,r'} , \chi^{0,r'} $, $\mu^{0,r'} $ and $\eta^{0,r'}$. Note $\nu^{0,r'}_{W_2'W_3E' \hat{M} \hat{E}M} = \tau^{0,r'}_{W_2'W_3E'  } \otimes \sigma_{\hat{M}} \otimes U_{\hat{E}M} $. This implies that the Schmidt number of the state $\nu^{0,r'}$ across the bipartition $(W_2'E', W_3\hat{E}M \hat{M})$ is $\leq 2^{\vert W_3 \vert}$.

The states $\chi^{0, r'}, \mu^{0, r'}$ can be prepared from $\nu^{0,r'}$ using just local operations on each side of the cut $(W_2'E' , W_3\hat{E}M \hat{M})$. From \cref{prop:schimidt}, their Schmidt numbers are at most $2^{\vert W_3 \vert}$. Moreover, again by \cref{prop:schimidt}, the reduced density matrix $\mu^{0,r'}_{E'\hat{E}}$ also has Schmidt number at most $2^{\vert W_3 \vert}$. \Cref{claim:tss-bellbasis} then ensures that the $\epr$ test on state $\mu^{0,r'}$ fails with probability at least $1-2^{\vert W_3 \vert-\vert E  \vert}$. We conclude $\eta^{0,r'}_{ \hat{M} M'} \approx_{ 2 \cdot 2^{\vert W_3 \vert-\vert E  \vert} }  \sigma_{\hat{M}} \otimes \bot_{M'}$.

Since the above argument works for every fixing of $R'=r'$ and $\eta^0 = \mathbb{E}_{r'} \eta^{0,r'}$, we have the desired.

\suppress{We fix $R'=r'$ and argue that we output $\bot_{M'}$ with high probability for every such fixing. Let
$\tau^{0,r'} \defeq \tau^{0} \vert (R'=r')$ and we similarly define $\nu^{0,r'} , \chi^{0,r'} $, $\mu^{0,r'} $ and $\eta^{0,r'}$. Note $\nu^{0,r'}_{W_2'W_3E' \hat{M} \hat{E}M} = \tau^{0,r'}_{W_2'W_3E'  } \otimes \sigma_{\hat{M}} \otimes U_{\hat{E}M} $. This implies that the Schmidt number of the state $\nu^{0,r'}$ across the bipartition $(W_2'W_3E' \hat{M},\hat{E}M )$ is $1$.

Using \cref{prop:schimidt2}, we can conclude that Schmidt number of the state $\nu^{0,r'}$ across the bipartition $(W_2'E' \hat{M},W_3\hat{E}M )$ is atmost $2^{\vert W_3 \vert}$. Now consider the state $\chi^{0,r'}$, i.e. $\chi^{0,r'} = T_{\hat{E}MW_3} (\nu^{0,r'})$. Using \cref{prop:schimidt}, we can conclude the Schmidt number of the state $\chi^{0,r'}$ across the biparition $(W_2'E' \hat{M},\hat{E}'M'W'_3 )$ is atmost $2^{\vert W_3 \vert}$. Using \cref{prop:schimidt} again, we further have that Schmidt number of the state $\mu^{0,r'}$ across the bipartition $(W_2'E' \hat{M},\hat{E}'M'W'_3 )$ is at most $2^{\vert W_3 \vert}$. Using the same proposition again, Schmidt number of the state $\mu^{0,r'}$ across the bipartition $(E' ,\hat{E}' )$ is atmost $2^{\vert W_3 \vert}$.

\Cref{claim:tss-bellbasis} then ensures that the $\epr$ test fails with probability at least $1-2^{\vert W_3 \vert-\vert E  \vert}$ on state $\mu^{0,r'}$. Thus, we conclude
$\eta^{0,r'}_{ \hat{M} M'} \approx_{ 2 \cdot 2^{\vert W_3 \vert-\vert E  \vert} }  \sigma_{\hat{M}} \otimes \bot_{M'}$.

Since the above argument works for every fixing of $R'=r'$ and $\eta^0 = \mathbb{E}_{r'} \eta^{0,r'}$, we have the desired. }

\end{proof}

\subsubsection{Proof of \cref{claim:nekjbs2}}

\begin{proof}

Let $\nu^1, \chi^1, \mu^1$ be the intermediate states and $\eta^1$ be the final state when we run the CPTP map $\Upsilon$ on $U_{\vert R \vert} \otimes \tau^1_{W_2'W_3E' \hat{E}M\hat{M}}$ (see \Cref{fig:3splitstatetdc1}).

Note we have $(\tau^1)_{W_2'W_3E' \hat{E}M\hat{M}} = (\tau^1)_{W_2'W_3E' \hat{E}} \otimes \sigma_{M \hat{M}}$. Consider the state $\mu^1$, i.e. the state obtained by the action of $C_R$ on $\tau^1$ followed by CPTP map $T$, followed by $C^\dagger_R$. Using, \cref{lem:twirl-wsi}, we have
\[\mu^1_{\hat{M}M'\hat{E}' E' W'_3} \approx_{2/(4^{\vert M \vert +\vert \hat{E} \vert} -1)}  T_1 ( (\tau^1)_{\hat{M}M\hat{E}E'W_3}  ) + T_2 (( \tau^1)_{\hat{M} E'W_3 } \otimes U_{M \hat{E}}  ), \]
where $T_1(.) : \cL( \cH_{W_3}) \to  \cL( \cH_{W'_3})$ ,  $T_2(.) : \cL( \cH_{W_3}) \to  \cL( \cH_{W'_3})$ are CP maps such that $T_1 +T_2$ is trace preserving and they depend only on adversary CPTP map $T(.)$. Note both \[  T_1 ( (\tau^1)_{\hat{M}M\hat{E}E'W_3}  ) \quad ; \quad T_2 (( \tau^1)_{\hat{M} E'W_3 } \otimes U_{M \hat{E}}  ) \] are sub-normalized density operators. Let $p_1 \defeq \Tr( T_1 ( (\tau^1)_{\hat{M}M\hat{E}E'W_3}  ) ) $. Let  \[ \mu^{1,0}  \defeq  \frac{1}{p_1} T_1 ( (\tau^1)_{\hat{M}M\hat{E}E'W_3}  )  \quad ; \quad  \mu^{1,1}  \defeq  \frac{1}{1-p_1} T_2 (( \tau^1)_{\hat{M} E'W_3 } \otimes U_{M \hat{E}}  ). \]
Note $\mu^1  \approx_{2/(4^{\vert M \vert + \vert \hat{E} \vert} -1)}  p_1 \mu^{1,0} + (1-p_1)\mu^{1,1}$. Let the final states be $\eta^{1,0}$, $\eta^{1,1}$ when we run the $\epr$ test followed by $\mathsf{Rep}$ on $\mu^{1,0}$, $\mu^{1,1}$ respectively. Since,  $\mu^1  \approx_{2/(4^{\vert M \vert + \vert \hat{E} \vert}-1)}  p_1 \mu^{1,0} + (1-p_1)\mu^{1,1}$, we conclude,
\begin{equation}\label{claim:eq1djfvsissdd}
\eta^1  \approx_{2/(4^{\vert M \vert + \vert \hat{E} \vert}-1)}  p_1 \eta^{1,0} + (1-p_1)\eta^{1,1}.
\end{equation}
In the first case, since  $(\mu^{1,0})_{W'_3E' \hat{E}'M'\hat{M}} = (\mu^{1,0})_{W'_3E' \hat{E}'} \otimes \sigma_{M \hat{M}}$, we can conclude that
\begin{equation}\label{claim:eq1djfvsi}
\eta^{1,0} = p_2 \sigma_{ \hat{M}M} + (1-p_2) \sigma_{\hat{M}} \otimes \bot_{M'},
\end{equation}
and furthermore $p_2$ depends only on CP map $T_1(.)$ and state $\tau^1$, which further depends only on tampering adversary $\mathcal{A}$.

In the second case, since  $(\mu^{1,1})_{W'_3E' \hat{E}M'\hat{M}} = (\mu^{1,1})_{W'_3E' } \otimes U_{\hat{E}'M} \otimes  \sigma_{ \hat{M}}$, we can conclude
\begin{equation}\label{claim:eq1djfvsiw}
\eta^{1,1}_{\hat{M}M'} \approx_{ 2 \cdot 2^{-\vert E \vert}} \sigma_{\hat{M}} \otimes \bot_{M'},
\end{equation}
using \cref{claim:tss-bellbasis} as $\epr$ test rejects with probability atleast $1- 2^{-\vert E \vert}$.

Combining \cref{claim:eq1djfvsissdd}, \cref{claim:eq1djfvsi} and  \cref{claim:eq1djfvsiw}, we have the following:
\begin{align*}
&\Upsilon(U_{\vert R \vert} \otimes (\tau^1)_{W_2'W_3E' \hat{E}M\hat{M}})  \\
&=  \eta^{1}_{\hat{M}M'} \\
&  \approx_{2/(4^{\vert M \vert + \vert \hat{E} \vert}-1)}  p_1 \eta^{1,0} + (1-p_1)\eta^{1,1}  \\
& = p_1p_2 \sigma_{\hat{M}M} + p_1 (1-p_2) \sigma_{\hat{M}} \otimes \bot_{M'} +(1- p_1) \eta^{1,1}  \\
& \approx_{2 \cdot 2^{-\vert E \vert}}  p_1 \cdot p_2 \sigma_{\hat{M}M} + p_1 (1-p_2) \sigma_{\hat{M}} \otimes \bot_{M'} +(1- p_1) \sigma_{\hat{M}} \otimes \bot_{M'} \\
&= p_1 \cdot p_2 \sigma_{\hat{M}M} + (1-p_1 \cdot p_2) \sigma_{\hat{M}} \otimes \bot_{M'}.
\end{align*}

Considering $p =p_1 \cdot p_2  $, we have the desired. Through $p_1, p_2$, $p$ depends only on tampering adversary $\mathcal{A}$.
\end{proof}

\newpage

\section{Tamper-Detecting Secret Sharing Schemes}
\label{section:tamper-detecting-secret-sharing}

In this section, we prove our main result on the construction of secret sharing schemes which detect local tampering, restated below. We refer the reader to \Cref{subsubsection:prelim-tamper-detecting-ss} for the definition of tamper-detecting secret sharing schemes.

\begin{theorem}[\cref{theorem:results-lo-ss}, restatement]
For every $p, t$ s.t. $4 \leq t \leq p-2$, there exists a $(p, t, 0, 0)$ secret sharing scheme for $k$ bit messages which is $(\lo^p, t+2, 2^{-\max(p, k)^{\Omega(1)}})$-tamper detecting.
\end{theorem}

In other words, no $t-1$ shares reveal any information about the message, any $t$ honest shares uniquely determine the message, and one can detect $\lo$ tampering on any $(t + 2)$ shares.

We organize this section as follows. We begin in \Cref{subsection:tdss-components} by introducing the relevant code components, overviewing the construction, as well as presenting the construction and analysis of the ``triangle gadgets" discussed in \Cref{subsubsection:overview-td-ss}. Next, in \Cref{subsection:tdss-construction} we present our secret sharing scheme, and in the subsequent \Cref{subsection:tdss-analysis} we present its analysis.

\subsection{Code Components and the Triangle Gadget}
\label{subsection:tdss-components}

In \Cref{subsubsection:tdss-ingredients}, we describe the ingredients in our secret sharing scheme, in \Cref{subsubsection:triangle} we introduce the ``triangle gadget", and in \Cref{subsubsection:analysis-triangle} we prove that it inherits two basic properties: (weak) tamper detection, and 3-out-of-3 secret sharing.

\subsubsection{Ingredients and Overview}
\label{subsubsection:tdss-ingredients}

We combine:

\begin{enumerate}

\item $(\share_{\lrss}, \rec_\lrss)$: A classical $(p, t, 0,0)$-secret sharing scheme which is $\epsilon_{lr}$-leakage resilient to $\mu$ qubits of the $3$-local leakage model $\mathcal{F}_{3, \mu}^{p, t}$, such as that of \Cref{theorem:lrss-local-leakage-prelim}.

For basic definitions of leakage-resilient secret sharing, see \Cref{subsubsection:prelim-lrss}.

\item $(\Enc_\td^\lambda, \Dec_\td^\lambda)$ and $\lambda\in \mathbb{N}$: The 3-split-state quantum tamper-detection code in the bounded storage model of \Cref{theorem:tdc-loa} with $\lambda$ EPR pairs, comprised of:

\begin{enumerate}
\item $\nmext:\{0, 1\}^q\times \{0, 1\}^{\delta \cdot q}\rightarrow \{0, 1\}^{r}$, a quantum secure two source non-malleable extractor, with error $\epsilon_\NM =2^{-q^{\Omega_\delta(1)}}$ and output size $r=(1/2-\delta)q$ from \cref{lem:qnmcodesfromnmext}.

\item The family of $2$-design unitaries $C_R$ from \cref{lem:subclifford} on $\frac{1}{5}\cdot r$ qubits.
\end{enumerate}

From \Cref{theorem:tdc-loa}, $(\Enc_\td^\lambda, \Dec_\td^\lambda)$ has message length $\frac{r}{5}-\lambda$ and is $\epsilon_\td\leq 2(\epsilon_\NM+2^{a-\lambda})$ secure against $\lo_{(a, *, *)}$. Definitions of these code components can be found in \Cref{section:bounded-storage} and \cref{section:prelim}.
\end{enumerate}

Our approach to secret sharing attempts to extend the compiler by [7] to a tripartite setting. First, the classical message $m$ is shared into the secret sharing scheme, resulting in classical shares $(M_1, \cdots, M_p)\leftarrow \share_\lrss(m)$. Then every triplet of parties $a<b<c$ jointly encodes their shares $M_a,M_b, M_c$ into a code $\Enc_\triangle$ supported on a tripartite register, the shares of which are redistributed among $a, b, c$.

In this subsection, we present our gadget code $\Enc_\triangle$ and prove two of its relevant properties: a strong form of 3-out-of-3 secret sharing, as well as a weak form of tamper detection. In the next subsections, we show how to leverage these gadget properties together with that of the underlying leakage-resilient secret sharing scheme to achieve tamper detection, globally.

\subsubsection{The Triangle Gadget}
\label{subsubsection:triangle}

\begin{algorithm}[H]
\setstretch{1.35}
\caption{$\Enc_{\triangle}$: The ``triangle gadget"}
\label{alg:triangle-gadget}
\KwInput{Three parties $p_0<p_1<p_2\in [p]$, three messages $M_0, M_1, M_2$, and an integer parameter $\lambda$.}
\KwOutput{A quantum state $\Enc_{\triangle}^\lambda(M_0, M_1, M_2)$ on a tripartite register $A, B, C$.}

\begin{algorithmic}[1]

\State Each party $i\in \{0, 1, 2\}$ encrypts their message $M_i$ into the tamper-detection code of \Cref{alg:algorithm3qtdc}, into a tripartite register $(Q_i, Y_i\hat{E}_i, X_i)$. Explicitly, party $i$:
\begin{enumerate}
\item Samples uniformly random classical registers $X_i, Y_i$ and evaluates the key $R_i = \nmext(X_i, Y_i)$.
\item Prepares $\lambda_i = (i+1)\cdot \lambda$ EPR pairs, on a bipartite register $E_i\hat{E}_i$.
\item Samples the Clifford unitary $C_{R_i}$ using the sampling process $\samp$ in \cref{lem:subclifford}. Applies $C_{R_i}$ on registers $M_i, E_i$ to generate $Q_i$.
\item Hands register $X_i$ to party $i-1$ (mod $3$), registers $Y_i, \hat{E}_i$ to party $i+1$ (mod $3$), and keeps the authenticated register $Q_i$.
\end{enumerate}

\State Output registers $A, B, C$ for parties $p_0, p_1, p_2$ respectively, where
\begin{equation}
A = (Q_0, Y_2\hat{E}_2, X_1), B = (Q_1, Y_0\hat{E}_0, X_2), C = (Q_2, Y_1\hat{E}_1, X_0)
\end{equation}
\end{algorithmic}
\end{algorithm}

$\Dec_\triangle$: To decode, we simply run the decoder $\Dec_\td$ for the tamper-detection code on the registers $(Q_i, Y_i\hat{E}_i, X_i)$ corresponding to $\Enc_\td(M_i)$. If any of the three are $\bot$, output $\bot$. If otherwise, output the resulting messages $({M}'_0, {M}'_1, {M}'_2)$. Note that if no tampering is present, then from the perfect correctness of the tamper-detection code $(\Enc_\triangle, \Dec_\triangle)$ is also perfectly correct.

\subsubsection{Analysis of the Triangle Gadget}
\label{subsubsection:analysis-triangle}

Before moving on to our global construction, we prove two important properties of the gadget $(\Enc_\triangle, \Dec_\triangle)$. The first is that not only is $\Enc_{\triangle}$ $3$-out-of-$3$ secret sharing, but in fact any two shares $\Enc_{\triangle}$ are near maximally mixed. Note that 3-out-of-3 secret sharing only implies that the two-party reduced density matrices are independent of the message, but apriori they could still be entangled.

\begin{claim}
[Pairwise Independence]\label{claim:triangle-pairwise-indep} For every share $W\in \{A, B, C\}$ and fixed strings $m_0, m_1, m_2$, the two party marginal of $\Enc_{\triangle}(m_0, m_1, m_2)$ without $W$ is $\delta_{\pair}$-close to maximally mixed, where $\delta_{\pair}\leq 6\cdot (\epsilon_\NM + 2^{-\lambda})$.
\end{claim}

\begin{proof}
Recall that $\Enc_\td^e$ is pairwise independent with error $\leq 2(\epsilon_\NM + 2^{-e})$ from \Cref{corr:2nmssq}. The result follows from a triangle inequality.
\end{proof}

The second property concerns the resilience of $\Enc_{\triangle}$ to tampering in $\lo^3$. We prove that two of the three inputs, namely $m_1, m_2$, are individually tamper-detected:

\begin{claim}[Share-wise Tamper Detection]\label{claim:share-weak-td}
Fix $\Lambda\in \lo^3$, three strings $m_0, m_1, m_2$, and an integer $\lambda$. Let $({M}'_0, {M}'_1, {M}'_2)\leftarrow \Dec_\triangle\circ\Lambda\circ \Enc_\triangle(m_0, m_1, m_2)$ denote the distribution over the recovered shares. Then for both $i\in \{ 1, 2\}$,
\begin{equation}
\mathbb{P}[{M}'_i\notin \{m_i, \bot\}]\leq  \epsilon_{\share},
\end{equation}
\noindent where $\epsilon_{\share}\leq \epsilon_\NM + 2^{4-\lambda}$.
\end{claim}

By a union bound, we have $\mathbb{P}[({M}'_1,{M}'_2) \notin \{(m_1,m_2),\bot\}]\leq 2\cdot \epsilon_{\share}$. However, here we already exhibit the selective bot problem. The event ${M}'_1=\bot$ may correlate with ${M}'_2$, breaking the tamper detection guarantee.

\begin{proof}

[of \cref{claim:share-weak-td}]
Fix $m_0, m_1, m_2$, the tampering channel $\Lambda\in \lo^3$, and $i\in \{ 1, 2\}$. In \Cref{alg:triangle-gadget}, note that the $i$th share of $\Enc_\triangle$ is comprised of registers $(Q_i, Y_{i-1}\hat{E}_{i-1}, X_{i+1})$, where
\begin{enumerate}
\item $Q_i$ is a share of $\Enc_{\td}^{\lambda_i}(m_i)$
\item The only other quantum register contains $|\hat{E}_{i-1}|\leq \lambda_{(i-1)\text{mod} 3}$ qubits.
\end{enumerate}

We can now consider the marginal distribution over the $i$th message $m_i$ after the tampering channel. The marginal distribution over the recovered share ${m}'_i$ in the gadget $\Enc_\triangle$ can be simulated using a channel $\Lambda'$ directly on $\Enc_\td(m_i)$:
\begin{equation}
\Tr_{\neq i}\Dec_\triangle\circ\Lambda\circ \Enc_\triangle(m_1, m_2, m_3) = \Dec_\td\circ\Lambda'\circ \Enc_\td(m_i),
\end{equation}
where $\Lambda'$ consists of a local tampering channel on $(Q_i, Y_{i}\hat{E}_{i}, X_{i})$ aided by pre-shared entanglement in a particular form: the adversary who receives share $Q_i$ holds at most $a=\lambda_{i-1}$ qubits of pre-shared entanglement (but the other two may hold unbounded-size registers). This is precisely the model $\lo^3_{(a, *, *)}$ of \Cref{def:lotsharedentanglement}, and we recall by \Cref{theorem:tdc-loa} that $\Enc_\td^{e}$ detects tampering against  $\lo^3_{(a, *, *)}$ with error $2\epsilon_\NM + 2^{4+a-e}$. Since parties $i\in \{1, 2\}$ hold more EPR pairs in their tamper-detection codes than the corresponding adversaries pre-shared, i.e $\lambda_i - \lambda_{i-1}= \lambda>0$ when $i\in \{1, 2\}$, we conclude their shares are tamper-detected:
\begin{equation}
i\in \{1, 2\}: \mathbb{P}[{M}'_i\notin \{m_i, \bot\}]\leq 2\epsilon_\NM + 2^{4-\lambda}.
\end{equation}
\end{proof}

\subsection{Code Construction}
\label{subsection:tdss-construction}

We describe our encoding algorithm in \Cref{alg:td-ss} below:

\begin{algorithm}[H]
\setstretch{1.35}
\caption{$\Enc$: A Tamper-Detecting Ramp Secret Sharing Scheme}
\label{alg:td-ss}
\KwInput{A $k$ bit message $m$.}
%\KwOutput{The product state $\rho^m_L\otimes \rho^r_R$ for some $m\in \{0, 1\}$ correlated with $b$}

\begin{algorithmic}[1]

\State Encode $m$ into the $\lrss$, $(M_1, \cdots, M_p)\leftarrow \share_\lrss(m)$.

\State For every triplet of parties $a< b < c\in [p]$,
\begin{enumerate}
\item Encode the shares $(M_a, M_b, M_c)$ into the ``triangle gadget" described in \Cref{alg:triangle-gadget} supported on triplets of quantum registers
\begin{equation}
A_{(a, b, c)}, B_{(a, b, c)}, C_{(a, b, c)}\leftarrow \Enc_{\triangle}(M_a, M_b, M_c)
\end{equation}
\item Hand the $A_{(a, b, c)}$ register to party $a$, $B_{(a, b, c)}$ to $b$, and $C_{(a, b, c)}$ to $c$.
\end{enumerate}

\State Let the resulting $i$th share be the collection of quantum registers
\begin{equation}
S_i = \{A_{(i, b, c)}:\forall b, c \text{ s.t. } i<b<c\}\bigcup \{B_{(a, i, c)}:\forall a, c\text{ s.t. } a<i<c\}\bigcup\{C_{(a, b, i)}: \forall a, b \text{ s.t. }a<b< i\}
\end{equation}
\end{algorithmic}

\end{algorithm}

We are now in a position to describe our decoding algorithm. Upon receiving the locally tampered shares of any authorized subset $T$ of size equal to $t+2$, our decoder partitions $T$ into two un-authorized subsets, and decodes the gadgets only within each partition.

\begin{algorithm}[H]
\setstretch{1.35}
\caption{$\Dec$: A Bipartite Decoding Algorithm.}
\label{alg:td-ss-dec}
\KwInput{An (authorized) subset $T$ of size $t+2$, and a collection of tampered quantum registers ${S}'_i:i\in T$.}
\KwOutput{A $k$ bit message $M'$}

\begin{algorithmic}[1]

\State Partition $T$ into a subset $U$ of the three smallest indexed shares, and $T\setminus U$.

\State For every triplet of parties $a<b<c$ contained entirely in $T\setminus U$ or entirely in $U$:

\begin{enumerate}
\item Apply the triangle gadget decoding algorithm $\Dec_\triangle$ on registers $A_{(a, b, c)}, B_{(a, b, c)}, C_{(a, b, c)}$.
\item Output $\bot$ if so does the decoder. Otherwise, let $M_{(a, bc)}', M_{(b, ac)}', M_{(c, ab)}'$ be the recovered shares.
\end{enumerate}

\State If $M_{(a, bc)}'\neq M_{(a, de)}'$ for any two triangles $(a, b, c), (a, d, e)$ on the same side of the partition, output $\bot$. Otherwise, let $M_U'$, $M'_{T\setminus U}$ be the recovered shares from either side of the partition.

\item Remove the lowest index share of $U$ to obtain $V\subset U$ and $T\setminus U$ to obtain $W\subset T\setminus U$. Note $|V\cup W|\geq t$.

\State Run the decoder $M'\leftarrow \rec_\lrss(M'_V, M'_W)$ on the classical shares of $V\cup W$.
\end{algorithmic}

\end{algorithm}

The main result of this section proves that the secret sharing scheme described in \Cref{alg:td-ss} and \Cref{alg:td-ss-dec} above detects unentangled tampering, when handed at least $t+2$ shares.

\begin{lemma}\label{lemma:tdss}
Assuming the $\lrss$ is $\epsilon_{lr}$-resilient to $\mu \geq 10\cdot p^2\cdot \lambda$ qubits of leakage, then $(\Enc, \Dec)$ described above is a $(p, t, 0, 0)$-secret sharing scheme which is $(\lo^p, t+2, \epsilon)$-tamper-detecting with error $\epsilon = O(\epsilon_{lr} + p^4\cdot (\epsilon_{\NM}^{1/2} + 2^{-\lambda/2}))$.
\end{lemma}

We dedicate the next subsection to its proof. By instantiating \Cref{lemma:tdss} above,

\begin{theorem}
There exists an efficient $(p, t, 0, 0)$ secret sharing scheme for $k$ bit messages which is $(\lo^p, t+3, 2^{-\max(k, p)^{\Omega(1)}})$-tamper-detecting.
\end{theorem}

\begin{proof}
We use the construction of the $(p, t,0, 0)$ $\lrss$ from \Cref{theorem:lrss-local-leakage-prelim} with message length $k$ bits, shares of length $s=k+ p^2\cdot \lambda$ bits, and error $2^{-\Omega(\lambda)}$; together with the tamper-detection codes $\Enc^\lambda$ from \Cref{theorem:tdc-loa} with message size $s$, error $2^{-\lambda} + 2^{-s^{\Omega(1)}}$, and selecting $\lambda = \max(k, p)$, we conclude the corollary.
\end{proof}

\subsection{Analysis}
\label{subsection:tdss-analysis}

Our proof is comprised of two key claims, which we state and use to prove \Cref{lemma:tdss} and then analyze in the subsequent sections. We begin by arguing that our secret sharing scheme inherits a weak form of tamper detection from the ``outer" split-state tamper-detection codes.

\begin{claim}[Weak Tamper Detection]\label{claim:tdss-weak-td}
For every tampering channel $\Lambda\in \lo^p$, authorized subset $T\subset [p]$ of size $\geq t+2$ and message $m$, the distribution over the recovered message $M'\leftarrow \Dec_T\circ \Lambda\circ \Enc(m)$ satisfies
\begin{equation}
\mathbb{P}[M'\notin \{m, \bot\}]\leq \eta_\td  = O(p^3\cdot (\epsilon_\share +  \delta_{\pair}\cdot p)) = O(p^4(\epsilon_{\NM}+2^{-\lambda}))
\end{equation}

\noindent In fact, all the shares of $V\cup W$ are recovered whp: $\mathbb{P}[\exists i\in V\cup W: M'_i\notin \{m_i, \bot\}]\leq \eta_\td$
\end{claim}

In other words, $(\Enc, \Dec)$ is a secret sharing scheme which is weak tamper-detecting against $\lo^p$, so long as the decoder receives at least $t+2$ shares. As previously discussed, the reason this is only \textit{weak} tamper detecting is due to the selective bot problem - the probability with which we reject may apriori depend on $m$. We leverage the leakage resilience of the underlying secret sharing scheme to ensure this cannot occur:

\begin{claim}[The Selective Bot Problem]\label{claim:tdss-selective-bot}
For every tampering channel $\Lambda\in \lo^p$ and authorized subset $T\subset [p]$ of size $\geq t+2$, the probability the decoding algorithm $\Dec$ in \Cref{alg:td-ss-dec} rejects is near independent of the message. That is,
\begin{equation}
\forall \Lambda\in \lo^p, m_0, m_1: \big|\mathbb{P}[\Dec_T\circ \Lambda\circ \Enc(m_0) = \bot] - \mathbb{P}[\Dec_T\circ \Lambda\circ \Enc(m_1) = \bot]\big|\leq \eta_{lr},
\end{equation}
\noindent where $\eta_{lr} = O(\epsilon_{lr}+p^2\cdot \sqrt{\delta_{\pair}+\epsilon_\share}) = O(\epsilon_{lr} + p^2(\epsilon_\NM^{1/2} + 2^{-\lambda/2}))$.
\end{claim}

Put together, we now conclude the proof:

\begin{proof}

[of \Cref{lemma:tdss}] Let the random variable $M$ denote the uniform distribution over messages, and let $m$ be any fixed value of $M$. From \Cref{claim:tdss-weak-td}, for a fixed $\Lambda\in \lo^p$ and  $T\subset [p]$ the distribution over the recovered message $M'$ is near a convex combination of $M$ and rejection, with bias $\gamma_m$ (dependent on $m$):
\begin{equation}
M'|_{M=m} \approx_{\eta_\td} \gamma_m \cdot m+(1-\gamma_m) \cdot \bot.
\end{equation}

However, by \Cref{claim:tdss-selective-bot}, the probability of $\bot$ can barely depend on $M$:
\begin{equation}
1-\gamma_m \approx_{\eta_\td} \mathbb{P}[M' = \bot|M=m] \approx_{\eta_{lr}} \mathbb{P}[M' = \bot] \equiv p_{ \mathsf{Adv}}
\end{equation}

By the triangle inequality, $M'|_{M=m}\approx_{3\cdot \eta_\td + 2\eta_{lr}} (1-p_{ \mathsf{Adv}})\cdot m+ p_{ \mathsf{Adv}}\cdot \bot$, for some fixed $p_{ \mathsf{Adv}}$ dependent on $\Lambda, T$. With $\eta_\td, \eta_{lr}$ as in the claims above we conclude the theorem.
\end{proof}

\subsubsection{Proof of Weak Tamper Detection (\Cref{claim:tdss-weak-td})}

\begin{proof}

[of \Cref{claim:tdss-weak-td}] Consider any triangle $a<b<c\in [p]$ contained on the same side of the partition $(U, T\setminus U)$, and let $(m_a, m_b, m_c)$ be any fixing of their classical shares. Note that the reduced density matrix on their quantum registers $(S_a, S_b, S_c) \vert ((M_a, M_b, M_c) = (m_a, m_b ,m_c))$ contains the triangle $\Enc_\triangle(m_a, m_b, m_c)$, as well as the registers of all the triangles $(a', b', c')$ which intersect $(a, b, c)$. However, since each individual register of $\Enc_{\triangle}$ is maximally mixed, and all pairs of registers of $\Enc_{\triangle}$ are $\delta_\pair$ approximately pairwise independent (\Cref{claim:triangle-pairwise-indep}), we have
\begin{equation}
(S_a, S_b, S_c)\vert_{((M_a, M_b, M_c) = (m_a, m_b ,m_c))} \approx_{3\cdot \delta_{\pair}\cdot p} \Enc_\triangle(m_a, m_b, m_c) \otimes \frac{\mathbb{I}}{\Tr\mathbb{I}}
\end{equation}

The copies $\sigma = \frac{\mathbb{I}}{\Tr\mathbb{I}} $ of the maximally mixed state are separable across the shares $a, b, c$, and independent of $m$, and act as ancillas. Therefore, any channel $\Lambda\in \lo^3$ which tampers with the registers $(S_a, S_b, S_c)$ using $\sigma$ can be simulated in $\lo^3$ without them:
\begin{gather*}
\Dec_\triangle\circ \Lambda\circ (S_a, S_b, S_c)\vert_{((M_a, M_b, M_c) = (m_a, m_b ,m_c))} \approx_{3\cdot \delta_{\pair}\cdot p} \Dec_\triangle\circ \Lambda (\Enc_\triangle(m_a, m_b, m_c) \otimes \sigma) \\= \Dec_\triangle\circ \Lambda' \circ \Enc_\triangle(m_a, m_b, m_c)
\end{gather*}

By \Cref{claim:share-weak-td} and the triangle inequality, this implies that two of the three shares in each triangle $(a, b, c)$ are weak tamper detected:
\begin{equation}
\mathbb{P}[({M}'_a, {M}'_b) \notin \{(m_a, m_b), \bot\}]\leq 2\epsilon_\share + 3\cdot \delta_{\pair}\cdot p
\end{equation}

By a union bound over all the triangles, either all the shares in $V\subset U, W\subset (T\setminus U)$ are recovered, or we reject with probability
\begin{equation}