Alternative Libraries

These are brief notes on the libraries that we looked at before embarking on writing our own.

Python Libraries

charm-crypto

> Charm is a framework for rapidly prototyping advanced cryptosystems. Based on > the Python language, it was designed from the ground up to minimize development > time and code complexity while promoting the reuse of components. > > Charm uses a hybrid design: performance intensive mathematical operations are > implemented in native C modules, while cryptosystems themselves are written in > a readable, high-level language. Charm additionally provides a number of new > components to facilitate the rapid development of new schemes and protocols.

http://charm-crypto.com/Main.html

Paillier Code, Pascal Paillier (Public-Key)

https://github.com/JHUISI/charm/blob/master/charm/schemes/pkenc/pkenc_paillier99.py

Worth looking at their object hierarchy, e.g., http://jhuisi.github.io/charm/toolbox/PKEnc.html They use a Ciphertext class which has the __add__ and __mul__ methods overridden.

Example:

>>> from charm.toolbox.integergroup import RSAGroup
>>> group = RSAGroup()
>>> pai = Pai99(group)
>>> (public_key, secret_key) = pai.keygen()
>>> msg_1=12345678987654321
>>> msg_2=12345761234123409
>>> msg_3 = msg_1 + msg_2
>>> msg_1 = pai.encode(public_key['n'], msg_1)
>>> msg_2 = pai.encode(public_key['n'], msg_2)
>>> msg_3 = pai.encode(public_key['n'], msg_3)
>>> cipher_1 = pai.encrypt(public_key, msg_1)
>>> cipher_2 = pai.encrypt(public_key, msg_2)
>>> cipher_3 = cipher_1 + cipher_2
>>> decrypted_msg_3 = pai.decrypt(public_key, secret_key, cipher_3)
>>> decrypted_msg_3 == msg_3
True

They have even got it going on Android: http://jhuisi.github.io/charm/mobile.html

mikeivanov/paillier

> Pure Python Paillier Homomorphic Cryptosystem

Very simple easy to understand code. Doesn’t use a Paillier object. No external dependencies. Based on the java library: https://code.google.com/p/thep/

https://github.com/mikeivanov/paillier

Example Usage:

>>> from paillier import *
>>> priv, pub = generate_keypair(128)
>>> x = encrypt(pub, 2)
>>> y = encrypt(pub, 3)
>>> x,y
(72109737005643982735171545918..., 9615446835366886883470187...)
>>> z = e_add(pub, x, y)
>>> z
71624230283745591274688669...
>>> decrypt(priv, pub, z)
5

encrypted-bigquery-client

License: Apache 2.0

> Paillier encryption to perform homomorphic addition on encrypted data

The ebq client is an experimental client which encrypts data in the specified fields before loading to Bigquery service. Currently there are various limitations including support for only a subset of query types on encrypted data.

Paillier specific code:

http://pydoc.net/Python/encrypted_bigquery/1.0/paillier/

Uses openssl via ctypes.

Features a Paillier object with the following methods:

  • __init__(seed=None, g=None, n=None, Lambda=None, mu=None)
  • Encrypt(plaintext, r_value=None)
  • Decrypt(ciphertext)
  • Add(ciphertext1, ciphertext2) - returns E(m1 + m2) given E(m1) and E(m2)
  • Affine(self, ciphertext, a=1, b=0) - Returns E(a*m + b) given E(m), a and b
  • EncryptInt64/DecryptInt64 - twos complement to allow negative addition
  • EncryptFloat/DecryptFloat - IEEE754 binary64bit where exponent <= 389

Code is well documented python2. Most arguments are long or int types. There is also a comprehensive unit test at http://pydoc.net/Python/encrypted_bigquery/1.0/paillier_test/

Even if we don’t reuse any of their code the tests would be great.

#### Floating point notes in code:

Paillier homomorphic addition only directly adds positive binary values, however, we would like to add both positive and negative float values of different magnitudes. To achieve this, we will:

  • represent the mantissa and exponent as one long binary value. This means that with 1024 bit n in paillier, the maximum exponent value is 389 bits.
  • represent negative values with twos complement representation.
  • Nan, +inf, -inf are each indicated by values in there own 32 bit region, so that when one of them is added, the appropriate region would be incremented and we would know this in the final aggregated value, assuming less than 2^32 values were aggregated.
  • We limit the number of numbers that can be added to be less than 2^32 otherwise we would not be able to detect overflows properly, etc.
  • Also, in order to detect overflow after adding multiple values, the 64 sign bit is extended (or replicated) for an additional 64 bits. This allows us to detect if an overflow happened and knowing whether the most significant 32 bits out of 64 is zeroes or ones, we would know if the result should be a +inf or -inf.

Project Home: https://code.google.com/p/encrypted-bigquery-client/

C/C++

Encounter

> Encounter is a software library aimed at providing a production-grade > implementation of cryptographic counters

To date, Encounter implements a cryptocounter based on the Paillier public-key cryptographic scheme

https://github.com/secYOUre/Encounter

FNP privacy-preserving set intersection protocol

A toolchain and library for privacy-preserving set intersection

It comes with rudimentary command-line interface: client, server, and key-generation tool. Extension and reuse is possible through C++ interfaces. The implementation is fully thread-aware and multi-core ready, thus computation time can be shortened by modern many-core machines. We have verified significant performance gains with quad-core Xeons and Opterons, through the use of bucket allocation in the algorithm.

For homomorphic encryption and decryption, both modified ElGamal cryptosystem and Paillier cryptosystem have been implemented on top of gmp. And yes, the source of randomness is always a headache for cryptosystem implementers; we have keyboard, file and network packet as the sources of entropy.

It requires OpenSSL, gmp, gmpxx, boost, pthread, and pcap to build. It currently runs on Linux.

http://fnp.sourceforge.net/

libpaillier

Library written in C and uses GMP. The privss toolkit for private stream searching is built on libpaillier.

http://hms.isi.jhu.edu/acsc/libpaillier/

### HElib

> HElib is a software library that implements homomorphic encryption (HE). > Currently available is an implementation of the Brakerski-Gentry-Vaikuntanathan > (BGV) scheme, along with many optimizations to make homomorphic evaluation runs > faster, focusing mostly on effective use of the Smart-Vercauteren ciphertext > packing techniques and the Gentry-Halevi-Smart optimizations. > > At its present state, this library is mostly meant for researchers working on > HE and its uses. Also currently it is fairly low-level, and is best thought of > as “assembly language for HE”. That is, it provides low-level routines (set, add, > multiply, shift, etc.), with as much access to optimizations as we can give. > Hopefully in time we will be able to provide higher-level routines.

https://github.com/shaih/HElib

Must read: http://tommd.github.io/posts/HELib-Intro.html

rinon/Simple-Homomorphic-Encryption

Another C++ fully homomorphic encryption implementation.

https://github.com/rinon/Simple-Homomorphic-Encryption

Javascript

Javascript Cryptography Considered Harmful - http://www.matasano.com/articles/javascript-cryptography/

mhe/jspaillier

Adds the methods to the Public and Private keys.

Dependencies: jsbn Demo Site: http://mhe.github.io/jspaillier/

p2p-paillier

> allows a peer to add two numbers over a peer-to-peer network. Peers add > these two numbers without even knowing what they are. It uses Firebase > (which is centralized) in order to push commands to the peers.

Demo: http://9ac345a5509a.github.io/p2p-paillier/ Code: https://github.com/9ac345a5509a/p2p-paillier

Haskell

There is a decent-looking haskell paillier library: https://github.com/onemouth/HsPaillier

BSD license

There’s just one test, which encrypts 37, decrypts it, and checks that it’s still 37.

Java

There are a bunch of paillier libraries for java.

Are there any tests?

UT Dallas

This one has documentation and two implementations:

https://www.utdallas.edu/~mxk093120/paillier/javadoc/paillierp/package-summary.html

Provides the structures and methods to encrypt data with the Paillier encryption scheme with thresholding. This package a simplified implementation of what is specified in the paper A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting by Damgård et al. Within this paper, the authors generalize the Paillier encryption scheme to permit computations modulo ns+1, allowing block length for encryption to be chosen freely. In addition to this undertaking, Damgård et al. also constructed a threshold variant of the scheme.

This package provides the following features of the paper
  • The degree of n is fixed to 1.
  • A fully functional simple Paillier encryption scheme with separate key classes for easy keysharing.
  • Proper Thresholding for an arbitrary number of decryption servers and threshold needed to decrypt.
  • Non-interactive zero knowledge proofs to ensure proper encryption and decryption.

Of particular note, this implementation is simple as s is fixed to be 1. This allows for simplicity at this stage of the design. Further, we hope to have added methods which would make the actual use of this package to be easy and flexible.

Future features would include support for encrypting arbitrary length strings/byte arrays to avoid padding issues.

BGU Crypto course

This one is also documented but is for a crypto course so I’m not sure how complete/practical it is intended to be. For example, it does its own keygen using java.util.Random. https://code.google.com/p/paillier-cryptosystem/

UMBC

This one is mercifully short but doesn’t implement add, multiply as functions or methods. Also it uses java.util.Random.

http://www.csee.umbc.edu/~kunliu1/research/Paillier.html