kyber
kyber copied to clipboard
dedis
Embedding on bn256
I added embedding on G1 for the bn256 package. I think a discussion about the adapters is required since I don't think what I have done here will maintain compatibility, namely, the adapter is returning a G1 for Point() and not a G2.
@taybart why is the change in the adapter necessary ? Do you need to create G1 points ? The adapter is just a hacky way to fit the Suite interface but you have access to a pairing suite that let you do something like suite.G1().Point().
@Gilthoniel I was confused about how to actually use the kyber suite when I started. Sorry about that, the hack is removed!
Does it look OK otherwise? I am using this code to test it (mostly lifted from the ElGamal example in ed25519):
package main
import (
"fmt"
"go.dedis.ch/kyber/v3"
"go.dedis.ch/kyber/v3/pairing"
"go.dedis.ch/kyber/v3/util/random"
)
func elGamalEncrypt(suite pairing.Suite, pubkey kyber.Point, message []byte) (
K, C kyber.Point, remainder []byte) {
// Embed the message (or as much of it as will fit) into a curve point.
M := suite.G1().Point().Embed(message, random.New())
max := suite.G1().Point().EmbedLen()
if max > len(message) {
max = len(message)
}
remainder = message[max:]
// ElGamal-encrypt the point to produce ciphertext (K,C).
k := suite.G1().Scalar().Pick(random.New()) // ephemeral private key
K = suite.G1().Point().Mul(k, nil) // ephemeral DH public key
S := suite.G1().Point().Mul(k, pubkey) // ephemeral DH shared secret
C = suite.G1().Point().Add(S, M) // message blinded with secret
return
}
func elGamalDecrypt(suite pairing.Suite, prikey kyber.Scalar, K, C kyber.Point) (
message []byte, err error) {
// ElGamal-decrypt the ciphertext (K,C) to reproduce the message.
S := suite.G1().Point().Mul(prikey, K) // regenerate shared secret
M := suite.G1().Point().Sub(C, S) // use to un-blind the message
message, err = M.Data() // extract the embedded data
return
}
func main() {
suite := pairing.NewSuiteBn256()
// Create a public/private keypair
a := suite.G1().Scalar().Pick(suite.RandomStream()) // Alice's private key
A := suite.G1().Point().Mul(a, nil) // Alice's public key
// ElGamal-encrypt a message using the public key.
m := []byte("The quick brown fox")
K, C, _ := elGamalEncrypt(suite, A, m)
// Decrypt it using the corresponding private key.
mm, err := elGamalDecrypt(suite, a, K, C)
// Make sure it worked!
if err != nil {
fmt.Println("decryption failed: " + err.Error())
} else if string(mm) != string(m) {
fmt.Println("decryption produced wrong output: " + string(mm))
} else {
fmt.Println("Decryption succeeded: " + string(mm))
}
}
I included examples/bn256_enc_test.go. Not sure what you mean about the test being weak. I am willing to add more tests if you point me in the right direction.
Sorry I wasn't clear enough. I was talking about the test that makes sure a point is actually on the curve (you subtract the point and check if it is null). Another guy will have a look at that before we move forward.
Sounds good, I could add the isOnCurve check. I couldn't find a good source to check if the point is in the group or not. The other method I saw was to multiply the point by the order of the group and check if it is at infinity.
One last thing I need to ask you is to sign this CLA. This is required because of our partnership with the Industry. If you agree to sign, you can send it to me at gaylor.bosson[at]epfl.ch.
The method implemented in this PR doesnt run in constant time, and could bring security issues in the future if not used appropriately. (for example, Dragonbleed attack on wpa3.0)
It would be better to implement a constant-time method, for example using the one in https://godoc.org/github.com/cloudflare/bn256#HashG1 which is aligned to the WIP specification of hash to curve Internet standard.
@armfazh embedding a hash on a curve kinda defeats El Gamal right? The data needs to be recoverable and hashing it would destroy the original message
@armfazh embedding a hash on a curve kinda defeats El Gamal right? The data needs to be recoverable and hashing it would destroy the original message
Right, the hash to curve is a one-way function, for ElGamal, it's required a reversible function.
Hi @taybart , Sorry for the long delay. As you can see, a number of issues and PRs have remained open in the last months without much response. This was due to a temporary organizational situation. That's changing, so we're going to resume addressing the issues, reviewing and merging the PRs, etc. Please hang in there, we'll get back to you in the coming weeks. Thank you for your understanding.
Would it be possible to get this merged?
As a first step, please make sure that all tests pass.
@ineiti Do you have the SONAR_TOKEN? Is that being set with github secrets? Sonarcloud scan is the thing that is failing
I could merge this into a branch in this org/repo and then make a new pr with that branch? That should make the secrets available
According to GitHub:
Secrets are not passed to workflows that are triggered by a pull request from a fork.
We use secrets to provide the Sonar token to the GitHub Action.
For many years, there was no solution, but apparently we should be able to do this now: https://community.sonarsource.com/t/how-to-use-sonarcloud-with-a-forked-repository-on-github/7363/30
I haven't personally got time to look into improving the GitHub Actions configuration right now. Anyone keen to fix this ? @ineiti @nkcr @jbsv
What @taybart proposes is perhaps the quickest solution, until somebody has the time to do it correctly: create a branch on this repo with the content of @taybart 's master branch, and then create a PR with that.
Sorry it took so long. I added a new PR here: #475 - can you look if that is the correct, latest version?
Shall we close this PR?