# SQRT: A Secure Querying Scheme of Routing Table Based on Oblivious Transfer
## 3 SQRT Scheme  
The security querying for the routing table process includes two participants, DS and \(U\!E_{k}\). They want to calculate \(f(q_{i}(d_{1},\,d_{2},\,\ldots,\,d_{m}))=r_{z}\) together, where \(r_{z}\) is the satisfied routing node obtained by comparison, and \(U\!E_{k}\) obtains the output function \(r_{z}\). The process of the user equipment \(U\!E_{k}\) querying the routing table security from the DS can be abstracted into an \(N_{k}+\Delta\)-out-of-\(N_{k}\) oblivious transfer model, which is abbreviated as \(OT_{N_{k}+\Delta}^{N_{k}}\). In a public key encryption scheme [19], there is an encryption function \(E\), a decryption function \(D\), a public key \(Key_{p}\), and a private key \(Key_{s}\). The key length satisfies \(|\,Key_{p}\,|\,=\,|\,Key_{s}\,|\,=\,K\) and \(\text{String}=D(E(String,key_{p}),\,Key_{s})\), which means that in any secure public key encryption scheme, the corresponding private key cannot be calculated for a specific public key. In other words, it is difficult to calculate the corresponding private key. The Algorithm 1 shows the process of secure querying for the routing table. Figure 3: The secure querying for the routing table in the directory server. For the 2-out-of-1 oblivious transfer scheme [20], the input of DS is two strings \(s_{0}\), \(s_{1}\in\{0,1\}^{k}\), and the input of \(U\!E_{k}\) is \(c\in\{0,1\}\). Using the 2-out-of-1 oblivious transfer to construct the \(N_{k}+\Delta\)-out-of-\(N_{k}\) oblivious transfer is shown in Figure 4. Figure 4 mainly introduces how to select \(N_{k}\) routing nodes from the \(N_{k}+\Delta\) routing nodes in the oblivious transfer model. 1. The DS has inputs \(M_{1}\), \(M_{2}\),..., \(M_{n}\in\{0,1\}^{k}\), selects a random string \(C\in\{0,1\}^{k}\), and sends \(C\) to the DS;
2. \(U\!E_{k}\) has different inputs \(c_{1}\), \(c_{2}\),..., \(c_{N_{k}}\in\{1,2,\)..., \(N_{k}+\Delta\}\), constructs a pair of public key \(\textit{Key}_{\textit{pc}}\) and private key \(\textit{Key}_{\textit{sc}}\), and then calculates another public key \(\textit{Key}_{p,1-c}\) according to \(\textit{Key}_{p,1-c}\oplus\textit{Key}_{\textit{pc}}=C\), and the key length is satisfied \(\big{|}\textit{Key}_{p_{0}}\big{|}\!=\!\big{|}\textit{Key}_{p_{1}}\big{|}\!=\! \big{|}\textit{Key}_{\textit{sc}}\big{|}\!=\!\big{|}C\);
3. \(U\!E_{k}\) sends \(\textit{Key}_{p_{0}}\) and \(\textit{Key}_{p_{1}}\) to the DS; The DS verifies whether \(\textit{Key}_{p_{0}}\oplus\textit{Key}_{p_{1}}=C\). If not, the execution is rejected. 4. The DS sends \(E(s_{0}\), \(\textit{Key}_{p_{0}})\) and \(E(s_{1}\), \(\textit{Key}_{p_{1}})\) to \(U\!E_{k}\);
5. \(U\!E_{k}\) uses \(\textit{Key}_{\textit{pc}}\) to get \(s_{c}\), i.e.,  
\[s_{c}=D(E(s_{c}\textit{Key}_{\textit{pc}}),\textit{Key}_{\textit{sc}}) \tag{4}\]
6. \(U\!E_{k}\) and DS perform the interaction process of \(N_{k}\) oblivious transfer. Each time the oblivious transfer protocol is executed, \(U\!E_{k}\) can always obtain the address information of a routing node \(j\), \(j=1\), \(2\),..., \(n\). After executing \(N_{k}\) times, \(U\!E_{k}\) can obtain \(N_{k}\) messages \(M_{t}\), \(t\in\{c_{1},c_{2},\)..., \(C_{N_{k}}\}\). If both DS and \(U\!E_{k}\) are honest [21; 22], \(U\!E_{k}\) can obtain \(s_{c}\) through (4), i.e., \(U\!E_{k}\) can obtain \(N_{k}\) messages \(M_{t}\), \(t\in\{c_{1},c_{2},\)..., \(C_{N_{k}}\}\). For DS, what it obtains in the process of interaction is only the sum of two strings \(\textit{Key}_{p_{0}}\) and \(\textit{Key}_{p_{1}}\), and it cannot judge the exact value of \(c\). For \(U\!E_{k}\), it can only construct public key and private key, \(\textit{Key}_{\textit{pc}}\), \(\textit{Key}_{\textit{sc}}\!\rightarrow\!\textit{Key}_{p,1-c}\) through the following methods. According to the requirements of a public key encryption scheme, \(U\!E_{k}\) cannot calculate \(\textit{Key}_{s,1-c}\) through \(\textit{Key}_{p,1-c}\).