Proposal: kyber.Group wrapper for libsecp256k1

[coventry]

I'm thinking of wrapping libsecp256k1 in the kyber.Group interface. I would use essentially the same structure as go-ethereum for this.

1. Would this be a welcome addition to kyber?
2. If there are any reasons why this is an obviously bad idea, I'd be glad to learn of them. My plan is to use it with the share/dkg and share/dss packages for ethereum crypto, where it's possible to do reasonably cheap Schnorr signatures. The Alt-BN128 curve, which the EVM precompiled contracts target, won't work for my purposes, and I can use ECRECOVER to do the arithmetic I need.

[jeffallen]

We welcome pull requests, but I cannot guarantee that this will be merged.

First, we need to respect a backwards compatibility commitment to those using kyber v3. If secp256k1 needs modifications to the main abstractions of kyber (Scalar and Point), that's a no-go. I would be open to discussing making Kyber v4 to support this, but it would need to be pretty compelling to justify that.

Next, we would like Kyber to remain pure Go, to make sure that building is still fast and easy for users (many of whom are students who are new to programming and new to Go). Thus other secp256k1's might be better choices:

• https://github.com/tendermint/tendermint/tree/master/crypto/secp256k1
• https://github.com/btcsuite/btcd/tree/master/btcec

Kyber will never be the fastest crypto library, but it should be fast enough while still being very easy to work with the prototype and develop novel applied crypto projects.

Finally, we'll need to look at license compatibility. You'll need to sign a CLAI or CLAC so that your contribution can be licensed like the rest of Kyber. (See https://github.com/dedis/cothority/blob/master/CONTRIBUTION) If your submitted code is simply a wrapper to adapt a dependency like tendermint's implementation to the Kyber API, easy. If you need to make modifications to the secp256k1 implementation in order to get access to the internals (we had to do this for both ed25519 and bn256), then you'll be forking their code and checking it into Kyber, in which case their code needs have a license that is compatible with Kyber's MPLv2 license.

[coventry]

Great. I actually did implement this with btcd in the end. Their handling of private keys (kyber Scalars) is backed by big.Ints, though. I'm planning to replace the Scalar implementation with libsecp256k1's, though with the symbol names changed to prevent linker conflicts with the go-ethereum packages.

[coventry]

Actually, I thought based on the algorithms they use to operate on the base field (field.go) that the btcd elliptic-curve arithmetic is constant time, but it seems to me now that their ScalarMult refrains from computing the addition for a doubling corresponding to a zero bit in the scalar, so it's not constant-time at all.

If you're interested in having a variable-time group implementation in kyber, I'll put together some unit tests for the btcd wrapper (so far I've just tested it with integration with the kyber dss and dkg packages), and post a PR next week, hopefully.

At some point, due to this timing issue, I'll probably have to move to using libsecp256k. That is "pure go" in the sense that it still builds with go build, but it does involve C code, built transparently using cgo. If that's unacceptable, tendermint probably is, too, since they copied their implementation from go-ethereum.

[jeffallen]

Variable time algorithms are now ok in Kyber, because we found that the risks of not having Bn256 (i.e. attacks on CoSi) were worse than the risks of using variable time algorithms.

cgo is not welcome because it makes compilation depend on things other than "go get" (i.e. external libraries, C compilers, etc).

The goal of Kyber is to be a toolbox to let students and researchers do applied cryptography with the best known implementations of the underlying crypto. Any software engineering bumps in the road need to be avoided, as students and researchers already have enough on their plates, just trying to prototype these new ideas.

[coventry]

Thanks, Jeff. I just posted a PR for this in #385.

[jeffallen]

See #385 for why this is closed; it's a good idea, but the core team is not working on it, and @coventry will not be able to finish it.