threshold test

[MoienBowen]

int main(void) {
  djcs_t_public_key *pk = djcs_t_init_public_key();
  djcs_t_private_key *vk = djcs_t_init_private_key();
  hcs_random *hr = hcs_init_random();

  // key length = 2048, sharing length 128, threshold 3, decrypt participant 3
  djcs_t_generate_key_pair(pk, vk, hr, 2048, 128, 3, 3); 
}

The code never finishes its compilation.

I thought that I understand how it works (the algorithm), that is why I wrote these function for keygen.
Please help me to point out the mistake.

Thanks in advance.

[tiehuis]

The issue here are the parameters for key generation. Specifically, the first parameter s actually specified the multiplicative group we perform some operations (Z*_{n^{s+1}}). If this is large, we are using a gigantic group and this is not optimal since the larger the group, the more expensive operations are. In particular, 2^2048 (as in this case) is massive!

The place we stall in the library code is here:

    for (unsigned long i = 1; i <= pk->s; ++i) {
        mpz_init(pk->n[i]);
        mpz_pow_ui(pk->n[i], pk->n[i-1], 2);
        mpz_init_set(vk->n[i], pk->n[i]);
    }

We compute and store all subsequent powers of n (our safe prime product) in an array. With s being 2048 this means we eventually need to compute (p*q)^2048 which is simply too large, with 2^2048 for example having 617 decimal digits.

You will want to call this function like this:

#include "libhcs.h"

int main(void) {
  djcs_t_public_key *pk = djcs_t_init_public_key();
  djcs_t_private_key *vk = djcs_t_init_private_key();
  hcs_random *hr = hcs_init_random();

  djcs_t_generate_key_pair(
      pk,
      vk,
      hr,
      2,    // n^3 base group
      2048, // 2048-bit key length
      2,    // Minimum number of parties needed to decrypt,
            // e.g. in this case we generate 3 keys and need at least 2 to succesfully decrypt
            // This should be >= l / 2 according to the paper.
      3     // Number of key segments to produce
  );
}

You then generate the keys for each party after this. I think I still have a full example of multiparty decryption lying around. I'll try and find it tonight and update as I think it would be helpful.

[MoienBowen]

Hi Marc, Thanks for your reply. I now understand well. In addition, I did the example for all your cryptosystem, if you want, I can make a pull request later.

[MoienBowen]

This is my test code for Damgard-Jurik scheme (djcs_t)

I do not understand why I can not clear and free the key at the end (you can try with key length = 1024).
I am now waiting for 2048 key length result...

#include <gmp.h>    // gmp is included implicitly
#include <libhcs.h> // master header includes everything
#include <math.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

int N = 200; // Device numbers
int l = 50;  // Vector length
const unsigned long key_length = 2048;
const unsigned long n_exp = 2; 
const unsigned long nb_need = 3;
const unsigned long nb_total = 3;

int main(void) {
  gmp_printf("Number of device: %d\n"
             "Data vector length: %d\n"
             "Cryptosystem key length: %d\n"
             "n exposant: %d\n\n",
             N, l, key_length, n_exp);

  struct timeval kengen_1, kengen_2, enc_1, enc_2, dec_2;
  double keygen_time = 0;
  gettimeofday(&kengen_1, NULL);

  // Initialize data structures
  djcs_t_public_key *pk = djcs_t_init_public_key();
  djcs_t_private_key *vk = djcs_t_init_private_key();
  hcs_random *hr = hcs_init_random();

  // Generate a key pair with modulus of size 2048 bits
  djcs_t_generate_key_pair(pk, vk, hr, n_exp, key_length, nb_need, nb_total);

  mpz_t *coeff = djcs_t_init_polynomial(vk, hr);
  djcs_t_auth_server **au =
      (djcs_t_auth_server **)malloc(nb_total * sizeof(djcs_t_auth_server *));
  mpz_t *si = (mpz_t *)malloc(nb_total * sizeof(mpz_t));
  for (int i = 0; i < nb_total; i++) {
    mpz_init(si[i]);
    djcs_t_compute_polynomial(vk, coeff, si[i], i);
    au[i] = djcs_t_init_auth_server();
    djcs_t_set_auth_server(au[i], si[i], i);
  }
  gettimeofday(&kengen_2, NULL);
  keygen_time += (double)((kengen_2.tv_sec - kengen_1.tv_sec) * 1000 +
                          (double)(kengen_2.tv_usec - kengen_1.tv_usec) / 1000);

  gmp_randstate_t gmpRandState;
  gmp_randinit_default(gmpRandState);
  gmp_randseed_ui(gmpRandState, 1234567890);

  mpz_t plains, ciphers, res;
  mpz_inits(plains, ciphers, res, NULL);
  mpz_t *dec = (mpz_t *)malloc(nb_need * sizeof(mpz_t));
  for (int j = 0; j < nb_need; j++) {
    mpz_init(dec[j]);
  }

  double enc_time = 0, dec_time = 0;

  int nb_val = (l * (l + 1) + N * (N + 1)) / 2;
  for (int i = 0; i < nb_val; i++) {
    mpz_urandomb(plains, gmpRandState, 3);
    gettimeofday(&enc_1, NULL);
    djcs_t_encrypt(pk, hr, ciphers, plains);
    gettimeofday(&enc_2, NULL);

    for (int j = 0; j < nb_need; j++) {
      djcs_t_share_decrypt(vk, au[j], dec[j], ciphers);
    }
    djcs_t_share_combine(vk, res, dec);
    gettimeofday(&dec_2, NULL);

    enc_time += (double)((enc_2.tv_sec - enc_1.tv_sec) * 1000 +
                         (double)(enc_2.tv_usec - enc_1.tv_usec) / 1000);
    dec_time += (double)((dec_2.tv_sec - enc_2.tv_sec) * 1000 +
                         (double)(dec_2.tv_usec - enc_2.tv_usec) / 1000);
  }

  // Clean up
  for (int j = 0; j < nb_need; j++) {
    mpz_clear(dec[j]);
  }
  free(dec);

  mpz_clears(plains, ciphers, res, NULL);
  gmp_randclear(gmpRandState);

  for (int i = 0; i < nb_total; i++) {
    mpz_clear(si[i]);
    djcs_t_free_auth_server(au[i]);
  }
  free(si);
  free(au);

  djcs_t_free_polynomial(vk, coeff);
  hcs_free_random(hr);
  // djcs_t_clear_public_key(pk);
  // djcs_t_free_public_key(pk);
  // djcs_t_clear_private_key(vk);
  // djcs_t_free_private_key(vk);

  gmp_printf("KeyGen: %'.3f ms\n"
             "Encryption: %'.3f ms (on average)\n"
             "Decryption: %'.3f ms (in on average)\n"
             "Encryption: %'.3f ms (in total)\n"
             "Decryption: %'.3f ms (in total)\n",
             keygen_time, enc_time / nb_val, dec_time / nb_val, enc_time,
             dec_time);

  return 0;
}

[lemonviv]

Hi, thanks for sharing the test code. I just run the test and print the plaintext (i.e., plains) and the decryption result (i.e., res), and I find that the res here is always 0. I do not know what is wrong. Have you tested the homomorphic operations of the threshold cryptosystem?

Would be great and highly appreciated if you can provide a full example of threshold decryption and homomorphic operations. @tiehuis

Update: the djcs_t_share_decrypt function returns valid mpz_t values dec[j], but the result of djcs_t_share_combine function is always 0.

[MoienBowen]

Hi, thanks for sharing the test code. I just run the test and print the plaintext (i.e., plains) and the decryption result (i.e., res), and I find that the res here is always 0. I do not know what is wrong. Have you tested the homomorphic operations of the threshold cryptosystem?

Would be great and highly appreciated if you can provide a full example of threshold decryption and homomorphic operations. @tiehuis

Update: the djcs_t_share_decrypt function returns valid mpz_t values dec[j], but the result of djcs_t_share_combine function is always 0.

Emmm, I agree with you, it is always 0 for the decrypted result.
I forgot if I checked the result when I wrote the code...
@tiehuis can you please check it?

Thanks.

[lemonviv]

The problem is because of vk->n[0] is not initialized, it can be fixed by initializing vk->n[0] by pk->n[0] (please see #3).

[MoienBowen]

The problem is because of vk->n[0] is not initialized, it can be fixed by initializing vk->n[0] by pk->n[0] (please see #3).

I saw your comments, thanks. :)

[tiehuis]

Sorry I haven't replied here, been a bit inactive. I did notice I actually pushed an example of a voting application using this library to github quite a while ago. I have not tested it recently but at the time it worked as I expected.

https://github.com/tiehuis/libhcs-voting