Additively homomorphic ElGamal

elagamal_test.go

package dlog

import (
	"errors"
	"fmt"

	"github.com/dedis/crypto/abstract"
	"github.com/dedis/crypto/nist"
	"github.com/dedis/crypto/random"
)

var suite = nist.NewAES128SHA256P256()

// most simple, naive implementation of a discrete log table (uses the base point of the underlying group)
func newDlogMap(N int, P abstract.Point) map[string]int64 {
	// Points seem to be not comparable (by '==') we use their string representation instead
	tab := make(map[string]int64)

	for i := 0; i < N; i++ {
		Base := suite.Point().Base()
		s := suite.Secret().SetInt64(int64(i))
		pow := Base.Mul(P, s)
		tab[pow.String()] = int64(i)
	}
	return tab
}

func ElGamalEncryptInt(suite abstract.Suite, pubkey abstract.Point, message int64) (
	K, C abstract.Point, remainder []byte) {

	// Embed the message in a abstract.Secret
	s := suite.Secret().SetInt64(message)
	B := suite.Point().Base()
	M := B.Mul(B, s)
	B = suite.Point().Base()

	// ElGamal-encrypt the point to produce ciphertext (K,C).
	k := suite.Secret().Pick(random.Stream) // ephemeral private key
	K = suite.Point().Mul(nil, k)           // ephemeral DH public key
	S := suite.Point().Mul(pubkey, k)       // ephemeral DH shared secret
	C = S.Add(S, M)                         // message blinded with secret
	return
}

func ElGamalDecryptInt(suite abstract.Suite, prikey abstract.Secret, K, C abstract.Point) (
	message int64, err error) {
	dlogs := newDlogMap(50, suite.Point().Base())

	// ElGamal-decrypt the ciphertext (K,C) to reproduce the message.
	S := suite.Point().Mul(K, prikey) // regenerate shared secret
	M := suite.Point().Sub(C, S)      // use to un-blind the message
	m, ok := dlogs[M.String()]        // extract the embedded data
	if !ok {
		return 0, errors.New("Could not find discrete log")
	}
	message = m
	return
}


func Example_elGamalEncryption() {

	// Create a public/private keypair
	a := suite.Secret().Pick(random.Stream) // Alice's private key
	A := suite.Point().Mul(nil, a)          // Alice's public key

	// ElGamal-encrypt a message using the public key.
	m := int64(12)
	K, C, _ := ElGamalEncryptInt(suite, A, m)

	m2 := int64(11)
	K2, C2, _ := ElGamalEncryptInt(suite, A, m2)

	kSum := suite.Point().Add(K, K2)
	cSum := suite.Point().Add(C, C2)
	// Decrypt it using the corresponding private key.
	mm, err := ElGamalDecryptInt(suite, a, kSum, cSum)
	//fmt.Print(mm)
	// Make sure it worked!
	if err != nil {
		panic("decryption failed: " + err.Error())
	}
	if mm != (m + m2) {
		panic(fmt.Sprintf("decryption produced wrong output: %d", mm))
	}
	println("Decryption succeeded: ", mm)
	// Output:
}