Shamira Changeset - 3c3a529119dd

Changeset - 3c3a529119dd

Parent rev.

Child rev.

[Not reviewed]

default

0 2 0

Laman - 4 years ago 2020-12-18 12:30:43

updated performance.md

2 files changed with 28 insertions and 2 deletions:

performance.md

src/shamira/fft.py

0 comments (0 inline, 0 general)

performance.md

➞

Show inline comments

 # Performance comparison #
 ## The base case ##
 Let's assume we have a secret of length _m_. The splitting takes _n_ evaluations of a polynomial of order _k_ (over Galois field 256) for each byte, leading to _O(n\*k\*m)_ finite field multiplications. Reconstruction of the constant parameters during joining first precomputes parts of the Lagrange polynomial and then reuses them for each byte, taking _O(k\*k + k\*m)_ multiplications.
 Benchmark results. The times for split and join mean _seconds per byte_ of the secret length:
+Benchmark results. Measured on a mid-end laptop made in 2020. The times for split and join mean _seconds per byte_ of the secret length:
 <table>
     <tr>
         <th>Revision</th>
         <th>Features</th>
         <th>k / n parameters</th>
         <th>Split</th>
         <th>Join</th>
     </tr>
     <tr>
         <td rowspan="2">a47ae3e113cc</td>
         <td rowspan="2">-</td>
         <td>2 / 3</td>
@@ @@ -27,13 +27,37 @@ Benchmark results. The times for split a @@
     <tr>
         <td rowspan="2">c6815615a077</td>
         <td rowspan="2">gfmul() caching</td>
         <td>2 / 3</td>
         <td>5.38e-06</td>
         <td>4.28e-05</td>
     </tr>
     <tr>
         <td>254 / 254</td>
         <td>0.00741</td>
         <td>0.00156</td>
     </tr>
 </table>
@@ \ No newline at end of file @@
     <tr>
         <td rowspan="2">0957647049ef</td>
         <td rowspan="2">splitting with FFT</td>
         <td>2 / 3</td>
         <td>1.26e-05</td>
         <td>-</td>
     </tr>
     <tr>
         <td>254 / 254</td>
         <td>0.00828</td>
         <td>-</td>
     </tr>
     <tr>
         <td rowspan="2">d5f60adc56c0</td>
         <td rowspan="2">splitting with FFT,<br> caching gfmul(), gfpow(), precompute_x()</td>
         <td>2 / 3</td>
         <td>7.88e-06</td>
         <td>-</td>
     </tr>
     <tr>
         <td>254 / 254</td>
         <td>0.00183</td>
         <td>-</td>
     </tr>
 </table>

src/shamira/fft.py

➞

Show inline comments

 # GNU GPLv3, see LICENSE
 import math
 import cmath
 import itertools
 from functools import cache
 from .gf256 import gfmul, gfpow
 # divisors of 255 and their factors in natural numbers
 DIVISORS = [3, 5, 15, 17, 51, 85, 255]
 FACTORS = {3: [3], 5: [5], 15: [3, 5], 17: [17], 51: [3, 17], 85: [5, 17], 255: [3, 5, 17]}
 # values of n-th square roots in GF256
 SQUARE_ROOTS = {3: 189, 5: 12, 15: 225, 17: 53, 51: 51, 85: 15, 255: 3}

0 comments (0 inline, 0 general)