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>
@@ @@ -33,7 +33,31 @@ Benchmark results. The times for split a @@
     </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

0 comments (0 inline, 0 general)