Prototype Implementations: The Secure Link Prediction Problem

Installation and Execution

  1. Download the source code from this link
  2. Install PBC library
  3. Install supporting Libraries; m4, flex, bison etc.
  4. Install GNU library if required
  5. Run myBGN_test to check whether the above library installed properly or not
  6. Give graph data file in the data folder.
  7. Update data file path, number of nodes and security bits in makefile
  8. Run SLP1 by "make slp1"
  9. Run SLP2 by "make slp2"







SLP1.c

  1. SLP1_Key_Gen(int lambda):
    Generates a key for the Secure Link Prediction (SLP) protocol.

    • Parameters: lambda - Security parameter used for key generation.
    • Returns: A pointer to the generated SLP1 key.

  2. SLP1_Encrypt_Matrix(int ** AdjMatrix, BGN_PK_t * bgn_pk, int noOfNodes):
    Encrypts an adjacency matrix using the Boneh-Goh-Nissim (BGN) cryptosystem.

    • Parameters:
      • AdjMatrix - The adjacency matrix to be encrypted.
      • bgn_pk - The public key used for encryption.
      • noOfNodes - The number of nodes in the graph represented by the adjacency matrix.
    • Returns: A pointer to the encrypted matrix.

  3. SLP1_Trapdoor_Gen(TRAPDOOR_t *trapdoor, int vertId, int keyPerm):
    Generates a trapdoor for a given vertex ID and key permutation.

    • Parameters:
      • trapdoor - Pointer to the structure where the trapdoor will be stored.
      • vertId - The ID of the vertex for which the trapdoor is generated.
      • keyPerm - Key permutation value.
    • Returns: None.

  4. read_matrix_from_file(char * fileName, int noOfNodes):
    Reads an adjacency matrix from a file.

    • Parameters:
      • fileName - Name of the file containing the adjacency matrix.
      • noOfNodes - Number of nodes in the graph.
    • Returns: Pointer to the read adjacency matrix.

  5. time_difference(struct timeval * startTime, struct timeval * endTime):
    Calculates the time difference between two timestamps.

    • Parameters:
      • startTime - Pointer to the start time.
      • endTime - Pointer to the end time.
    • Returns: Time difference in seconds.

  6. SLP1_print_times(int noOfNodes, int lambda, double runTimeKG, double runTimeEM, int noOfLPQueries, double runTimeTG, double runTimeLPQ, double runTimeFMV):
    Prints the times taken for different steps in the SLP protocol and writes them to a file.

    • Parameters:
      • noOfNodes - Number of nodes in the graph.
      • lambda - Security parameter.
      • runTimeKG - Time taken for key generation.
      • runTimeEM - Time taken for matrix encryption.
      • noOfLPQueries - Number of link prediction queries.
      • runTimeTG - Time taken for trapdoor generation.
      • runTimeLPQ - Time taken for each link prediction query.
      • runTimeFMV - Time taken for finding the maximum vertex.
    • Returns: None.







SLP2.c

  1. SLP2_contruct_b_matrix(int **AdjMatrix, int noOfNodes)
    Description: Constructs a matrix B used in Secure Link Prediction (SLP) problem.
    Parameters:
    • AdjMatrix: 2D array representing the adjacency matrix.
    • noOfNodes: Number of nodes in the graph.
    Output: BMatrix (constructed B matrix)
  2. SLP1_Key_Gen(int lambda)
    Description: Generates a key for Secure Link Prediction (SLP) using the BGN (Boneh-Goh-Nissim) cryptosystem.
    Parameters:
    • lambda: Security parameter.
    Output: slp1_KEY (generated key for SLP)
  3. SLP1_Encrypt_Matrix(int **AdjMatrix, BGN_PK_t *bgn_pk, int noOfNodes)
    Description: Encrypts the adjacency matrix using the BGN cryptosystem for Secure Link Prediction (SLP).
    Parameters:
    • AdjMatrix: Adjacency matrix.
    • bgn_pk: Public key.
    • noOfNodes: Number of nodes.
    Output: EncMatrix (encrypted matrix)
  4. SLP2_Encrypt_Matrix(int **BMatrix, BGN_PK_t *bgn_pk, int noOfNodes)
    Description: Encrypts the B matrix using the BGN cryptosystem for Secure Link Prediction (SLP).
    Parameters:
    • BMatrix: B matrix.
    • bgn_pk: Public key.
    • noOfNodes: Number of nodes.
    Output: EncMatrix (encrypted matrix)
  5. SLP1_Trapdoor_Gen(TRAPDOOR_t *trapdoor, int vertId, int keyPerm)
    Description: Generates a trapdoor for Secure Link Prediction (SLP1) based on vertex ID and key permutation.
    Parameters:
    • trapdoor: Trapdoor structure to store the generated trapdoor.
    • vertId: Vertex ID.
    • keyPerm: Key permutation.
    Output: None
  6. SLP1_LinkPred_Query(LP_Q_RES_t *lpQres, TRAPDOOR_t *trapdoor, element_t **EncMatrix, BGN_PK_t *bgn_pk, int noOfNodes)
    Description: Performs a link prediction query for Secure Link Prediction (SLP1) using the given trapdoor and encrypted matrix.
    Parameters:
    • lpQres: Link prediction query result structure.
    • trapdoor: Trapdoor generated for the query.
    • EncMatrix: Encrypted matrix.
    • bgn_pk: Public key.
    • noOfNodes: Number of nodes.
    Output: None
  7. SLP2_LinkPred_Query(LP2_Q_RES_t *lp2Qres, TRAPDOOR_t *trapdoor, element_t **EncMatrixA, element_t **EncMatrixB, BGN_PK_t *bgn_pk, int noOfNodes)
    Description: Performs a link prediction query for Secure Link Prediction (SLP2) using the given trapdoor and encrypted matrices.
    Parameters:
    • lp2Qres: Link prediction query result structure.
    • trapdoor: Trapdoor generated for the query.
    • EncMatrixA: Encrypted matrix A.
    • EncMatrixB: Encrypted matrix B.
    • bgn_pk: Public key.
    • noOfNodes: Number of nodes.
    Output: None
  8. SLP1_Find_Max_Vertex(SLP1_RES_t *slp1Res, SLP1_KEY_t *slp1_KEY, LP_Q_RES_t *lpQres, int noOfNodes)
    Description: Finds the maximum vertex in Secure Link Prediction (SLP1) based on the link prediction query result.
    Parameters:
    • slp1Res: Result structure for SLP1.
    • slp1_KEY: Key structure for SLP1.
    • lpQres: Link prediction query result structure.
    • noOfNodes: Number of nodes.
    Output: None
  9. SLP2_Find_Max_Vertex(SLP2_RES_t *slp2Res, SLP1_KEY_t *slp1_KEY, LP2_Q_RES_t *lp2Qres, int noOfNodes)
    Description: Finds the maximum vertex in Secure Link Prediction (SLP2) based on the link prediction query result.
    Parameters:
    • slp2Res: Result structure for SLP2.
    • slp1_KEY: Key structure for SLP1.
    • lp2Qres: Link prediction query result structure.
    • noOfNodes: Number of nodes.
    Output: None
  10. SLP2_sort(mpz_t *scores, int *indices, int n)
    Description: Sorts scores and indices for Secure Link Prediction (SLP2) based on maximum scores.
    Parameters:
    • scores: Scores to be sorted.
    • indices: Indices corresponding to the scores.
    • n: Number of elements.
    Output: None
  11. SLP2_final_score(SLP1_KEY_t *slp1_KEY, element_t *m, SLP2_RES_t *slp2Res, int noOfNodes)
    Description: Calculates the final score for Secure Link Prediction (SLP2) based on the maximum score and degree.
    Parameters:
    • slp1_KEY: Key structure for SLP1.
    • m: Element representing the matrix.
    • slp2Res: Result structure for SLP2.
    • noOfNodes: Number of nodes.
    Output: None
  12. SLP1_Clear_LPQRes(LP_Q_RES_t *lpQres, int noOfNodes)
    Description: Clears the memory allocated for the link prediction query result for Secure Link Prediction (SLP1).
    Parameters:
    • lpQres: Link prediction query result structure.
    • noOfNodes: Number of nodes.
    Output: None
  13. SLP1_Clear_All(int **AdjMatrix, element_t **EncMatrix, BGN_PK_t *bgnPk, int noOfNodes)
    Description: Clears the memory allocated for all structures and matrices used in Secure Link Prediction (SLP1).
    Parameters:
    • AdjMatrix: Adjacency matrix.
    • EncMatrix: Encrypted matrix.
    • bgnPk: Public key.
    • noOfNodes: Number of nodes.
    Output: None
  14. SLP2_Clear_All(int **AdjMatrix, element_t **EncMatrixA, int **BMatrix, element_t **EncMatrixB, BGN_PK_t *bgnPk, int noOfNodes)
    Description: Clears the memory allocated for all structures and matrices used in Secure Link Prediction (SLP2).
    Parameters:
    • AdjMatrix: Adjacency matrix.
    • EncMatrixA: Encrypted matrix A.
    • BMatrix: B matrix.
    • EncMatrixB: Encrypted matrix B.
    • bgnPk: Public key.
    • noOfNodes: Number of nodes.
    Output: None
  15. SLP1_print_slp1_res(SLP1_RES_t *slp1Res)
    Description: Prints the result of Secure Link Prediction (SLP1) including the vertex ID and maximum score.
    Parameters:
    • slp1Res: Result structure for SLP1.
    Output: None
  16. SLP2_print_slp2_res(SLP2_RES_t *slp2Res)
    Description: Prints the result of Secure Link Prediction (SLP2) including the vertex ID and maximum score.
    Parameters:
    • slp2Res: Result structure for SLP2.
    Output: None
  17. read_matrix_from_file(char *fileName, int noOfNodes)
    Description: Reads the adjacency matrix from a file.
    Parameters:
    • fileName: Name of the file containing the adjacency matrix.
    • noOfNodes: Number of nodes.
    Output: AdjMatrix (adjacency matrix)
  18. Allocate_2D_int(int n, int m)
    Description: Allocates memory for a 2D integer array.
    Parameters:
    • n: Number of rows.
    • m: Number of columns.
    Output: arr (allocated 2D integer array)
  19. Allocate_2D_element(int n, int m)
    Description: Allocates memory for a 2D element array.
    Parameters:
    • n: Number of rows.
    • m: Number of columns.
    Output: arr (allocated 2D element array)
  20. time_difference(struct timeval *startTime, struct timeval *endTime)
    Description: Calculates the time difference between two timevals.
    Parameters:
    • startTime: Start time.
    • endTime: End time.
    Output: Time difference in seconds