How To Prove An Election

How To Prove An Election

Well. In the UK we are going through a strange political drama just now, and the current government is asking for another general election on 12 December 2019. So it will be out with the printed cards, the paper registers, the pencil, the votes in a van, and the human counting, again. In previous elections there have been many cases of where there was a recount, and each time the count came out differently. So how can we create a simple signature that would account for every vote cast, and where everyone could check the results?

What we need is to issue every voter with a unique ID (associated with a private key). From this private key, the voter will be able to generate a public key, and which will be used to verify their vote. Once they cast their vote, each voter will take a hash of the vote, and then encrypt this with their private key, and each voter will then create a signature for their vote. Trent can then take a copy of the signature and check it against the vote. The checking is done with the public key of the voter. Trent can then gather all the signatures and public keys, and create a merged public key and a merged signature, and which can then be verified for their trustworthiness, and that all the votes have been taken into account. Let’s say there’s Bob, Alice and Carol voting, we then get:

And so one of the most amazing things about crypo pairing is that you can merge public keys into a single public key (W), and can also merge all the generated signatures from a message into a single signature (SIG). For this you might have a hundred public keys used, and would then have 100 signatures, and where each signature was signed by one of the 100 signers. This becomes a significant overhead in storing and processing the signatures.

With this we can use h crypto pairing, and where we can merge the public keys of (W1…Wn) with:

W = W1 + W2 + W3 + … Wn

and then take the private keys of the signers (S1 … Sn) and create n signtures (SIG1 … SIGn). The merged signature is then:

SIG= SIG1 + SIG2 + SIGn

We can then test the merged public key with the signature, and can verify that each of the public keys signed the message. Overall, a compressed public key and signature takes up just 33 bytes of space.

In crypto pairing we have two elliptic curves curves (G1 and G2), and where our signature adds points on the G1 curve, and the public key on the G2 curve. And so, I grabbed some crypto pairing code from Miracl, and wrote a small test program which merges two public keys and two signatures, and then proves them [here]. For the merging of the public keys we add points on the G2 curve:

func addW(W1 []byte, W2 []byte, W [] byte) (int)  {	
        P := BN254.ECP2_fromBytes(W1)
	Q := BN254.ECP2_fromBytes(W2)
	P.Add(Q)
	P.ToBytes(W[:],true)
	return 0}

For the merging of the signatures, we add the points on the G1 curve:

func addS(S1 []byte, S2 []byte, S [] byte) (int)  {	
        P := BN254.ECP_fromBytes(S1)
	Q := BN254.ECP_fromBytes(S2)
	P.Add(Q) 
	P.ToBytes(S[:],true)
	return 0}

The overall code is [here]:

The coding is here:

package main

import "fmt"
import "os"
import "github.com/miracl/core/go/core"
import "github.com/miracl/core/go/core/BN254"



func printBinary(array []byte)(s string)  {
        s= "" 
	for i := 0; i < len(array); i++ {
	s = s+ fmt.Sprintf("%02x", array[i])
		
	}
	
	return
}
func addW(W1 []byte, W2 []byte, W [] byte) (int)  {

	P := BN254.ECP2_fromBytes(W1)
	Q := BN254.ECP2_fromBytes(W2)
	P.Add(Q)
	P.ToBytes(W[:],true)
	return 0

}
func addS(S1 []byte, S2 []byte, S [] byte) (int)  {

	P := BN254.ECP_fromBytes(S1)
	Q := BN254.ECP_fromBytes(S2)
	P.Add(Q) 
	P.ToBytes(S[:],true)
	return 0

}

func salt(rng *core.RAND)(IKM [32]byte) {


	for i:=0;i&li;32;i++ {

	        IKM[i]=byte(rng.GetByte())
	}
	return
	
}




func Core_Verify1(SIG []byte, M []byte, W []byte) int {
	HM := BN254.Bls_hash_to_point(M)
	
	D := BN254.ECP_fromBytes(SIG)
	if !BN254.G1member(D) {return BN254.BLS_FAIL}
	D.Neg()

	PK := BN254.ECP2_fromBytes(W)

	// Use new multi-pairing mechanism

	r :=  BN254.Initmp()
	 BN254.Another_pc(r, BN254.G2_TAB, D)
	 BN254.Another(r, PK, HM)
	v :=  BN254.Miller(r)


	v = BN254.Fexp(v)

	if v.Isunity() {
		return BN254.BLS_OK
	} else {
		return BN254.BLS_FAIL
	}
}

func main() {

	const BGS = BN254.BGS
	const BFS = BN254.BFS
	const G1S = BFS + 1 /* Group 1 Size */
	const G2S = 2 * BFS + 1 /* Group 2 Size */

        var S1 [G1S]byte
        var W1 [G2S]byte
        var S2 [G1S]byte
        var W2 [G2S]byte

        var W [G2S]byte
        var SIG [G1S]byte
        var SIG1 [G1S]byte
        var SIG2 [G1S]byte
	var IKM [32]byte


	rng := core.NewRAND()
	var raw [100]byte
	for i := 0; i < 100; i++ {
		raw[i] = byte(i + 1)
	}
	rng.Seed(100, raw[:])



    	IKM = salt(rng)

	mess := "This is a test message"

	argCount := len(os.Args[1:])

	if (argCount>0) {mess = string(os.Args[1])}



	res1 := BN254.Init()
	if res1 != 0 {
		fmt.Printf("Failed to Initialize\n")
		return
	}

	res1 = BN254.KeyPairGenerate(IKM[:], S1[:], W1[:])

	if res1 != 0 {
		fmt.Printf("Failed to generate keys\n")
		return
	}

	IKM = salt(rng)

	res2 := BN254.Init()
	if res2 != 0 {
		fmt.Printf("Failed to Initialize\n")
		return
	}

	res2 = BN254.KeyPairGenerate(IKM[:], S2[:], W2[:])
	if res2 != 0 {
		fmt.Printf("Failed to generate keys\n")
		return
	}




	BN254.Core_Sign(SIG1[:], []byte(mess), S1[:])
	BN254.Core_Sign(SIG2[:], []byte(mess), S2[:])






	addW(W1[:],W2[:],W[:])

	addS(SIG1[:],SIG2[:],SIG[:])


	fmt.Printf("\nBoneh-Lynn-Shacham BLS signature with aggregation\n")
	
	fmt.Printf("Message: %s\n", mess)
	fmt.Printf("Private key 1: 0x%s\n", printBinary(S1[:]))
	fmt.Printf("Private key 2: 0x%s\n", printBinary(S2[:]))
	fmt.Printf("\nPublic key 1: 0x%s\n", printBinary(W1[:]))
	fmt.Printf("Public key 2: 0x%s\n", printBinary(W2[:]))
	fmt.Printf("\nSignature  1: 0x%s\n", printBinary(SIG1[:]))
	fmt.Printf("Signature 2: 0x%s\n", printBinary(SIG2[:]))

	fmt.Printf("\nMerged public key: 0x%s\n", printBinary(W[:]))
	fmt.Printf("Merged signarture: 0x%s\n\n", printBinary(SIG[:]))
	

	res1 = Core_Verify1(SIG[:], []byte(mess),W[:])

	if res1 == 0 {
		fmt.Printf("Signature is OK\n")
	} else {
		fmt.Printf("Signature is *NOT* OK\n")
	}
	

}

And a sample run:

Boneh-Lynn-Shacham BLS signature with aggregation
Message: Hello
Private key 1: 0x070e2c5972ccd123d226e4154af268ffe991547770bad5851f8504fe5c8321c300
Private key 2: 0x15eeee5e0798df883c3061e3d5d43ba6058ea2260fdff6b85f06ef500e64e7e900

Public key 1: 0x020f0df48aba4e7b11d8afbf6a2805d79ca9604c8940ab0ff24d092899074ecd641215e6ea01f97405ad6f285c332c6a13496bd456ef41a23278995e2b8aaf0c23
Public key 2: 0x020d58567bf38c4a28477f05caac740211ff9cefe6ad731ffc0331766751d1f8e31bdbf8084cf839fdd91d07e4744bd70c4c11dffd0e1e1d1e0692844c4e19e90a

Signature  1: 0x0218106169bd8fbb3b064caf9c0451deece2b5efdf690e5e2d3a6a241645a3e83a
Signature 2: 0x020c803ea9279cdda2883bdf5e1eee0d984fcb55ff8fb6f26ac9fc2bfba49a6230

Merged public key: 0x0309d39b921ff8cadee540eaf445292ec771e49933ad7ccb4d19aa17fe25464e3c031e9578c891c7e44590f446c1a6c87da14b4e342dd98f5ecdf9180410afe527
Merged signarture: 0x021972f3b104d6ff59d89a3969a453acbc0ab66bb75b16dd2354035255bbbaf631

Signature is OK

And for us in the UK, who knows where we are going, and what will happen. At least a bit of crypto can take our minds away from …