additively homomorphic cryptosystem

[Vadym Fedyukovych]

Hello list,

attached is a homomorphic cryptosystem.
This code works for me.

It might be useful for counting encrypted votes
or some other arithmetics over encrypted data.

This design combine trapdoor of ElGamal cryptosystem and
easy logarithm in the group of roots of unity of Paillier.
It use a group of p-roots in the ring modulo p-square
with prime p.
Similar design was presented earlier (see references inside)
with modulus factorization considered the trapdoor.

Hope this message might trigger some interest to
"prime-square" groups and careful security evaluation
of this particular cryptosystem

Vadym Fedyukovych



-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

/* A variant of cryptosystem combining design features of Paillier and ElGamal,
 * using a subgroup of square residues in the ring modulo a prime square, $p^2$.
 * Homomorphic operation is addition of plaintex, multiplication of ciphertext.
 * Easy DL in the subgroup of p-th roots of unity.
 *
 * It's likely that patent on Paillier cryptosystem does not apply here.
 *
 * Original cryptosystem was described by Bresson, Catalano and Pointcheval in
 * "A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism
 *  and Its Applications", ASIACRYPT 2003.
 * Another source is BRICS report RS-03-16 of Damgard and Jurik, 2003.
 * Both use group of hidden order and RSA-like modulus, a composite square.
 *
 * Fair warning: it is still unknown to me exactly how hard DL problem is
 * in the group of square residues modulo a prime square.
 * V.M.Sidelnikov paper on Ferma quotients and a note of M.A.Cherepnev
 * (both in Russian) might be useful.  http://www.cryptography.ru/
 *
 * Written and placed in the public domain by Vadym Fedyukovych, 2005.
 */

#include <cryptlib.h>
#include <files.h>
#include <dh.h>
#include <osrng.h>

USING_NAMESPACE(std)
USING_NAMESPACE(CryptoPP)

typedef struct cphtext_st {
  Integer a, b;
} cphtext;

class sqp {
private:
  Integer p, p2, q, g;
  Integer priv_key, pub_key;
public:
  void generate_parameters(RandomNumberGenerator &rng, int mod_size, int 
ord_size);
  Integer get_modulus() { return p2; };
  Integer get_order() { return q; };
  Integer get_generator() { return g; };
  Integer get_prime_modulus() { return p; };
  void saveDER_parameters(BufferedTransformation &bt);
  void loadBER_parameters(BufferedTransformation &bt);

  void generate_keypair(RandomNumberGenerator &rng);
  Integer get_pubkey() {return pub_key;};
  // todo: save and load keys

  cphtext * encrypt(Integer plaintext, RandomNumberGenerator &rng);
  Integer decrypt(cphtext *ciphertext);
};

void sqp::generate_parameters(RandomNumberGenerator &rng, int modulus_sz, int 
order_sz) {
  DL_GroupParameters_GFP group_prm;
  const NameValuePairs &bsize =
    MakeParameters("ModulusSize", modulus_sz)("SubgroupOrderSize", order_sz);
  group_prm.GenerateRandom(rng, bsize);

  p = group_prm.GetModulus();
  p2 = p*p;  // yes, using a ring modulo a prime square, p^2
  q = group_prm.GetSubgroupOrder();
  Integer tg = group_prm.GetSubgroupGenerator();
  g = tg*tg; // enforce g is a square residue \pmod{p^2}
}

void sqp::saveDER_parameters(BufferedTransformation &bt) {
  DERSequenceEncoder parameters(bt);
    p2.DEREncode(parameters);
    p.DEREncode(parameters);
    q.DEREncode(parameters);
    g.DEREncode(parameters);
  parameters.MessageEnd();
}

void sqp::loadBER_parameters(BufferedTransformation &bt) {
  BERSequenceDecoder parameters(bt);
    Integer tp2(parameters);
    Integer tp(parameters);
    Integer tq(parameters);
    Integer tg(parameters);
  parameters.MessageEnd();

  p2 = tp2;
  p = tp;
  q = tq;
  g = tq;
}

void sqp::generate_keypair(RandomNumberGenerator &rng) {
  Integer r(rng, Integer::One(), p2 - 1);
  priv_key = r;
  pub_key = a_exp_b_mod_c(g, r, p2); // g^{priv_key} \pmod{p^2}
}

cphtext * sqp::encrypt(Integer plaintext, RandomNumberGenerator &rng) {
  cphtext *cph = new cphtext;
  Integer r(rng, Integer::One(), p2 - 1);
  cph->a = a_exp_b_mod_c(g, r, p2);
  cph->b = a_times_b_mod_c(
               a_exp_b_mod_c(pub_key, r, p2),
               a_exp_b_mod_c(p+1, plaintext, p2),
               p2);
  return cph;
}

Integer sqp::decrypt(cphtext *ciphertext) {
  Integer x, y, pr, pq;
  x = a_exp_b_mod_c(ciphertext->a, priv_key, p2);
  y = a_times_b_mod_c(ciphertext->b, x.InverseMod(p2), p2) - 1;
  Integer::Divide(pr, pq, y, sqp::p);
  // verify NotZero(pr) (that is, it was a correct ciphertext)
  return pq;
}

#if 0
#define NUM_TESTS 1000

int main() {
  int modulus_sz=1024, order_sz=128;
  const char *prmFilename = "group_parameters.der";
  FileSink prmFile(prmFilename);
  NonblockingRng rng;

  class sqp sq;
  sq.generate_parameters(rng, modulus_sz, order_sz);
  sq.saveDER_parameters(prmFile);

  int j, err;
  cphtext *cph;
  Integer probe;
  for(j=0, err=0; j<NUM_TESTS; j++) {
    sq.generate_keypair(rng);

    // get a random plaintext
    Integer pltext(rng, Integer::One(), sq.get_prime_modulus() - 1);

    cph = sq.encrypt(pltext, rng);
    probe = sq.decrypt(cph) - pltext;
    free(cph);

    if(probe.NotZero())
      err++;
  }
  if(err == 0)
    cout << "Correct decryption" << endl;
  return 0;
}
#endif
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDQD2aubns3bQu/lwRAkPpAJ0TfIcGqj5VI720PQK8TCy5ffpPLgCeJIoV
S6ji6jfWYdh1gVLuwSnOQxY=
=oSGK
-----END PGP SIGNATURE-----