6
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

Here's a paper showing how to realize the BGN cryptosystem with a prime order group. You could implement the cryptosystem with PBC or one of the other paring libs.

"Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups"
David Mandell Freeman
Eurocrypt 2010

Have a look at slide 13 of the talk — the BGN example looks fairly simple. The following slide suggests that prime-order BGN will be more efficient at higher security levels too.

This is probably how I would implement it.

Improve this answer
$\endgroup$
2
  • $\begingroup$ BGN with prime order groups; that's just too cool. Thanks for making me aware of that paper! $\endgroup$
    – offsite
    Mar 14, 2012 at 17:23
  • 1
    $\begingroup$ You may also want to check out the bilinear map implementation in the RELIC library. (I think it's more actively maintained than PBC and includes newer techniques from the literature.) $\endgroup$
    – porkbun
    Mar 14, 2012 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.