[Gzz-commits] manuscripts/Sigs article.rst kbmhtrade.tex poss.py

[Tuomas J. Lukka]

CVSROOT:        /cvsroot/gzz
Module name:    manuscripts
Changes by:     Tuomas J. Lukka <address@hidden>        03/05/19 12:18:08

Modified files:
        Sigs           : article.rst kbmhtrade.tex poss.py 

Log message:
        trade

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/article.rst.diff?tr1=1.111&tr2=1.112&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/kbmhtrade.tex.diff?tr1=1.1&tr2=1.2&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/manuscripts/Sigs/poss.py.diff?tr1=1.13&tr2=1.14&r1=text&r2=text

Patches:
Index: manuscripts/Sigs/article.rst
diff -u manuscripts/Sigs/article.rst:1.111 manuscripts/Sigs/article.rst:1.112
--- manuscripts/Sigs/article.rst:1.111  Mon May 19 11:58:31 2003
+++ manuscripts/Sigs/article.rst        Mon May 19 12:18:08 2003
@@ -200,10 +200,33 @@
 
 ..  raw:: latex
 
+    \begin{table*}
     \begin{tabular}{rr|rrrr}
-    $N$ & $n$ & $s$ & $t_0$ & $t_s$ & $t_v$ \\
+    $N$ & $n$ & \multicolumn{1}{c}{$s'$} & 
+               \multicolumn{1}{c}{$t_0'$} &
+               \multicolumn{1}{c}{$t_s'$} &
+               \multicolumn{1}{c}{$t_v'$} \\
+    \hline
     \input kbmhtrade
+    \hline
     \end{tabular}
+    \caption{The tradeoff between rounds of key boosting
+    and branching factor when using key boosting 
+    and Merkle hash trees to 
+    obtain the full digital signature feature set 
+    for 160 bits.
+    Notation: $N$ is the number of rounds of key boosting,
+    and $n$ is the merkle hash tree degree;
+    $s$ is the length of a signature in the underlying
+    algorithm, $k$ is the length of a public key in the underlying
+    algorithm, and $h$ is the number of bits in a hash (i.e. 160).
+    and $t_0$, $t_s$ and $t_v$ are the times
+    to generate a public key, to sign and to verify a signature
+    in the underlying scheme, respectively.
+    The primed symbols signify the same things for the derived
+    scheme.
+    }
+    \end{table*}
 
 For example,
 
Index: manuscripts/Sigs/kbmhtrade.tex
diff -u manuscripts/Sigs/kbmhtrade.tex:1.1 manuscripts/Sigs/kbmhtrade.tex:1.2
--- manuscripts/Sigs/kbmhtrade.tex:1.1  Mon May 19 11:58:31 2003
+++ manuscripts/Sigs/kbmhtrade.tex      Mon May 19 12:18:08 2003
@@ -1,23 +1,23 @@
-2 & 80 & $2 s' + 2 k' + 162 h$ & $1208925819614629174706176 t_0' +  
2417851639229258349412351$ & $2417851639229258349412352 t_0' + 2 t_s' +  
4835703278458516698824702$ & $2 t_v' +  162$ \
-3 & 54 & $3 s' + 3 k' + 165 h$ & $18014398509481984 t_0' +  36028797018963967$ 
& $54043195528445952 t_0' + 3 t_s' +  108086391056891901$ & $3 t_v' +  165$ \
-4 & 40 & $4 s' + 4 k' + 164 h$ & $1099511627776 t_0' +  2199023255551$ & 
$4398046511104 t_0' + 4 t_s' +  8796093022204$ & $4 t_v' +  164$ \
-5 & 32 & $5 s' + 5 k' + 165 h$ & $4294967296 t_0' +  8589934591$ & 
$21474836480 t_0' + 5 t_s' +  42949672955$ & $5 t_v' +  165$ \
-6 & 27 & $6 s' + 6 k' + 168 h$ & $134217728 t_0' +  268435455$ & $805306368 
t_0' + 6 t_s' +  1610612730$ & $6 t_v' +  168$ \
-7 & 23 & $7 s' + 7 k' + 168 h$ & $8388608 t_0' +  16777215$ & $58720256 t_0' + 
7 t_s' +  117440505$ & $7 t_v' +  168$ \
-8 & 20 & $8 s' + 8 k' + 168 h$ & $1048576 t_0' +  2097151$ & $8388608 t_0' + 8 
t_s' +  16777208$ & $8 t_v' +  168$ \
-9 & 18 & $9 s' + 9 k' + 171 h$ & $262144 t_0' +  524287$ & $2359296 t_0' + 9 
t_s' +  4718583$ & $9 t_v' +  171$ \
-10 & 16 & $10 s' + 10 k' + 170 h$ & $65536 t_0' +  131071$ & $655360 t_0' + 10 
t_s' +  1310710$ & $10 t_v' +  170$ \
-11 & 15 & $11 s' + 11 k' + 176 h$ & $32768 t_0' +  65535$ & $360448 t_0' + 11 
t_s' +  720885$ & $11 t_v' +  176$ \
-12 & 14 & $12 s' + 12 k' + 180 h$ & $16384 t_0' +  32767$ & $196608 t_0' + 12 
t_s' +  393204$ & $12 t_v' +  180$ \
-13 & 13 & $13 s' + 13 k' + 182 h$ & $8192 t_0' +  16383$ & $106496 t_0' + 13 
t_s' +  212979$ & $13 t_v' +  182$ \
-14 & 12 & $14 s' + 14 k' + 182 h$ & $4096 t_0' +  8191$ & $57344 t_0' + 14 
t_s' +  114674$ & $14 t_v' +  182$ \
-15 & 11 & $15 s' + 15 k' + 180 h$ & $2048 t_0' +  4095$ & $30720 t_0' + 15 
t_s' +  61425$ & $15 t_v' +  180$ \
-16 & 10 & $16 s' + 16 k' + 176 h$ & $1024 t_0' +  2047$ & $16384 t_0' + 16 
t_s' +  32752$ & $16 t_v' +  176$ \
-18 & 9 & $18 s' + 18 k' + 180 h$ & $512 t_0' +  1023$ & $9216 t_0' + 18 t_s' + 
 18414$ & $18 t_v' +  180$ \
-20 & 8 & $20 s' + 20 k' + 180 h$ & $256 t_0' +  511$ & $5120 t_0' + 20 t_s' +  
10220$ & $20 t_v' +  180$ \
-23 & 7 & $23 s' + 23 k' + 184 h$ & $128 t_0' +  255$ & $2944 t_0' + 23 t_s' +  
5865$ & $23 t_v' +  184$ \
-27 & 6 & $27 s' + 27 k' + 189 h$ & $64 t_0' +  127$ & $1728 t_0' + 27 t_s' +  
3429$ & $27 t_v' +  189$ \
-32 & 5 & $32 s' + 32 k' + 192 h$ & $32 t_0' +  63$ & $1024 t_0' + 32 t_s' +  
2016$ & $32 t_v' +  192$ \
-40 & 4 & $40 s' + 40 k' + 200 h$ & $16 t_0' +  31$ & $640 t_0' + 40 t_s' +  
1240$ & $40 t_v' +  200$ \
-54 & 3 & $54 s' + 54 k' + 216 h$ & $8 t_0' +  15$ & $432 t_0' + 54 t_s' +  
810$ & $54 t_v' +  216$ \
-80 & 2 & $80 s' + 80 k' + 240 h$ & $4 t_0' +  7$ & $320 t_0' + 80 t_s' +  560$ 
& $80 t_v' +  240$ \
+2 & 80 & $2 s + 2 k + 164 h$ & $1.21\cdot 10^{24} t_0 +  2.42\cdot 10^{24}$ & 
$2.42\cdot 10^{24} t_0 + 2 t_s +  4.84\cdot 10^{24}$ & $2 t_v +  162$ \\
+3 & 54 & $3 s + 3 k + 168 h$ & $1.8\cdot 10^{16} t_0 +  3.6\cdot 10^{16}$ & 
$5.4\cdot 10^{16} t_0 + 3 t_s +  1.08\cdot 10^{17}$ & $3 t_v +  165$ \\
+4 & 40 & $4 s + 4 k + 168 h$ & $1.1\cdot 10^{12} t_0 +  2.2\cdot 10^{12}$ & 
$4.4\cdot 10^{12} t_0 + 4 t_s +  8.8\cdot 10^{12}$ & $4 t_v +  164$ \\
+5 & 32 & $5 s + 5 k + 170 h$ & $4.29\cdot 10^{9} t_0 +  8.59\cdot 10^{9}$ & 
$2.15\cdot 10^{10} t_0 + 5 t_s +  4.29\cdot 10^{10}$ & $5 t_v +  165$ \\
+6 & 27 & $6 s + 6 k + 174 h$ & $1.34\cdot 10^{8} t_0 +  2.68\cdot 10^{8}$ & 
$8.05\cdot 10^{8} t_0 + 6 t_s +  1.61\cdot 10^{9}$ & $6 t_v +  168$ \\
+7 & 23 & $7 s + 7 k + 175 h$ & $8.39\cdot 10^{6} t_0 +  1.68\cdot 10^{7}$ & 
$5.87\cdot 10^{7} t_0 + 7 t_s +  1.17\cdot 10^{8}$ & $7 t_v +  168$ \\
+8 & 20 & $8 s + 8 k + 176 h$ & $1.05\cdot 10^{6} t_0 +  2.1\cdot 10^{6}$ & 
$8.39\cdot 10^{6} t_0 + 8 t_s +  1.68\cdot 10^{7}$ & $8 t_v +  168$ \\
+9 & 18 & $9 s + 9 k + 180 h$ & $262144 t_0 +  524287$ & $2.36\cdot 10^{6} t_0 
+ 9 t_s +  4.72\cdot 10^{6}$ & $9 t_v +  171$ \\
+10 & 16 & $10 s + 10 k + 180 h$ & $65536 t_0 +  131071$ & $655360 t_0 + 10 t_s 
+  1.31\cdot 10^{6}$ & $10 t_v +  170$ \\
+11 & 15 & $11 s + 11 k + 187 h$ & $32768 t_0 +  65535$ & $360448 t_0 + 11 t_s 
+  720885$ & $11 t_v +  176$ \\
+12 & 14 & $12 s + 12 k + 192 h$ & $16384 t_0 +  32767$ & $196608 t_0 + 12 t_s 
+  393204$ & $12 t_v +  180$ \\
+13 & 13 & $13 s + 13 k + 195 h$ & $8192 t_0 +  16383$ & $106496 t_0 + 13 t_s + 
 212979$ & $13 t_v +  182$ \\
+14 & 12 & $14 s + 14 k + 196 h$ & $4096 t_0 +  8191$ & $57344 t_0 + 14 t_s +  
114674$ & $14 t_v +  182$ \\
+15 & 11 & $15 s + 15 k + 195 h$ & $2048 t_0 +  4095$ & $30720 t_0 + 15 t_s +  
61425$ & $15 t_v +  180$ \\
+16 & 10 & $16 s + 16 k + 192 h$ & $1024 t_0 +  2047$ & $16384 t_0 + 16 t_s +  
32752$ & $16 t_v +  176$ \\
+18 & 9 & $18 s + 18 k + 198 h$ & $512 t_0 +  1023$ & $9216 t_0 + 18 t_s +  
18414$ & $18 t_v +  180$ \\
+20 & 8 & $20 s + 20 k + 200 h$ & $256 t_0 +  511$ & $5120 t_0 + 20 t_s +  
10220$ & $20 t_v +  180$ \\
+23 & 7 & $23 s + 23 k + 207 h$ & $128 t_0 +  255$ & $2944 t_0 + 23 t_s +  
5865$ & $23 t_v +  184$ \\
+27 & 6 & $27 s + 27 k + 216 h$ & $64 t_0 +  127$ & $1728 t_0 + 27 t_s +  3429$ 
& $27 t_v +  189$ \\
+32 & 5 & $32 s + 32 k + 224 h$ & $32 t_0 +  63$ & $1024 t_0 + 32 t_s +  2016$ 
& $32 t_v +  192$ \\
+40 & 4 & $40 s + 40 k + 240 h$ & $16 t_0 +  31$ & $640 t_0 + 40 t_s +  1240$ & 
$40 t_v +  200$ \\
+54 & 3 & $54 s + 54 k + 270 h$ & $8 t_0 +  15$ & $432 t_0 + 54 t_s +  810$ & 
$54 t_v +  216$ \\
+80 & 2 & $80 s + 80 k + 320 h$ & $4 t_0 +  7$ & $320 t_0 + 80 t_s +  560$ & 
$80 t_v +  240$ \\
Index: manuscripts/Sigs/poss.py
diff -u manuscripts/Sigs/poss.py:1.13 manuscripts/Sigs/poss.py:1.14
--- manuscripts/Sigs/poss.py:1.13       Mon May 19 11:58:31 2003
+++ manuscripts/Sigs/poss.py    Mon May 19 12:18:08 2003
@@ -41,7 +41,7 @@
 
 def merkle_hashtree(n, S):
     return (2L**n * S[0], S[1], 
-               S[2] + S[3] + n * S[4],
+               S[2] + S[3] + (n+1) * S[4],
                S[4],
                S[4],
                2L**n * S[5] + 2L**(n+1) - 1,