Question: If you had to implement BGN, how would you do it?
I'm looking for an implementation of the public-key cryptosystem due to Boneh, Goh, and Nissim (aka BGN), or at least some suggestions on implementing it myself. My goals are to explore/learn/play around with its structure, and, eventually, to produce some kind of timing data.
For those not familiar with BGN, it offers homomorphic addition of plaintexts (similar to Paillier and exp. Elgamal), but also a single homomorphic multiplication. So you can do things like homomorphically evaluate quadratic functions (with some bounds, mind you), or even do binary range proofs without a random oracle. Thus it seems like it would be incredibly useful in a range of cryptographic protocols, yet I can't seem to find an existing implementation, nor can I seem to account for why it hasn't been done already.
Nevertheless, it's not exactly something you can just whip up in Mathematica (with apologies to @PulpSpy).
Stanford's Pairing Based Crypto library (PBC) seems like a possible place to begin, but I don't know enough about the elliptic curves or pairings to modify their default curves to the one suggested in the paper. For example, the order of the default curve in PBC is based on a Solinas prime, whereas the order of the underlying curve in BGN is a prime that is functionally dependent on a large semiprime $n=q_1q_2$ such that the order of the bilinear group is $n$. The point is, it might take some doing to get PBC working for a BGN implementation.
Maybe CHARM would be a better option. Any thoughts?