# American Institute of Mathematical Sciences

November  2019, 13(4): 733-757. doi: 10.3934/amc.2019043

## The secure link prediction problem

 1 Cryptology and Security Research Unit, Indian Statistical Institute, Kolkata, India 2 R C Bose Centre for Cryptology and Security, Indian Statistical Institute, Kolkata, India

* Corresponding author

Received  October 2018 Revised  January 2019 Published  June 2019

Link Prediction is an important and well-studied problem for social networks. Given a snapshot of a graph, the link prediction problem predicts which new interactions between members are most likely to occur in the near future. As networks grow in size, data owners are forced to store the data in remote cloud servers which reveals sensitive information about the network. The graphs are therefore stored in encrypted form.

We study the link prediction problem on encrypted graphs. To the best of our knowledge, this secure link prediction problem has not been studied before. We use the number of common neighbors for prediction. We present three algorithms for the secure link prediction problem. We design prototypes of the schemes and formally prove their security. We execute our algorithms in real-life datasets.

Citation: Laltu Sardar, Sushmita Ruj. The secure link prediction problem. Advances in Mathematics of Communications, 2019, 13 (4) : 733-757. doi: 10.3934/amc.2019043
##### References:

show all references

##### References:
System model
Example of a Maximum circuit with $N = 7$
Different max blocks used in $\mathtt{MAXIMUM}$ circuit
Few circuit blocks
Number of vertices and edges of the subgraphs
comparison between $\mathtt{SLP}$-$\mathtt{I}$ and $\mathtt{SLP}$-$\mathtt{II}$ w.r.t. computation time when the primes are of 128 bits each
Time taken by the proxy in $\mathtt{SLP}$-$\mathtt{II}$ for different datasets considering 128-bit primes
Computational time in $\mathtt{SLP}$-$\mathtt{I}$ with 128,256 and 512-bit primes
Computational time in $\mathtt{SLP}$-$\mathtt{II}$ with 128,256 and 512-bit primes
Complexity Comparison Table
 Param Entity $\mathtt{SLP}$-$\mathtt{I}$ $\mathtt{SLP}$-$\mathtt{II}$ $\mathtt{SLP}$-$\mathtt{III}$ Leakage CS $|V|$, $\tau_{v_1},\tau_{v_2},\ldots$ $|V|$, $\tau_{v_1},\tau_{v_2},\ldots$ $|V|$, $\tau_{v_1},\tau_{v_2},\ldots$ PS $S_{v},i_{res}$ $S'_{v},i_{res}$ $i_{res}$ client $\lambda$ bits $\lambda$ bits $\lambda$ bits Storage CS $|V|^2\rho$ bits $2|V|^2\rho$ bits $|V|^2\rho$ bits PS $\rho$ bits $\rho$ bits $\rho$ bits client $|V|^2(\mathsf{M}+\mathsf{A})$ $|V|^2(\mathsf{M}+\mathsf{A}+\mathsf{M_1}+\mathsf{A_1})$ $|V|^2(\mathsf{M}+\mathsf{A})$ Compu- CS $|V|^2$ $\mathsf{P}$ + $|V|$ $\mathsf{E}$ $|V|^2$ $\mathsf{P}$ + $|V|^2$ $\mathsf{P}$ + $4|V|$ $\mathsf{E}$ tation + ($|V|^2+ |V|$) $\mathsf{M}$ ($|V|^2+ 2|V|$) $\mathsf{M}$ + ($|V|^2+ 3|V|$) $\mathsf{M}$ + $MGC_{const}{(\log |V|,|V|)}$ PS $|V|log|V| (\mathsf{M+C}+\mathsf{M_1+C_1})$ $|V| (\mathsf{M_1+C_1})$ + $|V| (\mathsf{M+C}+\mathsf{M_1+C_1})$+ +$|V|log|V| \mathsf{C}$ +$|V| log|V| \mathsf{C}$ $MGC_{eval}{(\log |V|,|V|)}$ client$\rightarrow$CS $|V|^2 \rho$ bits $2 |V|^2 \rho$ bits $|V|^2\rho$ bits Commu- CS$\rightarrow$PS $2|V|\rho$ bits $|V|\rho$ bits $2|V|\rho$ bits + $|V|OT ^{(\log |V| +1)}_{snd}$+ nication $MGC_{size}{(\log |V|,|V|)}$ bits PS$\rightarrow$CS - - $|V|OT ^{(\log |V| +1)}_{rcv}$ PS$\rightarrow$client $\log |V|$ bits $2|V| \log |V|$ bits $\log |V|$ bits $S_{v}$ - Set of scores of $v$ with all other vertices, $S'_{v}$- a subset of $S_{v}$, $\rho$- length of elements in $\mathbb{G}$ or $\mathbb{G}_1$, $\mathsf{C}$- comparison in $\mathbb{G}$, $\mathsf{C_1}$- comparison in $\mathbb{G}_1$, $\mathsf{M}$- multiplication in $\mathbb{G}$, $\mathsf{M_1}$- multiplication in $\mathbb{G}_1$, $\mathsf{E}$- exponentiation in $\mathbb{G}$, $\mathsf{E_1}$- exponentiation in $\mathbb{G}_1$, $\mathsf{P}$- pairing/ bilinear map computation, $MGC_{size}{(\log |V|,|V|)}$- size of $MGC$ with $|V|$ $\log |V|$-bit inputs, $MGC_{const}{(\log |V|,|V|)}$- $MGC$ contraction with $|V|$ $\log |V|$-bit inputs, $MGC_{eval}{(\log |V|,|V|)}$- $MGC$ evaluation with $|V|$ $\log |V|$-bit inputs, $OT ^{(\log |V| +1)}_{snd}$- information to send for $(\log |V|+1)$-bit $OT$, $OT ^{(\log |V| +1)}_{rcv}$- information to receive for $\log |V|$-bit $OT$.
 Param Entity $\mathtt{SLP}$-$\mathtt{I}$ $\mathtt{SLP}$-$\mathtt{II}$ $\mathtt{SLP}$-$\mathtt{III}$ Leakage CS $|V|$, $\tau_{v_1},\tau_{v_2},\ldots$ $|V|$, $\tau_{v_1},\tau_{v_2},\ldots$ $|V|$, $\tau_{v_1},\tau_{v_2},\ldots$ PS $S_{v},i_{res}$ $S'_{v},i_{res}$ $i_{res}$ client $\lambda$ bits $\lambda$ bits $\lambda$ bits Storage CS $|V|^2\rho$ bits $2|V|^2\rho$ bits $|V|^2\rho$ bits PS $\rho$ bits $\rho$ bits $\rho$ bits client $|V|^2(\mathsf{M}+\mathsf{A})$ $|V|^2(\mathsf{M}+\mathsf{A}+\mathsf{M_1}+\mathsf{A_1})$ $|V|^2(\mathsf{M}+\mathsf{A})$ Compu- CS $|V|^2$ $\mathsf{P}$ + $|V|$ $\mathsf{E}$ $|V|^2$ $\mathsf{P}$ + $|V|^2$ $\mathsf{P}$ + $4|V|$ $\mathsf{E}$ tation + ($|V|^2+ |V|$) $\mathsf{M}$ ($|V|^2+ 2|V|$) $\mathsf{M}$ + ($|V|^2+ 3|V|$) $\mathsf{M}$ + $MGC_{const}{(\log |V|,|V|)}$ PS $|V|log|V| (\mathsf{M+C}+\mathsf{M_1+C_1})$ $|V| (\mathsf{M_1+C_1})$ + $|V| (\mathsf{M+C}+\mathsf{M_1+C_1})$+ +$|V|log|V| \mathsf{C}$ +$|V| log|V| \mathsf{C}$ $MGC_{eval}{(\log |V|,|V|)}$ client$\rightarrow$CS $|V|^2 \rho$ bits $2 |V|^2 \rho$ bits $|V|^2\rho$ bits Commu- CS$\rightarrow$PS $2|V|\rho$ bits $|V|\rho$ bits $2|V|\rho$ bits + $|V|OT ^{(\log |V| +1)}_{snd}$+ nication $MGC_{size}{(\log |V|,|V|)}$ bits PS$\rightarrow$CS - - $|V|OT ^{(\log |V| +1)}_{rcv}$ PS$\rightarrow$client $\log |V|$ bits $2|V| \log |V|$ bits $\log |V|$ bits $S_{v}$ - Set of scores of $v$ with all other vertices, $S'_{v}$- a subset of $S_{v}$, $\rho$- length of elements in $\mathbb{G}$ or $\mathbb{G}_1$, $\mathsf{C}$- comparison in $\mathbb{G}$, $\mathsf{C_1}$- comparison in $\mathbb{G}_1$, $\mathsf{M}$- multiplication in $\mathbb{G}$, $\mathsf{M_1}$- multiplication in $\mathbb{G}_1$, $\mathsf{E}$- exponentiation in $\mathbb{G}$, $\mathsf{E_1}$- exponentiation in $\mathbb{G}_1$, $\mathsf{P}$- pairing/ bilinear map computation, $MGC_{size}{(\log |V|,|V|)}$- size of $MGC$ with $|V|$ $\log |V|$-bit inputs, $MGC_{const}{(\log |V|,|V|)}$- $MGC$ contraction with $|V|$ $\log |V|$-bit inputs, $MGC_{eval}{(\log |V|,|V|)}$- $MGC$ evaluation with $|V|$ $\log |V|$-bit inputs, $OT ^{(\log |V| +1)}_{snd}$- information to send for $(\log |V|+1)$-bit $OT$, $OT ^{(\log |V| +1)}_{rcv}$- information to receive for $\log |V|$-bit $OT$.
Detail of the graph datasets
 Dataset Name #Nodes #Edges bitcoin-alpha 3,783 24,186 ego-facebook 4,039 88,234 email-Enron 36,692 183,831 email-Eu-core 1,005 25,571 Wiki-Vote 7,115 103,689
 Dataset Name #Nodes #Edges bitcoin-alpha 3,783 24,186 ego-facebook 4,039 88,234 email-Enron 36,692 183,831 email-Eu-core 1,005 25,571 Wiki-Vote 7,115 103,689

2018 Impact Factor: 0.879