## 2 Methods
### Teleportation with Quantum Walks on Circles  
In view of the model of quantum walks on circles above, we describe the teleportation based on quantum walks on circles with two coins and \(P=4\) vertices. We postulate that [PERSON] and [PERSON] are the sender and the receiver, respectively, who participate in the communication, in which [PERSON] wants to transfer an unknown qubit \(|\phi_{i}\rangle=\alpha_{i}|0\rangle+\beta_{i}|1\rangle\) to [PERSON]. [PERSON] holds two particles \(a1\) and \(a2\), which separately carry the state of the first coin and the state of the position. While the state of the second coin is encoded onto particle \(b\), which is possessed by [PERSON]. The initial states of \(a1\), \(a2\) and \(b\) are denoted as \(|\phi_{i}\rangle\), \(|0\rangle\) and \(|+\rangle\). Thus, the whole initial state of the quantum walk system is  
\[|\psi\rangle^{0}=|0\rangle\otimes(\alpha_{i}|0\rangle+\beta_{i}|1\rangle) \otimes|+\rangle, \tag{5}\]  
Figure 1: Shift rules of quantum walks on a circle with \(P\) vertices.  
with the particle order \(a2\), \(a1\), \(b\) and \(|+\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\).  
We formulate the first step of the quantum walk as  
\[U_{1}=W_{1}\cdot(I_{p}\otimes C_{1}\otimes I_{2}), \tag{6}\]  
where \(W_{1}=Q\otimes|0\rangle_{1}\langle 0|\otimes I_{2}+Q^{\dagger}\otimes|1 \rangle_{1}\langle 1|\otimes I_{2}=O^{\prime}\otimes I_{2}\), \(C_{1}\) is the coin operator employed on the first coin state, \(Q=\sum_{x}|x+1\rangle\langle x|\) is the shift operator employed on the position space and \(Q^{\dagger}\) is the Hermitian operator of \(Q\). According to Equation (4), for convenience of calculation, we equate \(|R\rangle\) to \(|0\rangle\) and \(|L\rangle\) to \(|1\rangle\) and then we can express the notation \(O^{\prime}\) with \(P=4\) as  
\[O^{\prime}=\sum_{x=0}^{2}|x+1\rangle\langle x|\otimes|0\rangle\langle 0|+\sum_{ x=1}^{3}|x-1\rangle\langle x|\otimes|1\rangle\langle 1|+|0\rangle\langle 3|\otimes|0 \rangle\langle 0|+|3\rangle\langle 0|\otimes|1\rangle\langle 1|. \tag{7}\]  
If \(C_{1}=I\), the initial system state \(|\psi\rangle^{0}\) transforms into  
\[|\psi\rangle^{1}=\frac{1}{\sqrt{2}}(\alpha_{i}|1\rangle|0\rangle|0\rangle+ \beta_{i}|3\rangle|1\rangle|1\rangle), \tag{8}\]  
which produces the entanglement between position space and coin space referring to [PERSON] and [PERSON].  
We describe the second step of the quantum walk as  
\[U_{2}=W_{2}\cdot(I_{p}\otimes I_{1}\otimes C_{2}), \tag{9}\]  
where  
\[W_{2}=Q\otimes I_{1}\otimes|0\rangle_{2}\langle 0|+Q^{\dagger}\otimes I_{1} \otimes|1\rangle_{2}\langle 1|=O^{\prime}\otimes I_{1} \tag{10}\]  
and \(C_{2}\) is the coin operator employed on the second coin state. If \(C_{2}=I\), the state of the system evolves into  
\[|\psi\rangle^{2}=\frac{|0\rangle\otimes(\alpha_{i}|01\rangle+\beta_{i}|10 \rangle)}{\sqrt{2}}+\frac{|2\rangle\otimes(\alpha_{i}|00\rangle+\beta_{i}|11 \rangle)}{\sqrt{2}}. \tag{11}\]  
Subsequently, [PERSON] first measures particle \(a2\) using basis \(\{|0\rangle,|1\rangle,|2\rangle,|3\rangle\}\) corresponding to the classical results \(\{0,1,2,3\}\). Then [PERSON] measures particle \(a1\) using basis \(\{|+\rangle,|-\rangle\}\) corresponding to the classical results \(\{1,-1\}\). In the light of the measurement results of \(a2\) and \(a1\), [PERSON] implements corresponding unitary operations to recover the qubit to be teleported, which is listed in Table 1. In the following, this teleportation scheme is employed to transfer the encrypted qubit message copy from the signatory to the verifier, which helps to complete the validity verification of the completed proxy signature.