Implemention in Python of the SWE primitive of https://eprint.iacr.org/2022/433

The implementation uses the mcl library for elliptic curves and pairings operations (https://github.com/herumi/mcl)

Build instructions

You must first build the mcl library (https://github.com/herum/mcl) and then the python bindings for mcl from (https://github.com/Jemtaly/pymcl). Simply follow the instructions on (https://github.com/Jemtaly/pymcl) to build the bindings.

Once it's built, you can run the benchmark

python3 swe.py

Nix shell

If you are using nix-shell simply navigate to the root folder of this repo and type

nix-shell

Benchmarks

Results using the Baby-step Giant-step algorithm to compute the discrete log

msg_lengths	num_keys	dec_threshold	message_length (bytes)	Setup Time (ms)	Enc Time (ms)	Sig Time (ms)	Dec Time (ms)
16	5	3	32	4.936	25.137	1.000	31.944
16	5	3	64	2.449	43.814	0.956	62.069
16	5	3	128	2.407	84.617	0.959	123.387
16	10	3	32	3.074	24.680	0.953	31.626
16	10	3	64	3.076	45.115	0.955	62.080
16	10	3	128	3.061	86.326	0.956	122.817
16	10	7	32	3.072	24.730	2.274	32.310
16	10	7	64	3.056	45.212	2.278	62.739
16	10	7	128	3.050	86.261	2.292	123.549
16	15	3	32	3.799	26.057	0.957	31.740
16	15	3	64	3.723	46.658	0.958	62.058
16	15	3	128	3.708	87.582	0.959	122.774
16	15	7	32	3.727	26.242	2.277	32.332
16	15	7	64	3.763	47.828	2.284	63.899
16	15	7	128	3.754	88.681	2.333	126.806
16	15	11	32	3.739	26.252	3.685	33.122
16	15	11	64	3.741	46.795	3.690	63.513
16	15	11	128	3.732	87.631	3.690	124.277
16	15	15	32	3.721	26.295	5.204	34.025
16	15	15	64	3.724	46.796	5.205	64.380
16	15	15	128	3.729	87.846	5.202	125.327
16	20	3	32	4.399	27.531	0.956	31.664
16	20	3	64	4.400	48.024	0.958	62.035
16	20	3	128	4.404	88.930	0.958	122.808
16	20	7	32	4.383	27.589	2.281	32.355
16	20	7	64	4.391	48.030	2.287	62.678
16	20	7	128	4.402	89.677	2.283	123.566
16	20	11	32	4.376	27.664	3.688	33.124
16	20	11	64	4.413	48.179	3.691	63.588
16	20	11	128	4.399	89.247	3.685	124.425
16	20	15	32	4.387	27.796	5.205	34.039
16	20	15	64	4.404	48.352	5.198	64.436
16	20	15	128	4.393	89.352	5.190	125.652
24	5	3	32	17.827	16.995	0.953	58.733
24	5	3	64	17.972	31.250	0.958	120.252
24	5	3	128	17.226	58.473	0.957	237.481
24	10	3	32	17.872	18.397	0.954	58.788
24	10	3	64	17.800	32.727	0.960	120.113
24	10	3	128	17.783	61.274	1.018	241.868
24	10	7	32	19.267	18.607	2.287	59.554
24	10	7	64	17.816	33.102	2.305	121.108
24	10	7	128	18.420	60.912	2.366	241.080
24	15	3	32	18.514	19.859	0.956	58.737
24	15	3	64	18.526	34.185	0.959	121.632
24	15	3	128	19.741	66.198	1.033	263.656
24	15	7	32	19.703	20.538	2.343	60.877
24	15	7	64	18.717	34.144	2.274	121.914
24	15	7	128	18.498	61.511	2.300	238.799
24	15	11	32	18.522	20.038	3.726	60.260
24	15	11	64	18.479	34.322	3.689	122.134
24	15	11	128	18.487	61.616	3.685	239.666
24	15	15	32	18.529	20.024	5.218	61.158
24	15	15	64	18.484	34.410	5.205	122.624
24	15	15	128	18.460	61.988	5.276	240.367
24	20	3	32	19.146	21.262	0.956	58.670
24	20	3	64	19.162	35.622	0.962	120.014
24	20	3	128	19.181	62.833	0.959	237.163
24	20	7	32	19.182	21.498	2.337	59.513
24	20	7	64	19.184	36.124	2.293	122.788
24	20	7	128	19.477	66.389	2.378	253.664
24	20	11	32	20.400	22.318	3.842	62.482
24	20	11	64	20.687	36.990	3.832	126.797
24	20	11	128	19.775	64.032	3.778	242.579
24	20	15	32	19.221	22.363	5.318	63.608
24	20	15	64	19.859	39.701	5.710	135.434
24	20	15	128	22.034	72.815	5.944	270.306

Results using a discrete logarithm look up table

msg_lengths	num_keys	dec_threshold	message_length (bytes)	Setup Time (ms)	Enc Time (ms)	Sig Time (ms)	Dec Time (ms)
16	5	3	32	222.035	19.170	0.791	22.188
16	5	3	64	222.259	35.739	0.783	42.768
16	5	3	128	196.228	66.949	0.757	82.823
16	10	3	32	198.704	20.358	0.791	22.201
16	10	3	64	200.112	37.357	0.817	43.529
16	10	3	128	196.942	67.563	0.761	81.509
16	10	7	32	189.498	19.326	1.789	21.597
16	10	7	64	190.423	36.167	1.820	42.700
16	10	7	128	190.270	67.511	1.786	82.097
16	15	3	32	191.125	20.495	0.752	21.329
16	15	3	64	202.703	37.721	0.805	42.864
16	15	3	128	192.259	68.848	0.763	81.936
16	15	7	32	190.937	20.583	1.788	21.709
16	15	7	64	192.025	37.547	1.825	43.033
16	15	7	128	191.765	68.878	1.794	82.419
16	15	11	32	191.991	20.626	2.881	22.283
16	15	11	64	191.360	37.895	2.946	43.294
16	15	11	128	191.974	68.975	2.876	83.050
16	15	15	32	191.716	20.741	4.015	22.957
16	15	15	64	195.213	38.049	4.130	44.513
16	15	15	128	191.715	69.158	4.038	84.040
16	20	3	32	193.211	21.753	0.760	21.279
16	20	3	64	192.446	38.559	0.771	42.555
16	20	3	128	192.972	70.334	0.762	82.340
16	20	7	32	192.573	21.832	1.804	21.838
16	20	7	64	193.003	38.976	1.838	42.727
16	20	7	128	192.385	70.386	1.806	82.882
16	20	11	32	193.653	21.897	2.889	22.422
16	20	11	64	193.033	39.097	2.942	43.242
16	20	11	128	193.863	70.398	2.904	83.659
16	20	15	32	192.892	22.055	4.030	23.143
16	20	15	64	194.473	38.460	4.058	45.008
16	20	15	128	190.449	69.801	4.006	83.201
24	5	3	32	55656.133	13.681	0.769	15.188
24	5	3	64	59155.487	25.338	0.776	29.604
24	5	3	128	55134.503	47.501	0.781	57.330
24	10	3	32	53884.924	16.440	0.791	16.355
24	10	3	64	57851.953	26.923	0.790	30.580
24	10	3	128	56316.620	52.345	0.862	60.925
24	10	7	32	57032.932	15.204	1.877	15.998
24	10	7	64	57832.967	26.531	1.864	30.184
24	10	7	128	54126.322	55.261	2.024	63.821
24	15	3	32	59831.560	16.941	0.819	16.071
24	15	3	64	62799.450	30.762	0.898	32.601
24	15	3	128	56831.798	51.367	0.817	59.211
24	15	7	32	60467.994	16.992	1.947	16.683
24	15	7	64	61157.391	29.144	1.949	31.588
24	15	7	128	57903.982	55.597	2.209	64.813
24	15	11	32	60804.897	18.681	3.262	18.741
24	15	11	64	58373.881	27.984	2.989	31.077
24	15	11	128	54450.227	50.655	3.042	58.796
24	15	15	32	60024.026	17.340	4.397	18.382
24	15	15	64	60197.444	30.107	4.510	33.715
24	15	15	128	59748.321	50.397	4.193	61.850
24	20	3	32	60104.289	18.938	0.884	16.737
24	20	3	64	60265.954	30.865	0.870	31.553
24	20	3	128	59515.632	54.746	0.927	61.167
24	20	7	32	60383.634	18.587	2.032	16.958
24	20	7	64	60394.147	30.917	2.024	32.197
24	20	7	128	59762.562	54.401	2.010	61.560
24	20	11	32	60336.149	18.541	3.272	17.684
24	20	11	64	59555.589	31.177	3.207	33.133
24	20	11	128	60207.549	55.502	3.317	63.096
24	20	15	32	60385.173	19.347	4.455	19.088
24	20	15	64	60858.321	31.239	4.486	33.783
24	20	15	128	59621.032	56.738	4.811	62.438