BeleniosRF Client Speedtest

readme.md

BeleniosRF Client speedtest

All the BeleniosRF and GS related stuff are in the files:

• TestJS-BEL-GS.html (barebones booth speedtest)
• belenios-booth.js (most of the crypto lives here)

You can also use TestJS-BEL-GS.html?k=value to select values for k. The paper uses 1, 5, 10 and 25.

The test expects a MIRACL IOT/ Milagro library to be present in the /lib folder.

belenios-booth.js

//returns rng object and generators P,Q for G1,G2 as well as order
initcrypto = function(){
        //boilerplate MIRACL init, and base generators
		var RAW=[];
		for (i=0;i<100;i++) RAW[i]=i+1;		
		var rng=new RAND();
		rng.clean();
		rng.seed(100,RAW);

    	var n=new BIG(0); n.rcopy(ROM.CURVE_Order);
    	var p=new BIG(0); p.rcopy(ROM.Modulus);
    	var B=new BIG(0); B.rcopy(ROM.CURVE_B);

		//from ECDH
		//get generator P for G1

    	P=new ECP(0);
        gx=new BIG(0); gx.rcopy(ROM.CURVE_Gx);
		if (ROM.CURVETYPE!=ROM.MOMTGOMERY)
		{
			gy=new BIG(0); gy.rcopy(ROM.CURVE_Gy);
			P.setxy(gx,gy);
		}
		else P.setx(gx);
		
		//get generator Q for G2
		var A=new BIG(0);
		var B=new BIG(0);
		A.rcopy(ROM.CURVE_Pxa); B.rcopy(ROM.CURVE_Pxb);
		var QX=new FP2(0); QX.bset(A,B);
		A.rcopy(ROM.CURVE_Pya); B.rcopy(ROM.CURVE_Pyb);
		var QY=new FP2(0); QY.bset(A,B);

		var Q=new ECP2();
		Q.setxy(QX,QY);

		//var s=BIG.fromBytes(S);
		//Q=PAIR.G2mul(Q,s);
		return{
		    rng:rng,
		    n:n,
		    p:p,
		    g1:P,
		    g2:Q
		}    
}


//creates election keys used for ecnrypting stuff (UE,a)
//creates z and usig for the modified signature scheme(z,usig[k+1])
//creates extractable CRS for GS proofs (ui[2],vi[2])
//SK is not used anywhere as of right now
electionkeys=function(params){        
        
        
        //ElGamal
        var a=new FP(BIG.randomnum(params.n,params.rng))
        //note, we can't mul with a, we must mul with a.f because mul expects BIG, not FP 
		var UE=new ECP();
		UE.copy(params.g1);
		UE.mul(a.f);
		
		var UE2=new ECP2();
		UE2.copy(params.g2);
		UE2.mul(a.f);
		
		
		//z is used to generate user keys for the waters signature
		var temp=new FP(BIG.randomnum(params.n,params.rng))
        //note, we can't mul with a, we must mul with a.f because mul expects BIG, not FP 
		var z=new ECP();
		z.copy(params.g1);
		z.mul(temp.f);
		
		//usig[i] --used for the F hash function of the waters signature in the paper
		var usig= new Array(k+1);
		for (i=0;i<=k;i++){
		    temp=new FP(BIG.randomnum(params.n,params.rng))
		    usig[i]=new ECP();
		    usig[i].copy(params.g1);
		    usig[i].mul(temp.f);
		}
		
		//h1,h2 used for the message hash in the paper
		temp=new FP(BIG.randomnum(params.n,params.rng))
		h1=new ECP();
		h1.copy(params.g1);
		h1.mul(temp.f);
		
		temp=new FP(BIG.randomnum(params.n,params.rng))
		h2=new ECP();
		h2.copy(params.g1);
		h2.mul(temp.f);
		
		
		//GS u1,u2, v1,v2 (u in G1, v in G2, note that ui,vi are all tuples!)
		//this is an extractable CRS so, the second pair is a multiple of the first
		
		var u1= new Array(2);
		var u2= new Array(2);
		var t=new FP(BIG.randomnum(params.n,params.rng)) //t is rel between 1,2
	    temp=new FP(BIG.randomnum(params.n,params.rng)) //temp is rel between g1 and u1[1]

		
		u1[0]=new ECP();
		u1[1]=new ECP();
		u1[0].copy(params.g1);
		u1[1].copy(params.g1);
		u1[1].mul(temp.f);

		for (i=0;i<2;i++){
		    u2[i]=new ECP();
		    u2[i].copy(u1[i]);
		    u2[i].mul(t.f);		    
		}
        var uaux=new ECP(); //used for si1 function.
        uaux.copy[u2[1]];
        uaux.add(params.g1);

		var v1= new Array(2);
		var v2= new Array(2);
		t=new FP(BIG.randomnum(params.n,params.rng)) //refresh
		temp=new FP(BIG.randomnum(params.n,params.rng)) //refresh 

		
		v1[0]=new ECP2();
		v1[1]=new ECP2();
		v1[0].copy(params.g2);
		v1[1].copy(params.g2);
		v1[1].mul(temp.f);

		for (i=0;i<2;i++){
		    v2[i]=new ECP2();
		    v2[i].copy(v1[i]);
		    v2[i].mul(t.f);		    
		}
		var vaux=new ECP2();
        vaux.copy[v2[1]];
        vaux.add(params.g2);

        //GS helper functions see paper

        gi1=function(ge){
        t1=new ECP();
        t2=new ECP();
        t2.copy(ge);
        return [t1,t2];
        }

        gi2=function(ge){
        t1=new ECP2();
        t2=new ECP2();
        t2.copy(ge);
        return [t1,t2];
        } 
        
        si1=function(sca){
        t1=new ECP();
        t2=new ECP();
        t1.copy(u2[0]);
        t1.mul(sca.f);
        t2.copy(uaux);
        t2.mul(sca.f);
        return [t1,t2];
        }
        
        si2=function(sca){
        t1=new ECP2();
        t2=new ECP2();
        t1.copy(v2[0]);
        t1.mul(sca.f);
        t2.copy(vaux);
        t2.mul(sca.f);
        return [t1,t2];
        }
           
        F=function(mvector){
        if ((mvector.length)!=k) alert('size mismatch! ',k,' ',mvector.length);
        wh=new ECP();
        wh.copy(usig[0]);
        for (i=0;i<mvector.length;i++)
            if (mvector[i]!=0) wh.add(usig[i+1]);
        return wh;
        }
        
        //commit scalar in G1
        coms1=function(sca,r){
        t=si1(sca);
        
        t1=new ECP();
        t1.copy(u1[0]);
        t1.mul(r.f);
        t[0].add(t1);

        t1.copy(u1[1]);
        t1.mul(r.f);
        t[1].add(t1);        
        
        return t;
        }
        
        //commit scalar in G2
        coms2=function(sca,r){
        t=si2(sca);
        
        t1=new ECP2();
        t1.copy(v1[0]);
        t1.mul(r.f);
        t[0].add(t1);

        t1.copy(v1[1]);
        t1.mul(r.f);
        t[1].add(t1);        
        
        return t;
        }    
        
        //commits ge in G1
        comg1=function(ge,r1,r2){
        t=gi1(ge);
        
        t1=new ECP();
        t1.copy(u1[0]);
        t1.mul(r1.f);
        t[0].add(t1);
        t1.copy(u2[0]);
        t1.mul(r2.f);
        t[0].add(t1);
        

        t1=new ECP();
        t1.copy(u1[1]);
        t1.mul(r1.f);
        t[1].add(t1);
        t1.copy(u2[1]);
        t1.mul(r2.f);
        t[1].add(t1);        
        return t;
        } 
		
		return{
    		PK:{UE:UE,UE2:UE2,z:z,usig:usig,u1:u1,u2:u2,v1:v1,v2:v2,uaux:uaux,vaux:vaux,si1:si1,si2:si2,gi1:gi1,gi2:gi2,F:F,coms1:coms1,coms2:coms2,comg1:comg1,h1:h1,h2:h2},
	    	SK:{a:a}
		}
}

		
//creates user signature keys Y/ X1,X2
userkeys=function(params,ePK){
        
        var x=new FP(BIG.randomnum(params.n,params.rng));
        
		var X1=new ECP();
		X1.copy(params.g1);
		X1.mul(x.f);
		
		var X2=new ECP2();
		X2.copy(params.g2);
		X2.mul(x.f);
		
		var Y=new ECP();
		Y.copy(ePK.z);
		Y.mul(x.f);
		
		
		return{
		    PK:{X1:X1,X2:X2},
		    SK:{Y:Y}
		}
}

encryptchoice=function(params,ePK,uPK,mvec){
        var c=[];
        var r=new FP(BIG.randomnum(params.n,params.rng));
        FM=ePK.F(mvec);
        

        //note that as of this writing the ECP constructor is stupid and
        //ECP(ePK.X) produces the point at infinity, -NOT- a copy of X.
        //checked the source too.

        c[1]=new ECP();
        c[1].copy(ePK.UE);
        c[1].mul(r.f);
        c[1].add(FM);
        
        c[2]=new ECP();
        c[2].copy(params.g1);
        c[2].mul(r.f);
        
        var m=MPIN.hashit(0,uPK);  //0 because function takes optional argument
        //c[3]=MPIN.mapit(m); OLD, ROM version
        m=BIG.fromBytes(m);
		m.mod(params.p);
        
        c[3]=new ECP();
        c[3].copy(ePK.h1)
        c[3].mul(m)
        c[3].add(ePK.h2)
        
        c[3].mul(r.f);

        
        r=r;
        W=new ECP();
        W.copy(uPK.X1);
        W.mul(r.f);
                
        return [c,r,W];
}

checkenc=function(c,ePK,uPK){
        ///// USELESS CHECKS ///////////

        window.document.write("Check skipped<br>");
        return 1        
}


//This procuces a signature sig on a ciphertext c given an election public key ePK
sign_nocheck=function(c,ePK,uSK,uPK){
        var sig=[];
        var s=new FP(BIG.randomnum(params.n,params.rng));

        //mul expects BIGs, so FPs must be FP.f
        sig[1]=new ECP();
        sig[1].copy(c[1]);
        sig[1].mul(s.f);
        sig[1].add(uSK.Y);
        
        sig[2]=new ECP();
        sig[2].copy(c[2]);
        sig[2].mul(s.f);
        
        sig[3]=new ECP();
        //sig[3].copy(ePK.UE);
        //sig[3].mul(s.f);
        
        sig[4]=new ECP();
        sig[4].copy(params.g1);
        sig[4].mul(s.f);

        
        sig[5]=new ECP2();
        sig[5].copy(params.g2);
        sig[5].mul(s.f);
        
        sig[6]=new ECP();
        sig[6].copy(c[3]);
        sig[6].mul(s.f);
        

        return sig,s;
}

gs_prove=function(c,r,W,s,mvec,ePK,uPK,uSK,params){

    //convert to bignum notation 0/1
    bigvec=[]
    for (i=0;i<mvec.length;i++)
        if (mvec[i]==1) bigvec[i]= new FP(1)
        else bigvec[i]=new FP(0);


    //GS commits
    //scalar commits for mvec in both groups

    rcom=[] //rands1
    scom=[] //rands2

    mcom1=[] //com(m[i]) in G1
    mcom2=[] //com(m[i]) in G2

    for (i=0;i<mvec.length;i++){
        rcom[i]=new FP(BIG.randomnum(params.n,params.rng));
        scom[i]=new FP(BIG.randomnum(params.n,params.rng));
        mcom1=ePK.coms1(bigvec[i],rcom[i]);
        mcom2=ePK.coms2(bigvec[i],scom[i])
    }

    //group commits for Z=FM and W=X1^R

    R1=[new FP(BIG.randomnum(params.n,params.rng)),new FP(BIG.randomnum(params.n,params.rng))];
    //R2=[]
    //R2[0]=new FP(BIG.randomnum(params.n,params.rng));
    //R2[1]=new FP(BIG.randomnum(params.n,params.rng));

    wcom=comg1(W,R1[0],R1[1]);

    scomr=new FP(BIG.randomnum(params.n,params.rng));
    rcom2=ePK.coms2(r,scomr)

    //proofs

    ///PV : H(vk)*scomr
    var m=MPIN.hashit(0,uPK);  //0 because function takes optional argument
    //var piV=MPIN.mapit(m); OLD ROM HASH
    
    m=BIG.fromBytes(m);
    m.mod(params.p);

    
    var piV=new ECP();
    piV.copy(ePK.h1)
    piV.mul(m)
    piV.add(ePK.h2) //NEW standard model hash: see paper

    piV.mul(scomr.f);

    
    ///PR : g1*scomr
    var piR=new ECP();
    piR.copy(params.g1);
    piR.mul(scomr.f);

    
    
    ///PM : U1*scomr+ui*scom[i]
    var piM=new ECP();
    piM.copy(ePK.UE);
    piM.mul(scomr.f);
    temp= new ECP();
    for (i=0;i<bigvec.length;i++){
        temp.copy((ePK.usig)[i+1]);
        temp.mul(scom[i].f);
        piM.add(temp);
    }

    

    //proof-U : binds W and r, full multiscalar in G1
    TX1=new FP(BIG.randomnum(params.n,params.rng));
    TX2=new FP(BIG.randomnum(params.n,params.rng));

    //pi 
    tv=new ECP2;
    ONE=new FP(1);
    tv=ePK.si2(ONE); //will neg later

    piX=[]
    piX[0]=[]
    piX[1]=[]

    for (i=0;i<2;i++){
    piX[i][0]=new ECP2();
    piX[i][0].copy(tv[i]);
    piX[i][0].mul(R1[0].f);
    temp=new ECP2();
    temp.copy(ePK.v1[i]);
    temp.mul(TX1.f);
    piX[i][0].add(temp);
    piX[i][0].neg();


    piX[i][1]=new ECP2();
    piX[i][1].copy(tv[i]);
    piX[i][1].mul(R1[1].f);
    temp=new ECP2();
    temp.copy(ePK.v1[i]);
    temp.mul(TX2.f);
    piX[i][1].add(temp);
    piX[i][1].neg();
    }

    //theta free/cheap + T1*u10+T2*u11 // T1*u20+T2*u21
    thetaX=[];
    thetaX[0]=new ECP(); //first part of EQ is zeroes
    thetaX[0].copy(ePK.u1[0]);
    thetaX[0].mul(TX1.f);
    temp=new ECP();
    temp.copy(ePK.u1[1]);
    temp.mul(TX2.f);
    thetaX[0].add(temp);


    thetaX[1]=new ECP(); //first part of EQ is zeroes
    thetaX[1].copy(ePK.u2[0]);
    thetaX[1].mul(TX1.f);
    temp=new ECP();
    temp.copy(ePK.u2[1]);
    temp.mul(TX2.f);
    thetaX[1].add(temp);
    
    
    temp.copy(params.g1);
    temp.mul(scomr.f);
    thetaX[1].add(temp);


    //// Quadratic proofs /////

    qpi=[]
    qtheta=[]

    siab1=[]
    siab1[0]=[]
    siab1[0][0]=new ECP;
    siab1[0][1]=new ECP;
    siab1[1]=ePK.si1(ONE);
    siab1[-1]=[];
    siab1[-1][0]= new ECP;
    siab1[-1][1]= new ECP;

    siab1[-1][0].copy(siab1[1][0]);
    siab1[-1][1].copy(siab1[1][1]);
    siab1[-1][0].neg;
    siab1[-1][1].neg;

    siab2=[]
    siab2[0]=[]
    siab2[0][0]=new ECP2;
    siab2[0][1]=new ECP2;
    siab2[1]=ePK.si2(ONE);
    siab2[-1]=[];
    siab2[-1][0]= new ECP2;
    siab2[-1][1]= new ECP2;
    siab2[-1][0].copy(siab2[1][0]);
    siab2[-1][1].copy(siab2[1][1]);
    siab2[-1][0].neg;
    siab2[-1][1].neg;
    temp1=new ECP();
    temp2=new ECP2();
    temps=new FP();

    for (i=0;i<mvec.length;i++){
        qpi[i]=[]
        qtheta[i]=[]
        for (j=0;j<2;j++){
            qpi[i][j]=[]
            qtheta[i][j]=[]
            T=new FP(BIG.randomnum(params.n,params.rng));
            for (l=0;l<2;l++){
        
                qpi[i][j][l]=new ECP2();
                qpi[i][j][l].copy(siab2[mvec[i]-j][l]);
                qpi[i][j][l].mul(rcom[i].f);
                temp2.copy(ePK.v1[l]);
                temps.copy(rcom[i]);
                temps.mul(scom[i]);
                temps.sub(T);
                temp2.mul(temps.f);
                qpi[i][j][l].add(temp2)
            
                qtheta[i][j][l]=new ECP();
                qtheta[i][j][l].copy(siab1[mvec[i]+j-1][l]);
                qtheta[i][j][l].mul(scom[i].f);
                temp1.copy(ePK.u1[l]);
                temp1.mul(T.f);
                qtheta[i][j][l].add(temp1)
            }
    
        }
    }
    return {coms:{mcom1:mcom1,mcom2:mcom2,rcom2:rcom2,wcom:wcom},proofs:[piR,piV,piM,[piX,thetaX],[qpi,qtheta]]}
}

TestJS-BEL-GS.html

<!DOCTYPE HTML>
<html>
<head>
<title>Belenios JavaScript Speed Test</title>
<script type="text/javascript" src="lib/DBIG.js"></script>
<script type="text/javascript" src="lib/BIG.js"></script>
<script type="text/javascript" src="lib/FP.js"></script>
<script type="text/javascript" src="lib/ROM.js"></script>
<script type="text/javascript" src="lib/HASH.js"></script>
<script type="text/javascript" src="lib/RAND.js"></script>
<script type="text/javascript" src="lib/AES.js"></script>
<script type="text/javascript" src="lib/GCM.js"></script>
<script type="text/javascript" src="lib/ECP.js"></script>
<script type="text/javascript" src="lib/FP2.js"></script>
<script type="text/javascript" src="lib/ECP2.js"></script>
<script type="text/javascript" src="lib/FP4.js"></script>
<script type="text/javascript" src="lib/FP12.js"></script>
<script type="text/javascript" src="lib/PAIR.js"></script>
<script type="text/javascript" src="lib/MPIN.js"></script>

<script type="text/javascript" src="belenios-booth.js"></script>

<script> //qs from http://stackoverflow.com/questions/901115/how-can-i-get-query-string-values-in-javascript
var qs = (function(a) {
    if (a == "") return {};
    var b = {};
    for (var i = 0; i < a.length; ++i)
    {
        var p=a[i].split('=', 2);
        if (p.length == 1)
            b[p[0]] = "";
        else
            b[p[0]] = decodeURIComponent(p[1].replace(/\+/g, " "));
    }
    return b;
})(window.location.search.substr(1).split('&'));
 </script>

</head>
<body>
<h1>Belenios JavaScript Speed Test</h1>


<script>
        var start = new Date();
        
        k=qs["k"];
        if (typeof k == 'undefined') k=1;
        mvec=[]
        for (i=0;i<k;i++){mvec[i]=Math.floor(Math.random()+0.5);}
   		window.document.write("k=",k,"<br>Preprocessing starting... ");

        var params=initcrypto();
                
        var ekeys=electionkeys(params);
        var ppserverdone = new Date();

        var ukeys=userkeys(params,ekeys.PK);
      
		window.document.write(" done.<br>");
        var ppdone = new Date();

        //VOTING -- ENCRYPTION
        var ct=encryptchoice(params,ekeys.PK,ukeys.PK,mvec);
        c=ct[0];
        r=ct[1];
        W=ct[2];
		window.document.write("Encryption done.<br>");
        var encdone = new Date();
        
        //Check if ciphertexts are valid
        //useless if we know we just generated them, but depending on 
        //deployment might make sense (user uses 2 devices?)
        
        var valid=checkenc(c,ekeys.PK,ukeys.PK);
        var checkdone = new Date();
        
        //SIGN (with no check)
        var sig=sign_nocheck(c,ekeys.PK,ukeys.SK,ukeys.PK);
        var s=sig[1];
        var sigdone = new Date();

        var gsproof=gs_prove(c,r,W,s,mvec,ekeys.PK,ukeys.PK,ukeys.SK,params);
        window.document.write("Sig done.<br>");
        var proofdone = new Date();
        window.document.write("<H2>Performance:</H2>");
        window.document.write("<pre>Key Generation (Server), and params : "+(ppserverdone.getTime()-start.getTime())+"<br>");
        window.document.write("Key Generation (Client)             : "+(ppdone.getTime()-ppserverdone.getTime())+"<br>");
        window.document.write("Encryption                          : "+(encdone.getTime()-ppdone.getTime())+"<br>");
        window.document.write("Ciphertext Check (redundant)        : "+(checkdone.getTime()-encdone.getTime())+"<br>");
        window.document.write("Signing                             : "+(sigdone.getTime()-checkdone.getTime())+"<br><br>");
        window.document.write("GS Proof                            : "+(proofdone.getTime()-sigdone.getTime())+"<br><br>");

        window.document.write("Total                               : "+(proofdone.getTime()-start.getTime())+"<br>");
        window.document.write("<b>Voting</b>                              : "+(encdone.getTime()-ppdone.getTime()+proofdone.getTime()-checkdone.getTime())+"<br><br>");

        window.document.write("Platform: " + navigator.platform + "<br>");
        window.document.write("User-agent header: " + navigator.userAgent + "</pre>");
        
</script>
</body>
</html>

Note: for all versions of amcl that I can currently find, including amcl 2.2, ECP.mul returns the multiplied result and does not multiply in-place. Thus all the calls like Y.mul(x.f); in the above code do basically nothing.

A full implementation of the BelenioRF e-voting scheme has been published here: https://github.com/webmaster128/private-voting