The following tables present timing results for Encrypted Matrix Multiplication (A \times B)
using the TenSEAL Fully-Homomorphic Encryption (FHE) library. The results represent a first order analysis of the timing complexity considering Key Generation, Matrix Encryption, Matrix Multiplication, and Matrix Decryption. Two FHE algorithms assessed are: the Brakerski/Fan-Vercauteren (BFV, 2012); and the Cheon/Kim/Kim/Song (CKKS, 2017).
The results represent the median of 10 executions of the same functions for exactly the same matrix values on a AMD Ryzen 7 3800XT 8-Core Processor with 128GB of RAM running Ubuntu 18.04 LTS.
It considers values distributed in the interval [-1, 1]
.
Square Matrix Size | Poly Degree | Key Generation | Matrix Encryption | Matrix Multiplication | Matrix Decryption | Total |
---|---|---|---|---|---|---|
2 | 4096 | 0.0373685 | 0.00558531 | 0.00353527 | 0.000678956 | 0.047348 |
4 | 4096 | 0.0415051 | 0.00971408 | 0.0108032 | 0.00253088 | 0.065991 |
6 | 4096 | 0.0384495 | 0.0151066 | 0.0321764 | 0.00567592 | 0.0976619 |
8 | 4096 | 0.0378664 | 0.0249162 | 0.0531681 | 0.00990422 | 0.126971 |
10 | 4096 | 0.037962 | 0.0432207 | 0.109004 | 0.0154365 | 0.207592 |
12 | 4096 | 0.0390311 | 0.0509846 | 0.169315 | 0.02288 | 0.282631 |
14 | 4096 | 0.0390451 | 0.0726871 | 0.283288 | 0.0310608 | 0.427466 |
16 | 4096 | 0.0381212 | 0.08773 | 0.399686 | 0.0403261 | 0.565632 |
18 | 4096 | 0.0386489 | 0.105945 | 0.58683 | 0.0505936 | 0.782588 |
20 | 4096 | 0.0379708 | 0.126649 | 0.77721 | 0.0619784 | 1.00465 |
2 | 8192 | 0.351809 | 0.018675 | 0.0229037 | 0.0052375 | 0.399295 |
4 | 8192 | 0.314432 | 0.0265851 | 0.0611404 | 0.0202107 | 0.425485 |
6 | 8192 | 0.313806 | 0.0599225 | 0.182204 | 0.0451886 | 0.603148 |
8 | 8192 | 0.315484 | 0.0785349 | 0.361297 | 0.0809502 | 0.840385 |
10 | 8192 | 0.315917 | 0.13319 | 0.713796 | 0.125733 | 1.2869 |
12 | 8192 | 0.325244 | 0.160896 | 1.1832 | 0.188304 | 1.85589 |
14 | 8192 | 0.325775 | 0.232407 | 1.91734 | 0.255411 | 2.72282 |
16 | 8192 | 0.325226 | 0.2642 | 2.80793 | 0.334424 | 3.72532 |
18 | 8192 | 0.32283 | 0.329212 | 3.99955 | 0.42196 | 5.08879 |
20 | 8192 | 0.320731 | 0.397718 | 5.38735 | 0.518657 | 6.62535 |
2 | 16384 | 3.30117 | 0.0765723 | 0.153542 | 0.0343709 | 3.56885 |
4 | 16384 | 3.26297 | 0.104264 | 0.384418 | 0.137865 | 3.88944 |
6 | 16384 | 3.33185 | 0.251622 | 1.28806 | 0.314782 | 5.20725 |
8 | 16384 | 3.77817 | 0.339053 | 2.86381 | 0.643181 | 7.59356 |
10 | 16384 | 3.36282 | 0.535207 | 5.63527 | 1.01315 | 10.5234 |
12 | 16384 | 3.58629 | 0.723618 | 9.44421 | 1.4474 | 15.1965 |
14 | 16384 | 3.30264 | 0.990225 | 15.0997 | 1.95204 | 21.3634 |
16 | 16384 | 3.3449 | 1.24563 | 22.3121 | 2.57096 | 29.4396 |
18 | 16384 | 3.37075 | 1.5931 | 31.9139 | 3.28238 | 40.16 |
20 | 16384 | 3.40239 | 1.92663 | 43.2923 | 3.98654 | 52.6965 |
2 | 32768 | 22.2062 | 0.237622 | 0.498116 | 0.205471 | 23.1674 |
4 | 32768 | 22.2687 | 0.358636 | 1.91777 | 0.630358 | 25.1722 |
6 | 32768 | 22.5224 | 0.770142 | 6.3481 | 1.93495 | 31.5635 |
8 | 32768 | 21.944 | 1.21687 | 15.7835 | 3.47359 | 42.2752 |
10 | 32768 | 22.5665 | 1.89781 | 29.8854 | 5.45901 | 59.8807 |
12 | 32768 | 22.7846 | 2.63184 | 55.1396 | 7.89782 | 88.5128 |
14 | 32768 | 22.7331 | 3.64222 | 84.8491 | 10.7527 | 121.482 |
16 | 32768 | 22.5677 | 4.59591 | 131.853 | 13.785 | 172.652 |
18 | 32768 | 22.2236 | 5.84971 | 183.95 | 17.6166 | 229.475 |
20 | 32768 | 22.7574 | 7.21072 | 259.041 | 21.538 | 310.432 |
For values encoded in a 8-bits words, i.e., [-128, 127]
.
Square Matrix Size | Poly Degree | Key Generation | Matrix Encryption | Matrix Multiplication | Matrix Decryption | Total |
---|---|---|---|---|---|---|
2 | 4096 | 0.0377995 | 0.0079144 | 0.0119991 | 0.001757 | 0.059412 |
4 | 4096 | 0.0385401 | 0.0310754 | 0.04857 | 0.0101067 | 0.128903 |
6 | 4096 | 0.0388934 | 0.0711818 | 0.116208 | 0.0141443 | 0.240435 |
8 | 4096 | 0.0381538 | 0.125155 | 0.224531 | 0.0247384 | 0.411264 |
10 | 4096 | 0.0392515 | 0.202174 | 0.428509 | 0.0396459 | 0.70993 |
12 | 4096 | 0.038788 | 0.289526 | 0.699746 | 0.0572524 | 1.08411 |
14 | 4096 | 0.0393694 | 0.395334 | 1.15041 | 0.0777138 | 1.66316 |
16 | 4096 | 0.0380453 | 0.498316 | 1.63302 | 0.0991596 | 2.26808 |
18 | 4096 | 0.039335 | 0.648478 | 2.3776 | 0.12829 | 3.1923 |
20 | 4096 | 0.0386491 | 0.787167 | 3.16908 | 0.156403 | 4.14982 |
2 | 8192 | 0.31991 | 0.0245685 | 0.0622934 | 0.00594231 | 0.416783 |
4 | 8192 | 0.323777 | 0.100165 | 0.148528 | 0.0239333 | 0.596174 |
6 | 8192 | 0.325106 | 0.227095 | 0.535228 | 0.0537211 | 1.13977 |
8 | 8192 | 0.320736 | 0.398389 | 1.08796 | 0.0944704 | 1.90198 |
10 | 8192 | 0.327888 | 0.635885 | 2.19645 | 0.15062 | 3.30938 |
12 | 8192 | 0.317587 | 0.885985 | 3.60398 | 0.210393 | 5.01883 |
14 | 8192 | 0.325236 | 1.23842 | 5.87361 | 0.295459 | 7.72569 |
16 | 8192 | 0.323558 | 1.60148 | 8.53057 | 0.382403 | 10.8397 |
18 | 8192 | 0.324627 | 2.04541 | 12.3053 | 0.486117 | 15.1466 |
20 | 8192 | 0.321264 | 2.48859 | 16.6187 | 0.59123 | 20.0204 |
2 | 16384 | 3.34215 | 0.106466 | 0.299036 | 0.0276478 | 3.78774 |
4 | 16384 | 3.34082 | 0.572084 | 0.962007 | 0.11198 | 4.99987 |
6 | 16384 | 3.64353 | 1.26835 | 3.30309 | 0.247418 | 8.32709 |
8 | 16384 | 3.65239 | 1.95942 | 7.4746 | 0.435587 | 13.4169 |
10 | 16384 | 3.35543 | 3.56769 | 14.4802 | 0.692605 | 22.1931 |
12 | 16384 | 3.33258 | 5.11146 | 25.168 | 0.992516 | 34.4741 |
14 | 16384 | 3.30843 | 7.03182 | 39.4612 | 1.35115 | 51.1695 |
16 | 16384 | 3.50898 | 8.47907 | 59.7193 | 1.76845 | 73.6794 |
18 | 16384 | 3.35361 | 11.5886 | 84.2869 | 2.22871 | 101.457 |
20 | 16384 | 3.3764 | 14.309 | 116.513 | 2.77341 | 137.316 |
2 | 32768 | 19.5607 | 0.461412 | 1.09035 | 0.0958294 | 21.1562 |
4 | 32768 | 22.6645 | 2.05374 | 7.07852 | 0.390171 | 31.9644 |
6 | 32768 | 21.5771 | 3.58952 | 17.5453 | 0.85866 | 43.6383 |
8 | 32768 | 21.5342 | 6.75882 | 54.9134 | 1.52116 | 83.9918 |
10 | 32768 | 22.5634 | 12.4821 | 94.0993 | 2.43751 | 130.537 |
12 | 32768 | 22.5477 | 17.7262 | 185.33 | 3.49048 | 227.191 |
14 | 32768 | 22.9315 | 24.19 | 272.474 | 4.72813 | 322.338 |
16 | 32768 | 23.1699 | 30.9058 | 438.097 | 6.172 | 497.845 |
18 | 32768 | 23.2238 | 35.8982 | 595.899 | 7.80789 | 662.042 |
20 | 32768 | 23.0588 | 49.6902 | 851.113 | 9.5594 | 933.631 |